圖靈機

圖靈機tou4 ling4 gei1（英文：Turing machine），又有叫確定型圖靈機，係運算理論上好常分析嘅運算模型，個名取自廿世紀初嘅英國大數學家亞倫圖靈（Alan Turing）。一部圖靈機嘅運作如下：一部圖靈機會讀取一條分做若干個格嘅帶，條帶每個格裏面都會有個符號（可以係 1 同 0 等多個款）；喺每一個時間點，部圖靈機個讀取器都會位於條帶其中一格，而部機會做以下三個基本作業當中是但一個：

1. 讀取讀取器下嗰格係乜符號；
2. 編輯嗰格－寫一個新嘅符號落去或者刪除咗嗰格佢；
3. 將條帶向左或者向右移一格，等個讀取器可以讀取打前嗰個格隔離嘅一個格。

一部圖靈機嘅想像圖；部機會一路讀取條帶上面嘅一格，並且對嗰個格作出運算，再決定要使唔使改嗰格同埋跟住要向左郁定向右郁。

一條圖靈機讀嘅帶會好似以下噉樣，當中 $s_{i}$ 代表第 $i$ 款符號：

圖靈機呢部抽象機械就噉睇好似好簡單，但查實可以計到好多嘢；原則上，是但攞一個演算法，都梗會有一款圖靈機能夠模擬呢段演算法嘅邏輯。

例子

例：計加減法

想像以下嘅演算法，條帶上面有兩個數值，$x$ 同 $y$，兩個都用二進制表達，而兩個數之間同條帶嘅起始有個 $ 做標示，即係話部機會讀嘅輸入會類似噉嘅樣：

• $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）如下：

1. 攞補充－將 1 冚唪唥變做 0，0 冚唪唥變做 1；
2. 將個數加 1（睇 T1）；
3. 再做一次補充。

T1（將個數加 1）如下：

1. 如果喺個數嘅左邊盡頭（$）起始，行去個數嘅右邊盡頭；
2. 由右邊開始行，將所有 1 變做 0，直至
3. 將第一個 0 變成 1。

例如如果輸入係 $0010$0011，部機行完一次段演算法之後，條帶嘅狀態就會變成 $0000$0101（「0101」喺二進制入面係 5）－呢一部圖靈機曉做加減數。

睇埋

• 運算理論
• 圖靈完整性

文獻

• 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.

拎

• （英文） 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.