图灵机

图灵机是由艾伦·图灵（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”），以及六边形网格上的“蜜蜂”、“蠕虫”或“海龟”。方格上最著名的蚂蚁是兰顿蚂蚁。