状态
步数
纸带上的符号
状况

当前状态 读取 写入 移动 下一状态

更多关于图灵机

图灵机模拟器

图灵机是最简单的计算机:一个读写头读取无限长纸带上的一个符号,写入一个符号,向左或向右移动一格并改变状态,一切都遵循一张简短的规则表。艾伦·图灵在 1936 年发明了它,你的计算机所做的一切原则上都能用这种方式完成。编写你自己的规则或载入一个示例,按下“运行”,看纸带一步步变化,下方还有一张记录其完整历史的图示。 选择一个程序或自己编写,填写输入后按“运行”,或按“单步”逐条执行规则;“后退”可撤销一步。程序的每一行是一条规则:状态、读到的符号、要写的符号、移动(L、R,或 N 表示不移动)以及下一状态,例如 A 0 -> 1 R B。用 _ 表示空白格。机器从第一条规则的状态开始,位于输入的第一个符号上,在进入 H、accept 或 reject,或者没有规则适用时停止。图示从上到下显示每一步之后的纸带。

它是如何运作的

  1. 选择一个示例程序,或者编写形如 A 0 -> 1 R B 的规则,每行一条,然后填写输入。
  2. 按“运行”观看读写头移动,或按“单步”逐条执行规则;“后退”可撤销一步。
  3. 在信息块中查看状态、步数和纸带上的符号,在图示中查看纸带的历史。

机器如何工作

在任何时刻,机器都处于少数几个状态之一,读写头停在纸带的某一格上。对应该状态和读写头下符号的规则说明三件事:在这一格写入哪个符号,向左、向右移动还是不动,以及接下来进入哪个状态。这就是整台机器。当它到达停机状态(如 H、accept 或 reject),或者没有规则适用时,它就停止。一个给二进制数加 1 的程序只需要九条这样的规则。

忙碌海狸

在空白纸带上启动、有 n 个状态的机器中,哪一台在停机前写下的 1 最多?蒂博尔·拉多(Tibor Radó)在 1962 年提出了这个问题。这些冠军被称为忙碌海狸,它们的增长比计算机能计算的任何函数都快。两个状态在 6 步内写下 4 个 1,三个状态写下 6 个 1,四个状态在 107 步内写下 13 个 1。1989 年发现的五状态冠军在 47,176,870 步内写下 4,098 个 1;2024 年,一个在线协作项目用经计算机验证的数学证明了:没有其他会停机的五状态机器运行得更久。

常见问题

怎样编写一条规则?

每行一条规则:当前状态、读到的符号、要写的符号、移动(L、R 或 N)以及下一状态,例如 A 0 -> 1 R B。箭头和逗号可写可不写。用 _ 表示空白格,用 # 写注释。机器从第一条规则的状态开始;名为 H 或 halt 的下一状态会使它停机,accept 和 reject 则使它停机并给出判定结果。

图灵机真的什么都能计算吗?

只要纸带和时间足够,任何计算机能计算的,它都能计算:这就是丘奇–图灵论题。图灵机没有内存限制,所以在这个意义上它比任何真实的计算机都更强大,尽管慢得多。它做不到的是回答所有问题:图灵证明了,没有任何机器能对每个程序和输入判定它是否会停机。

为什么计数器永远不停?

它的规则永远不会通向停机状态。它不断在纸带右端给一个二进制数加 1,然后走回去,所以这个数永远增长下去。图灵的停机问题表明,没有一种通用方法能对每台机器判断它是否会停机;对这个简单的计数器你一眼就能看出来,但对某些只有六个状态的机器,至今还没有人知道答案。

五状态忙碌海狸怎么能在这里运行 4700 万步?

纸带以一个向两个方向增长的紧凑数组存储,在最快设置下,应用在两次屏幕刷新之间运行数十万步,因此在现代浏览器中整个运行只需几秒钟。图示只记录前 400 步,因为一张 4700 万行的图放不进任何屏幕。

会有数据发送到服务器吗?

不会。程序在你的浏览器中运行,你的程序和输入保存在此浏览器的本地存储中。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

前往编辑器