正文
后来“所有计算或算法都可以由一台图灵机来执行”的观点便被称为“丘奇-图灵论题”。
按照这个思路,我们来继续深入,是否每一个问题都可判定是否可计算?会不会出现像逻辑中的悖论一样有无法判断的问题?
图灵为了解答这个问题,就设计了这么一个能够模拟所有计算的机器,然后证明了:
这个机器在有限时间内能够执行完毕问题便是可以判定的问题,这个机器无法在有限时间内执行完毕的便是不可以判定的问题。
说到这里,我们来做一个假设,编写一个图灵机一号,它遍历所有大于等于2的偶数,尝试将这样的偶数分成两个质数的和。如果它遇到一个不能被分解为两个质数之和的偶数,它就停机并输出这个偶数;否则,它就一直运行下去。
我们满心希望的设想,如果图灵机可以解决上述的程序,那么不就解决了三大数学难题之一的哥德巴赫猜想?
三五分钟过去了……五年十年过去了……几十年几百年过去了,程序依然没有运行完毕,那么这个问题到底是无法执行完毕呢,还是时间不够还没有执行完毕?
为了解决这个问题,我们构建一个图灵机二号,它的功能是:判断所有的图灵机是否能在有限时间内执行完毕。
这么说来,只要我们能够判断这一个图灵机是否能够执行完毕,就可以判断所有的图灵机是否能够执行完毕。那么我们大胆构思一个“反例”——图灵机三号,它可以判断自身是否能够执行完毕,并做出相反的行为。
那么问题来了,图灵机二号判断图灵机三号是否可以执行完毕的时候就会出矛盾,图灵机三号总是无法被判断到底是否可以执行完毕。逻辑学中宛若魔咒一般的自我指涉问题同样在图灵机中也体现出来。
举一个经典自我指涉的例子,有位理发师说:“我将为所有不给自己理发的人理发”,那么到底这位理发师给不给自己理发便成为了一个无法解决的命题。
“矛盾的自我指
涉”
图灵机二号存在无法判定的图灵机,因此它功能的假设便是不成立的,并没有这么一台图灵机可以判断所有图灵机可以在有限范围内执行完毕。自然图灵机理论无法尽善尽美地判断问题是否都可判定。
这证明图灵机也有无法解决的问题,但是,图灵机的“不完美”通过完备的论证过程证明了不可判定问题的无解,上述这一切的一切最终埋葬了希尔伯特宏伟的数学大厦的计划。
二、图灵机——可计算理论的“副产物”
设想一下,我们在计算乘法的时候:在每个时刻,我们只将注意力集中在一个地方,根据已经读到的信息移动笔尖,在纸上写下符号或数字;而指示我们写什么怎么写的,则是早已背好的九九乘法表,以及简单的加法。
参考维基百科中图灵机的基本思想:
图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程,他把这样的过程看作下列两种简单的动作:
在纸上写上或擦除某个符号;
把注意力从纸的一个位置移动到另一个位置;
而在每个阶段,人要决定下一步的动作,依赖于(a)此人当前所关注的纸上某个位置的符号和(b)此人当前思维的状态。
图灵机的实现结构并不复杂,它有一条无限长的纸带,纸带由方格组成。有一个读写头在纸带上移来移去,读写头连接控制器,控制器内有状态转移表,还有一些固定的程序。在每个时刻,读写头都要从当前纸带上读入一个方格信息,然后结合自己的内部状态查找程序表,根据程序输出信息到纸带方格上,并转换自己的内部状态,然后进行移动。图灵机不断重复上述的步骤,这便是执行的过程。
图灵机理论示意图