0
Q
圖靈機設計0和1
A
回答
2
我假設你想要磁帶字母只包含0,1和 - (空白)。在使用單磁帶圖靈機時,我們的策略是卓有成效的:我們將在中間的0點周圍來回跳動,並在我們找到它們時將其交叉掉1。我們將繼續,直到我們用完1
s並達到空白。那時,磁帶上剩下的全部是1^| m-n |以及n + m + 1- | m-n |零。最後,我們將結果複製到磁帶的開頭(如果這不是已經存在的地方,即m> n)並清除零。
Q s s' D Q'
// read past 1^n
q0 1 1 R q0
// read through zeroes
q0 0 0 R q1
q1 0 0 R q1
// mark out the first 1 remaining in 1^m
q1 1 0 L q2
// read through zeros backwards
q2 0 0 L q2
// mark out the last 1 remaining in 1^n
q2 1 0 R q1
// we were reading through zeroes forward
// and didn't find another 1. n >= m and
// we have deleted the same number from
// the first and last parts so just delete
// zeroes
q1 - - L q3
q3 0 - L q3
q3 1 1 L halt_accept
// we were reading through zeroes backwards
// and didn't find another 1. n < m and we
// accidentally deleted one too many symbols
// from the 1^m part. write it back and start
// copying the 1s from after the 0s back to
// the beginning of the tape. then, clear zeroes.
q2 - - R q4
q4 0 1 R q5
q5 0 0 R q5
q5 1 0 L q6
q6 0 0 L q6
q6 1 1 R q4
q5 - - L q7
q7 0 - L q7
q7 1 1 L halt_accept
當然,沒有TM例子是沒有它的執行的例子是完整的。
-111110111- => -111110111- => -111110111-
^ ^ ^
q0 q0 q0
=> -111110111- => -111110111- => -111110111-
^ ^ ^
q0 q0 q0
=> -111110111- => -111110011- => -111110011-
^ ^ ^
q1 q2 q2
=> -111100011- => -111100011- => -111100011-
^ ^ ^
q1 q1 q1
=> -111100001- => -111100001- => -111100001-
^ ^ ^
q2 q2 q2
=> -111100001- => -111000001- => -111000001-
^ ^ ^
q1 q1 q1
=> -111000001- => -111000001- => -111000001-
^ ^ ^
q1 q1 q1
=> -111000000- => -111000000- => -111000000-
^ ^ ^
q2 q2 q2
=> -111000000- => -111000000- => -111000000-
^ ^ ^
q2 q2 q2
=> -110000000- => -110000000- => -110000000-
^ ^ ^
q1 q1 q1
=> -110000000- => -110000000- => -110000000-
^ ^ ^
q1 q1 q1
=> -110000000- => -110000000- => -11000000--
^ ^ ^
q1 q3 q3
=> -1100000--- => -110000---- => -11000-----
^ ^ ^
q1 q3 q3
=> -1100------ => -110------- => -11--------
^ ^ ^
q1 q3 q3
=> -11--------
^
halt_accept
相關問題
- 1. 圖靈機設計
- 2. 計算理論圖靈機
- 3. 統計員的圖靈機圖
- 4. 圖靈機器和機器圖解
- 5. Is!0和!1比1和0好嗎?
- 6. 解釋一個圖靈機的計算
- 7. 平方根計算圖靈機
- 8. 設計一個圖靈機的狀態表
- 9. 類圖設計問題:1到n和1到1
- 10. 隨機選擇0和1之間
- 11. 圖靈機停機問題
- 12. 圖靈機配置
- 13. 預計1實際0
- 14. 隨機插入一個0和1與1的特定數
- 15. 如何在Java中輸出序列'1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 ...'?
- 16. 圖像精靈和觸摸設備
- 17. 圖靈機與模式
- 18. 如何模擬圖靈機?
- 19. 素數的圖靈機
- 20. 設計一個靈活的用戶查找機制
- 21. 噴漆設備返回的發動機== 0,類型:1
- 22. 從其他計算機移動精靈
- 23. 如何計算0111爲0 + 1 + 1 + 1 = 3在php中
- 24. plt.plot [:,0]和[:,1]的含義
- 25. 0和1的排列
- 26. 加速期0和1
- 27. C++與隨機數只有0到1
- 28. AWK gensub正則表達式反斜槓0和反斜槓1不靈
- 29. 替換二進制形式0-> 1和1-> 0值 - perl
- 30. erlang,'catch 1 = 0'和'(catch 1 = 0)'有什麼區別?