※ 引述《edhs0011 (偉)》之銘言： : 請問各位關於第5題Turing machine : 所謂turing machine 他的指令運作方式為何? : 何謂symbol及state? : 題目如下 : a turing machine instruction consists of 5 components: : (current state, current symbol, next symbol, next state , direction of move) : given a turing machine with the following avaliable instruction : (1,0,1,2,R), (1,1,1,2,R), (2,0,1,2,R), (2,1,0,2,R), (2,b,b,3,L) : and initial configuration show below: : ----------------------------------------------- : | . | . | b | b | 0 | 1 | 1 | b | b | . | . | . | : ----------------------------------------------- : ^ : | : 1 1. show the sequential of operation performed by this turing machine. b b 0 1 1 b b ^ | 1 一開始的狀態是 "1" ,開始的符號是 "0" , 所以我們可以找到(1,0,1,2,R)這條指令 執行結果如下: b b 1 1 1 b b ^ | 2 執行完(1,0,1,2,R)這條指令後 ,因為next state是"2",且方向往右邊移動, 指到的符號為"1",所以我們找到(2,1,0,2,R)這條指令, 執行結果如下: b b 1 0 1 b b ^ | 2 經過一連串動作 ,就是下面的操作, 直到"halt" ,就是沒有所提供的指令 可以執行的時候 ,我們就可以停止了 operation ---------------------------------------- Initial b b 0 1 1 b b ^ (1,0,1,2,R) b b 1 1 1 b b ^ (2,1,0,2,R) b b 1 0 1 b b ^ (2,1,0,2,R) b b 1 0 0 b b ^ (2,b,b,3,L) b b 1 0 0 b b ^ : 2. a bit inverter converts 0s to 1s and 1s to 0s. design a turing machine that : will do the bit conversion and illustrate the conversion process with the : string 1101. : 終於key完了...希望有好心的高手能夠交我^^ 這題留給大家練習 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 211.74.191.134