圖 靈 機
閱讀設定
![](https://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/330px-Maquina.png)
讀取 讀取 器 下 嗰格係 乜符號 ;編輯 嗰格-寫 一個新嘅符號落去或者刪除咗嗰格佢;將 條 帶 向 左 或 者 向 右 移 一 格 ,等 個 讀取 器 可 以讀取 打 前 嗰個格 隔離 嘅一 個 格 。
一條圖靈機讀嘅帶會好似以下噉樣,
例 子
[例 :計 加減 法
$
做
$0010$0011
(「0010」喺二 進 制 係 2,而「0011」喺二 進 制 係 3)。
// 由 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 冚唪唥變做 0,0 冚唪唥變做 1; 將 個數 加 1(睇 T1);再 做一 次 補充 。
T1(
- 如果喺個
數 嘅左邊 盡 頭 ($)起 始 ,行 去 個數 嘅右邊 盡 頭 ; 由 右邊 開始 行 ,將 所有 1變 做 0,直 至 將 第 一 個 0變成 1。
$0010$0011
,$0000$0101
(「0101」喺
睇埋
[文獻
[- 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.