Re: [問題] 96年政大資科
※ 引述《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
推
07/03 16:15, , 1F
07/03 16:15, 1F
推
07/03 17:02, , 2F
07/03 17:02, 2F
推
07/03 17:12, , 3F
07/03 17:12, 3F
推
07/03 17:30, , 4F
07/03 17:30, 4F
推
07/03 17:32, , 5F
07/03 17:32, 5F
討論串 (同標題文章)