圖ず靈れい機き

一部圖靈機嘅想像圖；部ぶ機會きかい一路讀取條帶上面嘅一格，並なみ且對嗰個格かく作出さくしゅつ運算うんざん，再さい決定けってい要よう使つかい唔使改あらため嗰格同どう埋うめ跟住要よう向こう左ひだり郁いく定てい向こう右みぎ郁いく。

圖ず靈れい機き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.