圖靈機

圖靈機是由艾倫·圖靈（1937年）發明的一種理論計算機器，用作數學計算的理想化模型。圖靈機由一系列稱為“紙帶”的單元格組成，紙帶可以來回移動；一個稱為“磁頭”的活動元件，它具有稱為“狀態”的屬性，並且可以更改其下方活動單元格的稱為“顏色”的屬性；以及一組指令，用於說明磁頭應如何修改活動單元格並移動紙帶（Wolfram 2002，第 78-81 頁）。在每個步驟中，機器可以修改活動單元格的顏色並更改磁頭的狀態。之後，它將紙帶向左或向右移動一個單位。

圖靈機在 Wolfram 語言中實現為TuringMachine.

Macura（2005）考慮了圖靈機的推廣，其中允許磁頭在任一方向移動 步。

上面使用 Wolfram（2002）提出的一種符號形式顯示了用於指定三狀態、雙色圖靈機的模板。在此圖中，狀態由包含指標的正方形表示，指標指示三個可能的方向中的任何一個；“顏色”屬性由正方形的顏色表示；指令由一列中的兩個正方形表示，頂部的正方形表示活動單元格的可能顏色和狀態，底部的正方形給出活動單元格的新狀態和顏色，以及紙帶應移動的方向。特殊狀態 0（沒有指標）表示圖靈機應停止的狀態，即停止計算。

（不允許具有停機狀態的機器） 狀態、 色圖靈機的數量由 給出（Wolfram 2002，第 888 頁）。

上面說明了一個三狀態、雙色圖靈機的示例（Wolfram 2002，第 78 頁）。它總共有 條規則，這些規則描述了所有可能狀態下的機器行為。一般來說，一個 狀態、 色圖靈機需要 條規則來指定其行為。雖然這些規則中的任何數量都可能指定停機條件，但最常考慮的圖靈機具有 0 或 1 個停機狀態。

圖靈機可以永遠執行、進入迴圈，或達到特定狀態或條件集（即，磁頭是否會到達給定位置，紙帶上是否會產生給定模式等等），在這種狀態或條件下，它被規定為停止。確定圖靈機是否會針對給定的輸入和規則集停止被稱為停機問題。一個 狀態、雙符號圖靈機，它從空白紙帶開始，並在達到停機狀態之前儘可能多地寫入 1，被稱為忙碌的海狸。對於 狀態二進位制圖靈機，忙碌的海狸寫入的 1 的數量表示為 。類似地，雙色 狀態圖靈機在停止之前可以採取的最大步數表示為 。

二維圖靈機最常被稱為方格上的螞蟻（turmites，儘管有時使用術語“ant”和“vant”），以及六邊形網格上的“蜜蜂”、“蠕蟲”或“海龜”。方格上最著名的螞蟻是蘭頓螞蟻。