1936 年还没有任何计算机。英语里的 computer 指的是一个人：以计算为职业、用铅笔和纸在保险公司、天文台和政府部门里做算术的人。图灵就从这个人出发。他问：一个人在计算时真正在做什么？然后把一切不重要的东西都去掉。

计算的人还剩下什么

图灵在《论可计算数》中的推理，几乎就是一串简化：

  • 纸可以换成一条分成格子的纸带，因为方格纸上的计算可以一格一格地抄到一行上。
  • 每格里放一个符号，取自一张有限的清单：数字、字母、空白。
  • 计算的人每次只看少数几格。看一格就够了：看几格，就是先看一格，再看它旁边那格。
  • 计算的人有一种心理状态，比如“我在做加法”或“我在进位”。这样的状态只有有限多个。
  • 每一步只取决于当前状态和正在读的符号。这一步就是写下一个符号、向左或向右移动一格、改变状态。

剩下的就是一台机器：一条纸带、一个能读能写的头，以及一张规则表。表的每一行说：“在某某状态下，读到某某符号，就写下这个，移到那边，进入某某状态”。

一台加 1 的机器

我们来造一台把二进制数加 1 的机器。手算 $1011+1$ 时，从右往左：最后一个 1 变成 0，“进一”；倒数第二个 1 也变成 0，再进一；接下来的 0 变成 1，计算结束。结果是 $1100$，也就是 $11+1=12$。

机器做的正是这件事，只需要一个状态“加”，外加终止状态“停机”。读写头从最后一位开始：

状态 读到 写下 移动 下一状态
加 1 0 向左 加
加 0 1 不动 停机
加 空白 1 不动 停机

第一行就是进位：把 1 换成 0，继续向左。第二行在遇到 0 时结束计算。第三行处理所有数字都是 1 的情形，比如 $111+1=1000$：读写头走到数字左边的空白处，在那里写下新的 1。

为什么这么简陋？

图灵机看上去简陋得可笑。它不能一次把两个数相加，除了纸带之外没有记忆，每次只走一格。但这种简陋是有意为之。图灵想要一个关于“机械计算”的定义，它要简单到没有人会怀疑一个人能执行它，同时又要普遍到涵盖任何计算。

这一赌注的后一半被称为丘奇–图灵论题：凡是能用机械程序计算的东西，都能用图灵机计算。它不是定理，因为在图灵之前，“机械程序”并不是一个数学概念。它是一个从未被推翻的论题：此后造出的所有计算机，从最简单的到最快的，计算的函数都和图灵机完全相同，只是更快而已。

练习：让机器处理 111

从纸带 $111$ 开始，读写头在最后一个 1 上。第 1 步：读到 1，写 0，向左；纸带是 $110$。第 2 步：读到 1，写 0，向左；纸带是 $100$。第 3 步：读到 1，写 0，向左；纸带是 $000$，读写头在数字前面的空白上。第 4 步：读到空白，写 1，停机。纸带是 $1000$：$7+1=8$，用了 4 步。

练习：要走多少步？

如果一个数最后 $k$ 位都是 1，再前面一位是 0，机器给它加 1 要走多少步？

$k$ 个 1 变成 0，每个一步，再用一步把 0 变成 1，共 $k+1$ 步。对以 0 结尾的偶数，一步就够了。最坏的情况是全由 1 组成的 $n$ 位数：$n+1$ 步。

来源： Alan Turing, “On computable numbers, with an application to the Entscheidungsproblem”, Proceedings of the London Mathematical Society（1936）· Charles Petzold, The Annotated Turing（2008）。

艾伦·图灵的全部主题 · ← 艾伦·图灵的一生 · 停机问题：没有机器能回答的问题 →

图片来源.