波斯特-圖靈機

Post-圖靈機是一種特別簡單類型的圖靈機的程式公式化，由下面描述的Emil Post的圖靈等價的計算模型構成。（Post的模型和圖靈的模型，儘管相互之間非常類似，但卻是獨立開發的。圖靈的論文在1936年五月出版，Post的論文在十月出版。）

基本介紹

• 中文名：波斯特-圖靈機
• 學科：計算機

簡介

Post-圖靈機使用二元字母表，無限序列的二元存儲位置，和帶有在存儲位置上雙向移動和一次一個更改其內容的指令的原始程式語言。"Post-圖靈程式"和"Post-圖靈機"的名字由Martin Davis在1973年-1974年使用（Davis 1973, p.69ff）。後來Davis在1980年使用名字"Turing-Post程式"（Davis, in Steen p. 241）。

Post模型

在他1936年的論文"Finite combinatory processes—formulation 1"（可以在The Undecidable的289頁找到它），Emil Post描述了非常簡單的一個模型，它被猜測為"邏輯上等價於遞歸函式"，並且後來被證明確實如此。

Post的模型採用了由"雙向無限序列的空間或盒子"組成的"符號空間"，每個盒子能處於在兩種可能狀態中之一，也就是"有標記的"（一個豎線）和"無標記的"（空）。最初，有限多的盒子是有標記的，餘下的是無標記的。接著一個"工人"在盒子間移動，一次只操作一個盒子，依據固定有限的"指令的集合"，它們編號為（1,2,3,...,n）。開始於"被挑選為起點的盒子"，工人每次一條的服從於指令集合，開始於指令1。

指令可以要求工人進行下列"基本活動"或"操作":

• （a）標記當前操作的盒子（假定為空的），
• （b）去除盒子的標記（假定為有標記的），
• （c）移動到右邊的盒子，
• （d）移動到左邊的盒子，
• （e）確定當前的盒子是否是有標記的。

特別是，給工人的第i條"指令"是下列形式之一：

• （A）進行操作O_i[O_i=（a），（b），（c）或（d）]並接著服從指令j_i，
• （B）進行操作（e）並依據答案的與否來相應的服從指令j_i'或j_i' '，
• （C）停止。

（上述交錯的文本和斜體同最初一樣）。Post備註說這種公式處於開發的"初始階段"，並提及了在最終的"終極形式"中的一些可能的"更大的靈活性"，包括：

• （1）把無限的盒子替代為有限可擴展的符號空間，"擴展原始操作來允許隨著處理的進行對給定的有限符號空間作必要的延伸"，
• （2）使用多於兩個符號的字母表，"有多於一種的方式標記盒子"，
• （3）介入有限多的"物理對象充當指針，工人識別它們並從一個盒子移動到另一個"。

圖靈機

圖靈機（英語：Turing machine），又稱確定型圖靈機，是英國數學家艾倫·圖靈於1936年提出的一種抽象計算模型，其更抽象的意義為一種數學邏輯機，可以看作等價於任何有限邏輯數學過程的終極強大邏輯機器。

對於任意一個圖靈機，因為它的描述是有限的，因此我們總可以用某種方式將其編碼為字元串。我們用{\displaystyle \langle M\rangle }表示圖靈機{\displaystyle M}的編碼。

我們可以構造出一個特殊的圖靈機，它接受任意一個圖靈機{\displaystyle M}的編碼{\displaystyle \langle M\rangle }，然後模擬{\displaystyle M}的運作，這樣的圖靈機稱為通用圖靈機（Universal Turing Machine）。現代電子計算機的計算模型其實就是這樣一種通用圖靈機，它能接受一段描述其他圖靈機的程式，並運行程式實現該程式所描述的算法。