在图灵1936年论文第二章，图灵用circle-free来定义“可计算数（Computable sequences and numbers）”，这个定义实际上是由二部份构成的，首先由circle-free来定义“可计算序列”，进一步由“可计算序列”定义“可计算数”。 按照图灵的定义： A sequence is said to be computable if it can be computed by a circle-free machine. 一个序列被说成“可计算的”，如果能够通过一台“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”计算的数只差一个整数。 我们以图灵所举的一个可计算序列：010101...为例来理解circle-free与“可计算序例”与“可计算数”的定义关系。图灵的意思是：一个可计算的数（A number is computable）只与circle-free计算的数（the number computed by a circle-free machine）相差一个整数，这就是指“小数”。因此，可计算序列“010101...”对应一个（可计算的）二进制无限循环小数“.010101...”，就是十进制小数：2^(-2)+2^(-4)+2^(－6)＋ ...，即0.333...。 由这个实例的递进定义来理解图灵的“可计算数”是理解图灵论文的关键之一。无限循环小数表达了机器意义的“可计算数”的最大能力，这个最大能力是由（不停机的）circle－free的机器过程实现的。得到确定性的结果而“停机”只是circle-free的特殊情况，因此图灵并不是想由机器直接写出一个可计算数（而停机），“停机”是对已经存在的一台具体可计算机器而言，这正是把“停机问题”顶替“判定问题”所发生的对图灵1936年论文误读的原因。所以图灵并不关心“停机”，图灵所做的是揭示机器自身的机械步骤过程的算法性质，即机器化的“算法”——图灵机。 因此这和一般人观念中的机器的“可计算性”完全不同，通常认为，一台计算机器如果不输出最终结果而总是处于计算之中，则这台机器（算法）就进入了“死循环”，被认为是没有用的。产生这种差别的原因在于普通人只是把计算机当作一台现成的计算工具使用，而图灵是计算机器的建造师，他只有首先保证机器具有无限的运行能力（circle-free），然后才有可能让机器“停机”而得到某个解。
计算机理论中现在流行的一个最基本术语就是“停机问题”（the Halting Problem），其基本意思是：判断任意一个程序是否会在有限的时间之内结束运行的问题。这种解释一开始就隐含了一个主体上的混乱，“判断者”是谁？ 这个问题实质源于数学和逻辑基本理论，也就是著名的希尔伯特第十问题（Hilbert's tenth problem）。1900年，德国数学家希尔伯特(David Hilbert 1862─1943)在巴黎第二届国际数学家大会上作了《数学问题》的著名讲演，提出了数学理论中的23个最困难的问题，其中的第10个问题是这样说的: Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers. 注意希尔伯特的用词，作为一个大数学家和形式主义代表，他并没有用“数学方法”、“函数”或“形式方法”这样现成的术语，而是问：能否 “发明一种过程”（或“设计一种方法”）（To devise a process）去“判定”（determine）任何一个丢番图方程问题是否可解？因此，希尔伯特第十问题隐含着数学家的一种哲学上的反思，面对任何可定义的数学问题，数学的“确定性”能力究竟为何？用今天的表达方式就是：存在或不存在对任何可定义的数学问题可解的判定方法？ 图灵理解了希尔伯特第十问题的真正要求，图灵具有对复杂机械过程的强大直觉能力（因此后来也成为了一个密码专家），他把人的进行计算的过程完全以符号化的形式表达出来，成为一种算法的机械模型——“图灵机”，图灵机最大的意义就是展示了算法的机械过程，虽然数学和图灵机都使用符号，但它们的组织性质完全不同，数学是纯粹的形式关系，算法则一定是实时（the Actual Time）过程，这样就把数学意义上的“可计算的”函数表达为“可计算的”机械过程，揭示了算法的“能行性”本质，在数学形式之外表达了算法关系，凸现了“算法”的特殊性质和地位，所以“丘奇－图灵论题”说，“能行可计算的”就是图灵机可计算的。 借助于对算法过程的构造性研究，图灵得到了对希尔伯特第十问题的结论，但不是通过一台机器的计算而得到一个确定性的答案，图灵只是肯定，这样的机器是设计不出来的，用今天的表达方式就是，不存在判定任何可定义的数学问题可解的方法。因此图灵是确定地否定了希尔伯特第十问题。希尔伯特第十问题的提出和图灵的否定性回答，现在统称为“判定问题”（Entscheidungsproblem）。 “判定问题”的提出和回答方式之间的关系和性质充满了复杂性，深刻地涉及对数学、逻辑、算法的本质和它们的关系的理解，有些已经成为了哲学上的困难问题，因此人们不断地从各种角度来解释，其中一个广泛的理解角度就是“悖论”方式，即众所周知的“停机问题”（the Halting Problem）。然而，图灵并没有在他的论文中提出“停机”这个术语，此术语可能来源于D.戴维斯，但戴维斯自己也没有确认： Although Turing defined no instruction that would ever halt the machine, the problem that Turing is now attacking is studied more in the variation known as the Halting Problem. (The term originated in Martin Davis's 1958 book Computability and Unsolvability. 32) Can we define a Turing Machine that will determine whether another Turing Machine will either halt or go on forever? If we substitute the idea of circularity for halting, it's a similar problem. Can one Turing machine analyze another Turing Machine and determine its ultimate fate?－Charle Petzold’s “The Annotated Turing “停机问题”中的“停机”就是指计算机输出确定的答案而停机，注意，这个具有“停机”能力的机器就是能行可计算的机器，所以这里的“停机”并没有图灵机的工作中（circle－free）的那种特殊意义（ http://blog.sciencenet.cn/home.php?mod=spaceuid=2322490do=blogid=993665 ），“停机问题”通俗的理解，只是问计算机能不能计算所有的问题，从常识上可以理解，一方面，所有能行可计算的算法都是可以得到确定性的答案而停机的，另一方面，不存在可以解决所有问题的确定性算法，就是说这是两回事，并不冲突。 但“停机问题”对“判定问题”的替代却是采用逻辑悖论的方式设计的，就是设计一台计算机的自我指涉，即让一台计算机去判断自己能否得到正确的答案而停机，这实质只是把自指悖论变成了机器形式，最多只是解释了“停机问题”具有悖论性质，与图灵对希尔伯特问题的解决完全不同。图灵的解决是确定性的判断而不是归结到悖论——“‘判定问题’不可判断”，即“不存在对任何可定义的数学问题的判定方法”。 由于把“circle－free”换成了“停机”，就把“判定问题”偷换成了“停机问题”，如此就隐含了“所有的算法都具有不可判定的性质”，这是一个观念上的大错误，如果一台计算机或算法不能肯定自己，就推翻了“可计算性”这个概念本身，“‘停机问题’不可判定”意味着——“可计算的”机器不能肯定自己的“可计算性”！就是说，“停机问题”这种悖论式的解释“判定问题”的代价，只是将问题推进到一个更深的缠绕层次。 希尔伯特第十问题是由丢番图方程问题表达的，在数学界存在一种较狭义的理解方式，认为希尔伯特第十问题是1970年由马季亚谢维奇(Matijacevic, Y.)在普特南(Putnam,H. )、鲁宾孙(Robinson, J. B.)和戴维斯( Davis , M. D.)等人工作的基础上否定地解决了的，他们的工作证明了一个谓词是递归可枚举的，当且仅当该谓词是丢番图谓词，而递归可枚举集是不可判定的，故希尔伯特第十问题是不可解的。（参见博文：什么是“判定问题”？（4）－丢番图方程的两难问题， http://blog.sciencenet.cn/home.php?mod=spaceuid=2322490do=blogquickforward=1id=958109 ） 因此，马季亚谢维奇等人的工作只是成功地将丢番图方程问题归结到递归可枚举集，但递归可枚举集是不可判定的这个性质正是建立在“判定问题”的基础上，如果没有这个基础，马季亚谢维奇等人的工作也就没有意义。 希尔伯特第十问题的意义不仅仅是一个数学问题，也反映了数学和逻辑学基本问题后面一直存在着的哲学上的困难，所谓“数学的三次危机”等认识，不仅是数学上的，也是人类的知识、信息以及今天的人工智能所摆脱不了的本质性，在最终的意义上都源于人的不确定性本质，人就是在对自己的本质的不断深入认识中得到自己的存在意义的。
“判定问题 ” （德语entscheidungsproblem，英语decision problem）是可计算性理论的核心问题，由希尔伯特于1900年在巴黎第二届国际数学家大会上提出：是否存在这样一种确定的方法，在理论上可适用于任何假设，并且能够保证对无论是否正确的假设都能给出一个正确的结果？（ https://zh.wikipedia.org/wiki/決定性問題 ）。图灵于1936年在他那篇著名的论文“论可计算数及其在判定问题上的应用”中给予了否定的回答。 人们一般将此“判定问题”表述为“停机问题”：是否存在一个图灵机能判断任一图灵机停机？首先假设存在一个能够判断任一图灵机停机的图灵机，然后利用康托尔的对角线法构造出一个类似于“我在撒谎”的悖论，于是通过反证法证明了不存在这样的万能图灵机，即“停机问题”是不可判断的，从而给出了希尔伯特的“判定问题”的否定回答。 然而，“停机问题”的本质经常未得到人们的正确认识，比如维基网（ https://zh.wikipedia.org/wiki/停机问题 ）将“停机问题”理解成： 通俗地说，停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：给定一个程序P和输入w，程序P在输入w下是否能够最终停止。 实质上，“判断任一图灵机（程序）停机（停止）”与“判断是否存在一个图灵机能判断任一图灵机停机”，是二个层次完全不同的问题，前者是暗中肯定了有一台图灵机用以判断别的机器是否能停机，这是“真、假”判断；后者是质疑是否存在这样一台判断机去判断所有机器能否停机；前者是“判断”，而后者是对“判断”的“判断”。“停机问题”的证明正是具体化了这二个不同的层次，然后又将它们同一化造成“自我否定”，以此来证明不存在一个能判断任一图灵机停机的图灵机。 正确理解“停机问题”关键在于，“停机问题不可判断”这个结论等同于逻辑上的悖论——不可说，这是由人做出的结论，不是直接由机器给出的答案。 “停机问题”揭示的是不存在一个能判断任一图灵机停机的图灵机，这与逻辑悖论相同，但这个问题并没有因此而被抹杀，“停机问题不可判断”只是表明：对停机问题不存在确定性的算法，这是对机器能力而言，但对人的能力而言，这个问题既不能肯定也不能否定，正是在此意义上，“停机问题”成为了“不确定性问题（Nondeterministic Problem，NP）”，与确定性的“可计算问题”有本质的区别。 但是我们还要指出，“停机”在这里的意义是得到确定性的结果，与图灵论文中的“可计算数”相同，但对于“无限循环小数”这样的“可计算数”来说，正是机器不“停 机 ”才能计算这个循环小数：A sequence is said to be computable if it can be computed by a circle-free machine （这个circle-free 可以指机器处在不停止、但没有进入“死循环”的计算过程中），我们在这个特定的机器状态意义上说，机器状态是可以表示“不确定性”的意义的，但这与以前博文中所论的NDTM（Nondeterministic Turing Machine）完全不同。指出这一点有助于对NP（Nondeterministic Problem）的深入理解。 参考文献： A. M. Turing, On Computability Numbers, with an Application to the Entscheidungsproblem. https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
上回我们看到，停机问题这个良定义的问题，不能由图灵机来解决。那么像停机问题这样的图灵机不可解或者说不可计算的问题，究竟是有很多呢，还是只是个别呢？ 其实，有另外一种论证，可以说明绝大多数将自然数映射到自然数的函数是图灵机不可计算的。这个论证的思路是把一切可能的图灵机进行点数，把它们排个队。 首先，请注意图灵机的有限性。这个 我们在讨论通用性的时候 说过。除了带子之外，图灵机所有其他方面都是有限的。记号的种类是有限的，控制器的可能状态数是有限的，读写头的可能移动是有限的。这样一来，任何特定的图灵机，其指令表中包含的五元组的数目也就自然是有限的。这就意味着，我们可以把图灵机们按照它们各自的指令表来排队。比如，把指令表视为一个句子，每个五元组视为一个单词，同时将组成五元组的记号种类、控制器状态和读写头移动方向视为字母并规定其字母表顺序。这样，我们就可以像把英语句子按字母顺序排序那样来给图灵机排序了。由此我们可以说明所有可能图灵机的集合是可数（无穷）的。因此，可能图灵机的数目和自然数一样多。（更准确地说，图灵机集合的基数和自然数集合的基数相同。） 另一方面，将自然数映射自然数的函数个数是不可数（无穷）的，远远超过我们用来给图灵机点数的自然数集合的大小，而至少有［0 1］区间里的实数那么多个。（因为这种自然数到自然数映射的集合至少有自然数的幂集那么大。） 由此可见，从自然数到自然数的函数个数比可能的图灵机的个数要多很多。（在集合的基数序列里要整整高出一阶。）这就意味着必然存在着图灵机不可计算的函数；而且，事实上有无穷不可数那么多的函数是图灵机所不可计算的。跟不可计算函数的数目比起来，可能图灵机的数目相对而言小到可以忽略不计。所谓停机问题只是这些不可计算函数中的一个有趣的例子罢了。 需要注意的是这里所谓不可解，是相对于图灵机而言的，所以也叫图灵机不可计算或者图灵不可计算。这里的论证并没有说明其他的跟图灵机不同的机制也不能解决图灵机的停机问题，虽然这些别的机制也可能有自己的停机问题。 这里的讨论表明，存在这数学上良定义的函数，其映射是图灵机这种机制所不能实现的。正如哥德尔曾经指出的，如停机问题这样的不可计算函数的存在，表明了语义是超越纯粹的机制的，就是说哪怕在自然数算术这样一个很简单的领域里，数学语义上可以严格一贯地定义的映射也不能为纯粹机制加以有效执行。 在过去六七十年乃至今天，有不少人由此得出结论说，既然我们一方面能够理解和把握停机问题这类情况，尤其是哥德尔句子为真这样的事实，而机器却不能机械地解决停机问题或者推导出哥德尔句子，因此人的理解或者直觉能力不是机器能够实现的，完全的人工智能也就是不可能的。这个推断成不成立，咱们以后会专门详细讨论。 不过，图灵机并非唯一的计算模型。前面提到过丘奇对不可判定性的工作，他用的模型叫做演算，这个是后来Lisp程序设计语言的基础。此外，还有由克林尼（Stephen Kleene）在哥德尔工作基础上加以整理推广的递归函数（recursive functions）、波斯特（Emil Post）的波斯特产生式系统（Post production systems）等等。再后来，有戴维斯（Martin Davis）提出的S编程语言。这一模型对于程序员来讲会比较直观。它非常简单，只有三种指令，分别是加1、减1和条件转移： （1）x i = x i + 1 （2）x i = x i 1 （3）if x i = 0 goto LABEL 这个模型下的程序由上述三种类型的指令行构成。每行有仅属于自己的唯一标记（LABEL），可以用在转移（goto）语句里面来指明转移的目标。这个模型假定了存在很多下标变量x i 可用，它们起的作用是存储器，跟图灵机的带子相当。不过，这个可是随机存储器（RAM）！您要有兴趣的话，可以试着用S编程语言来写点小程序。（提示：您可以先考虑如何把一个下标变量拷贝到另一个下标变量，由此构造出赋值语句来。） 在1930年代的短短几年里面递归函数、演算、图灵机等等先后被提出，人们很快证明了他们之间的任何一对都是等价的。所谓等价，在这里的意思就是说一个模型能做的，另一个模型也都能做；反之亦然。 当然，要谈两个模型之间的等价性，就必须有一定的准则来界定各个模型要做的事情。比如说，你不能要求演算去做图灵机能做的移动读写头，因为演算里根本就没有读写头；此外，你也不能要求任何这些模型给你炒个小菜或者打个华尔兹的拍子啥的。在这里，等价性证明采用的准则很简单，就是看这些模型如何实现自然数到自然数的函数映射。所谓等价的意思就是说，对于任何一个自然数到自然数的函数映射，如果一个模型能够实现此映射，那么另一个模型也能实现该映射；反之亦然。因为我们前面看到，图灵机并不能实现全部这些映射，所以这个准则并不是空洞的，因为有可能存在某个映射是图灵机不能做的，演算可以做；或者说反过来。 值得注意的是，这里的等价关系是相当的行为主义的，它只关心输入和输出──如果有输出的话──两端的符合，其他任何方面都不管。模型里面具体如何运作，算法是什么，运作有多快，需要多少存储等等全都无所谓，经典计算和量子计算之间的区别也无所谓。 不管怎么样，既然这些特定的模型一个个地被证明为相互等价，人们就在想：嘿，咱们是不是抓住了一点什么具有一般性的东东呢？是不是说所有这些模型共同指向了直观上的计算或者可计算概念的本质呢？由此就有了著名的丘奇-图灵论题（Church-Turing thesis）： 任何直观上可计算的函数都可以由某个图灵机来计算。 这个说法之所以叫做论题（thesis）而不是定理（theorem），是因为直观上可计算这个概念是没法形式化，所以也就不可能有形式化的证明。直观上可计算，其大体意思恐怕是说按照某种确定的过程来一步一步地、机械而有效地把输入变形到输出。与其他等价的模型相比，图灵机有个特点，就是它一方面把这个思想给形式化了，另一方面又保留了机器之为机器的直观性。由此，我们可以理解为什么哥德尔会认为，是图灵机这个模型的提出，真正把有效可计算性这个概念给抓住了。 丘奇-图灵论题提出至今有70多年的了。它也不是没有人反对，今天也还有人在尝试提出与图灵机不等价的，计算能力超越图灵机的模型。不过，迄今为止还没有任何被断言为超越图灵机的计算模型被普遍接受为合理的、符合直观可计算观念的模型。所以，今天的主流观点依然认为这一论题是对的，以图灵机为代表的这批计算模型确实抓住了直观上的可计算性。
标签: 停机问题
