通过追本溯源我们看到，“停机问题”在图灵1936年的论文中从来没出现过【1】，只是Martin Davis在1958年的书《可计算性与不可解决性》中提出的术语【2】，后来学术界用“停机”取代了“可计算性”【3】，图灵的“判定问题”简化为“停机问题”。

于是，我们问：

- 图灵到底是如何定义“可计算性”的？

- “停机”取代“可计算性”是怎么发生的？

一，图灵是如何定义“可计算性”的？

图灵1936年的论文正如其文章题目所示：On Computable Numbers, with an Application to the Entscheidungsproblem，目的是基于Computable Numbers解决Hilbert提出的Entscheidungsproblem。

图灵否定性回答了Entscheidungsproblem，图灵说：

- 我建议指出，不存在判定函数计算K（注：K指一阶谓词）中的给定公式A是否可证明的通用过程，也就是说，不可能存在机器在提供这些公式中任何一个公式A时，最终会说A是否可以证明。

I propose, therefore, to show that there can be no general process for determining whether a given formula A of the functional calculus K is provable, i.e. that there can be no machine which, supplied with any one A of these formulae, will eventually say whether A is provable.

为此，图灵给出了“存在通用过程判定。。。”这样的“判定问题”的定义。

1，判定问题

图灵说：

- 在本节中，“存在通用过程判定。。。”，这一表述等同于 “有一个机器判定。。。”，这种用法的合理性在于我们能够论证我们对“可计算的”定义是合理的。对于每一个“通用过程”的问题，都可以表示为关于通用过程判定一个给定的整数n是否具有某个属性的问题（例如，G(n)可能表示“n是可满足的’’或者“n是一个可证明公式的Godel表达’’），这相当于计算一个数，如果G(n)为真，此数的第n个数字为1；如果G(n)为假，则此数的第n个数字为0。

The expression ‘‘there is a general process for determining . . .’’ has been used throughout this section as equivalent to ‘‘there is a machine which will determine . . .’’. This usage can be justified if and only if we can justify our definition of “computable’’.For each of these ‘‘general process’’ problems can be expressed as a problem concerning a general process for determining whether a given integer n has a property G(n) [e.g. G(n) might mean ‘‘n is satisfactory’’ or ‘‘n is the Godel representation of a provable formula’’], and this is equivalent to computing a number whose n-th figure is 1 if G(n) is true and 0 if it is false.

“可计算性”指机器的能力，为了给出一个合理的“可计算性”定义，图灵提出“图灵机（computing machine）”，构造性地表达“通用过程”，并将图灵机的计算结果表达为“可计算数（computable number）”。注意：这里的计算结果不是一个实例的计算结果，而是一个问题的所有实例的计算结果。

2，可计算性的“象”：可计算数

图灵说：

- 按照我的定义，一个数是可计算的，如果它的十进制的表达能被机器写下来。According to my definition, a number is computable if its decimal can be written down by a machine.

- 如果一台机器打印两类符号，第一类（称为数字）全是0和1，其它被称为第二类符号，则机器将被称为“计算机器”。If an a-machine prints two kinds of symbols, of which the first kind (called figures) consists entirely of 0 and 1 (the others being called symbols of the second kind), then the machine will be called a computing machine.

- 如果计算机器不再写下第一类有限数目的符号，被称作circular；否则，被称作circle-free。If a computing machine never writes down more than a finite number of symbols of the first kind, it will be called circular. Otherwise it is said to be circle-free.

- 一个序列被说成“可计算的”，如果能够通过一台“circle-free machine”计算而得。一个数是“可计算的”，如果它与由“circle-free machine”计算的数只差一个整数。A sequence is said to be computable if it can be computed by a circle-free machine. A number is computable if it differs by an integer from the number computed by a circle- free machine.

可见，“可计算数”是circle-free machine的直观表达，也就是说，是图灵机的“可计算性”的“象”，表达“可计算性”的整体性和无限性。

二，“可计算数”的消失

“可计算数”作为“红线”贯穿于图灵1936年论文，正如 Charles Petzold在其书The Annotated Turing所说【4】：

- 尽管解决Entscheidungsproblem确实是图灵写这篇文章的动机，但是这篇长篇大论本身讲的却是’可计算数’。在图灵的定义中，可计算数就是可以使用机器计算的数。论文前面60%的内容都是对可计算数的探索。Although the  Entscheidungsproblem  was certainly the motivation  for Turing's  paper, the bulk of the paper itself is really about computable numbers. In Turing's definition, these are numbers that can be calculated by a machine. Turing's exploration of computable numbers accounts for the first 60 percent of the paper.

然而，人们采纳和开发了“图灵机”，成就了如今的计算机科学，却让“可计算数”从如今的计算机理论中消失了。那么，“可计算数”为什么会消失？是如何消失的？

我们以考拉兹猜想为例来初步考察此议题。

考拉兹猜想是指，对于每一个正整数，如果它是奇数，则对它乘3再加1，如果它是偶数，则对它除以2，如此循环，最终都能够得到1【5】。

考拉兹序列定义本身可以表达为递归函数f(n)：

f(n) = 1 (n=1)
f(n) = f(n/2) (n is pair)
f(n) = f(3n+1) (n is impair)

考拉兹猜想的真正含义是对递归函数 f(n)（对应的图灵机）的可计算性的判断。

现在，让我们从“停机问题”的角度和图灵的“判定问题”的角度来看考拉兹猜想。

1, 从“停机问题”的角度

考拉兹猜想：判断对应于递归函数 f(n)的图灵机对于任意给定的正整数n是否停机？

2，从“判定问题”的角度

考拉兹猜想：判断对应于递归函数 f(n)的图灵机能否写下“可计算数”：f(1)f(2)f(3)f(4)f(5)f(6)… = 111111…，或者说，图灵机是否circle-free？

从“停机问题”的角度看考拉兹猜想，是通过枚举个体来判断递归函数 f(n)的可计算性，然而可计算性蕴含无穷，无法通过枚举达到对可计算性的判断。事实上，到2020年，已枚举正整数到2^68，也仍未有找到例外的情况，但是这并不能够证明对于任何大小的数，这猜想都能成立。

而从“判定问题”的角度看考拉兹猜想，是希望对作为整体的正整数的性质进行深入挖掘达到对可计算性的判断，这正是考拉兹猜想的真正意义。

由此可见，正是在“停机问题”的定义中，可计算数被取消了，这导致图灵机可计算性的判断消失了，从证明的角度，证明有效性的判断消失了。

或许我们看到了，“一只蝴蝶在巴西轻拍翅膀，可以导致一个月后德克萨斯州的一场龙卷风”，。。。

参考文献：

【1】Turing, A. M. (1937). "On Computable Numbers, with an Application to the Entscheidungsproblem". 

https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

【2】Martin Davis (1958). Computability and Unsolvability. New York: McGraw-Hill.

【3】B. Jack. Copeland, The EssentialTuring, 2004.

http://www.cse.chalmers.se/~aikmitr/papers/Turing.pdf

【4】Perzold Charles, The Annotated Turing - A Guided Tour Through Alan Turing's Historic Paper On Computability And The Turing Machine

https://github.com/pengbo-learn/books/blob/master/The%20Annotated%20Turing%20(Petzold-2008).pdf

【5】https://en.wikipedia.org/wiki/Collatz_conjecture