停机问题

停机问题(The Halting Problem)是逻辑数学中可计算性理论的一个问题。通俗地说,停机问题就是判断任意一个程序,是否会在有限的时间之内结束运行的问题。该问题等价于如下的判定问题:给定一个程序P和输入w,程序P在输入w下是否能够最终停止。

艾伦·图灵在1936年用对角论证法证明了,不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义,这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。

用数学语言描述,则其本质问题为: 给定一个图灵机T,和一个任意语言集合S,是否T会最终停机于每一个。其意义相同于可确定语言。显然任意有限 S 是可判定性的,可数的(countable)S 也是可停机的。

如果这个问题可以在有限的时间之内解决,则有一个程序判断其本身是否会停机并做出相反的行为,这时候显然不管停机问题的结果是什么都不会符合要求。所以这是一个不可解的问题。停机问题本质是一阶逻辑的不自恰性和不完备性。类似的命题有理发师悖论、全能悖论等。

严谨的解释

假设存在一个程序,其有两个输入值 iipp ,其中 pp 为一段程序、 ii 为输入 pp 的数据,并对于任意 pp 与任意 iiHH会在有限步内给出结果,结果仅为 1100

假设存在满足上面要求的 H(p,i)H(p, i),那么我们可以构造一个特殊的程序 K(i)K(i)
defK(i):def K(i):
对于任意的输入 ii 来说,K(i)K(i) 会先调用 H(K,i)H(K, i),如果 H(K,i)H(K, i) 的返回值为 1(也就是说HH判断K(i)K(i)停机),则 K(i)K(i) 接下来执行一段死循环代码,从而不会在有限步内停机;
反之,如果 如果 H(K,i)H(K, i) 的返回值为 0(也就是说HH判断K(i)K(i)不停机),则 K(i)K(i) 立即结束,也即是在有限步内停机。

这时候,很显然,程序 K(i)K(i) 是无论如何也矛盾的(如果H(K,i)H(K, i)判定为不停机的话K(i)K(i)会立即停机,从而与上一步中H(K,i)H(K, i)的判定结果相矛盾,反之亦然)。

所以说,我们之前的假设是错的,满足上述要求的 HH 是无法构造出来的。

哲学“自指”问题

说谎者悖论

说谎者悖论 又叫谎言者悖论。公元前六世纪,克里特人的哲学家埃庇米尼得斯(Epimenides):“所有克里特人都说谎”,这就是这个著名悖论的来源。

这句话之所以有名在于它没有答案。因为如果埃庇米尼得斯所言为真,但这跟先前假设此言为真相矛盾;又假设此言为假,那么也就是说不是所有克里特人都说谎,自己也是克里特人的埃庇米尼得斯就不一定是在说谎,就是说这句话可能是真的,但如果这句话是真的,又会产生矛盾。因此这句话是无解的。

偶然看到这个问题发现不对,因为存在这样一种情况,“有些克里特人说谎,有的不说谎”。“如果埃庇米尼得斯所言为真,那么克里特人就全都是说谎者,身为克里特人之一的埃庇米尼得斯自然也不例外,于是他所说的这句话应为谎言,但这跟先前假设此言为真相矛盾”没有问题,于是接着假设这句话是假的,但是并没有矛盾产生。

“所有克里特人都说谎。”的否定是“存在至少一个克里特人不说谎”,由于克里特按照常理来说不只有一个人,虽然埃庇米尼得斯说谎,但是存在至少一个人不说谎还是可能的,这并不产生矛盾。可以构造这样一个命题:“我在说谎。”这就是一个自我指涉引发的悖论。

罗素

问题并不简单:哲学家罗素曾经认真地思考过这个悖论,并试图找到解决的办法。他在《我的哲学的发展》第七章《数学原理》里说道:“自亚里士多德以来,无论哪一个学派的逻辑学家,从他们所公认的前提中似乎都可以推出一些矛盾来。这表明有些东西是有毛病的,但是指不出纠正的方法是什么。在1903年的春季,其中一种矛盾的发现把我正在享受的那种逻辑蜜月打断了。”

他说:谎言者悖论最简单地勾画出了他发现的那个矛盾:“那个说谎的人说:‘不论我说什么都是假的’。事实上,这就是他所说的一句话,但是这句话是指他所说的话的总体。只是把这句话包括在那个总体之中的时候才产生一个悖论。”(同上)

罗素试图用命题分层的办法来解决:“第一级命题我们可以说就是不涉及命题总体的那些命题;第二级命题就是涉及第一级命题的总体的那些命题;其余仿此,以至无穷。”但是这一方法并没有取得成效。“1903年和1904年这一整个时期,我差不多完全是致力于这一件事,但是毫不成功。”

通俗例子

  • 绝对没有绝对的事情。
  • 从前有家饭店,只卖包子和馒头,这时候假设存在一个聪明的侍者,这个侍者可以判断任何一个前来点餐的客人要点什么菜,这时候有个腹黑的家伙说:“如果你判断我要点包子,那我就点馒头;如果你判断我点馒头,那我就吃包子。”所以这样的侍者是不存在的。

相关阅读

《数学原理》尝试说明,整个纯粹的数学是在纯逻辑的前提下推导出来的,并且使用逻辑术语说明概念,回避自然语言的歧意。书的序言里说:“发表一本包含那么多未曾解决的争论的书。”从数学基础的逻辑上彻底地解决这个悖论并不容易。接下来罗素指出,在一切逻辑的悖论里都有一种“反身的自指”,就是说,“它包含讲那个总体的某种东西,而这种东西又是总体中的一份子。”

但是在集合论里,问题并不这么简单。事实上,我们要讨论这个悖论,问“这句话是不是正确的”是没有意义的。我们充其量只能问:"这个模型是否满足人类逻辑?"
很明显,这句话是对它本身的描述,因此他是一个模型。而这个模型的建立,需要在以下逻辑上:
"如果A,那么非A。’(这句话在经典逻辑里,是正确的,但在直觉主义逻辑里,并不一定。可阅读另一篇文章,命题逻辑,其中讲到经典逻辑与直觉主义逻辑的不同

但这种逻辑不被人类逻辑所允许,换言之,这个模型无法在人类逻辑中建立(或者说,它与人类逻辑不协调)也就是说:这句话在本质上就不存在于人类模型中,因此,讨论“它是否正确”是无意义的。

参考笔记

[1]康托尔、哥德尔、图灵——永恒的金色对角线(刘未鹏)