圖靈機

又有叫確定型圖靈機，係運算理論上好常分析嘅運算模型，個名取自廿世紀初嘅英國大數學家亞倫圖靈。一部圖靈機嘅運作如下：一部圖靈機會讀取一條分做若干個格嘅帶，條帶每個格裏面都會有個符號；喺每一個時間點，部圖靈機個讀取器都會位於條帶其中一格，而部機會做以下三個基本作業當中是但一個：
讀取讀取器下嗰格係乜符號；
編輯嗰格－寫一個新嘅符號落去或者刪除咗嗰格佢；
將條帶向左或者向右移一格，等個讀取器可以讀取打前嗰個格隔離嘅一個格。

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

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

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

再想像部圖靈機跟以下嘅演算法行：

// 由 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如下：
如果喺個數嘅左邊盡頭起始，行去個數嘅右邊盡頭；
由右邊開始行，將所有 1 變做 0，直至
將第一個 0 變成 1。

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

運算理論
圖靈完整性

參考 
B. Jack Copeland ed. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Clarendon Press (Oxford University Press), Oxford UK, ISBN 0-19-825079-7. Contains the Turing papers plus a draft letter to Emil Post re his criticism of "Turing's convention", and Donald W. Davies' Corrections to Turing's Universal Computing Machine.
Martin Davis (ed.) (1965), The Undecidable, Raven Press, Hewlett, NY.
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.

電腦科學
運算理論