關於計概的問題
先祝大家新年快樂
知道不該在此版發這篇文章的
但是我實在找不到地方問
只好來高手如雲的史萊姆po此篇文(都要考試了~只是我非本科系,很多沒有學過- -計概課本也找不到答案 ==冏)
Please read the definitions of Turing machine carefully, then answer the following questions:
The instruction(1,0,1,2,R) stands for
If you are in state 1 and you are reading symbol 0 from the tape
Then write symbol 1 onto the tape
Go into state 2
Move Right
Consider the following Turing machine:
(1,1,1,1,R)
(1,0,0,1,R)
(1,b,1,2,L)
(2,1,1,2,L)
(2,0,0,2,L)
(2,b,0,3,L)
1、Ecplain what the Turing machine does when run on any binary input string of length n.
2、Analyze the time efficiency of the Turing machine.
3、 If you think it is possible to do the same operation more efficiently, explain how you would do it, otherwise explain why it is not possible to be more efficient.
|