圖靈機
閱讀設定
- 讀取讀取器下嗰格係乜符號;
- 編輯嗰格-寫一個新嘅符號落去或者刪除咗嗰格佢;
- 將條帶向左或者向右移一格,等個讀取器可以讀取打前嗰個格隔離嘅一個格。
一條圖靈機讀嘅帶會好似以下噉樣,當中 代表第 款符號:
圖靈機呢部抽象機械就噉睇好似好簡單,但查實可以計到好多嘢;原則上,是但攞一個演算法,都梗會有一款圖靈機能夠模擬呢段演算法嘅邏輯[3]。
例子
[編輯]- 例:計加減法
想像以下嘅演算法,條帶上面有兩個數值, 同 ,兩個都用二進制表達,而兩個數之間同條帶嘅起始有個 $
做標示,即係話部機會讀嘅輸入會類似噉嘅樣[4]:
$0010$0011
(「0010」喺二進制係 2,而「0011」喺二進制係 3)。
再想像部圖靈機跟以下嘅演算法行[4]:
// 由 x 嗰度減 1,再加 1 落 y 嗰度,直至 x = 0 為止。
repeat until x == 0, then HALT {
// 用 T2(睇下面)
subtract 1 from x
// 用 T1(睇下面)
add 1 to y
go back to the first $
}
T2(將個數減 1)如下:
- 攞補充-將 1 冚唪唥變做 0,0 冚唪唥變做 1;
- 將個數加 1(睇 T1);
- 再做一次補充。
T1(將個數加 1)如下:
- 如果喺個數嘅左邊盡頭($)起始,行去個數嘅右邊盡頭;
- 由右邊開始行,將所有 1 變做 0,直至
- 將第一個 0 變成 1。
例如如果輸入係 $0010$0011
,部機行完一次段演算法之後,條帶嘅狀態就會變成 $0000$0101
(「0101」喺二進制入面係 5)-呢一部圖靈機曉做加減數[4]。
睇埋
[編輯]文獻
[編輯]- Emil Post (1936), "Finite Combinatory Processes—Formulation 1", Journal of Symbolic Logic, 1, 103–105, 1936. Reprinted in The Undecidable, pp. 289ff.
- Emil Post (1947), "Recursive Unsolvability of a Problem of Thue", Journal of Symbolic Logic, vol. 12, pp. 1–11. Reprinted in The Undecidable, pp. 293ff. In the Appendix of this paper Post comments on and gives corrections to Turing's paper of 1936–1937. In particular see the footnotes 11 with corrections to the universal computing machine coding and footnote 14 with comments on Turing's first and second proofs.
參考
[編輯]- ↑ Hodges, Andrew (2012). Alan Turing: The Enigma (The Centenary Edition). Princeton University Press.
- ↑ Petzold, C. (2008). The annotated Turing: a guided tour through Alan Turing's historic paper on computability and the Turing machine. Wiley Publishing.
- ↑ Rabin, Michael O. (June 2012). Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View 互聯網檔案館嘅歸檔,歸檔日期2019年6月5號,..
- ↑ 4.0 4.1 4.2 Turing Machine example to add two numbers.
拎
[編輯]- (英文) Turing Machine on Stanford Encyclopedia of Philosophy.
- (英文) Detailed info on the Church–Turing Hypothesis. (Stanford Encyclopedia of Philosophy).
- (英文) Turing Machine-Like Models in Molecular Biology, to understand life mechanisms with a DNA-tape processor.