首页 >> 专题:图灵 >> 学科 >> 数学 >> 文章

在图灵诞辰100周年之际,献给这位伟大的开拓者。

计算无处不在。

走进一个机房,在服务器排成的一道道墙之间,听着风扇的鼓噪,似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘,到今天的计算机,我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多,甚至超越了它们的制造者。上个世纪末,深蓝凭借前所未有的搜索和判断棋局的能力,成为第一台战胜人类国际象棋世界冠军的计算机,但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识;而仅仅十余年后,Watson却已经能凭借自己的算法,先“理解”问题,然后有的放矢地在海量的数据库中寻找关联的答案。长此以往,工具将必在更多的方面超越它的制造者。而这一切,都来源于越来越精巧的计算。

计算似乎无所不能,宛如新的上帝。但即使是这位“上帝”,也逃不脱逻辑设定的界限。

第一位发现这一点的,便是图灵。

计算的极限》系列

所有机器的机器

图灵机非常简单,只要明白了它的运作过程,任何一个受过足够训练的计算机系本科生都可以写出一个模拟图灵机运行的程序。只消输入状态转移表和纸带的输入内容,程序就可以一步一步模拟相应的图灵机在纸带上爬来爬去的过程。对于一些熟悉图形编程的程序员来说,做个模拟动画也问题不大。即使不用计算机,靠人手一步步操作,也是一件小孩子也能完成的事。图灵机就是这么简单的一种机器。

虽然看上去简单,但实际上图灵机能做的事情远远超出一般的想象。只要有足够长的纸带和足够好的耐心,今天的电脑能做的计算,一台精心设计的图灵机也能完成。诀窍在于,电脑中的电路是有限的,电路的状态也是有限的,我们可以用图灵机去模拟电脑中的电路状态。只要有足够长的纸带,那就可以模拟出足够大的寄存器、内存和硬盘;而CPU中的电路,虽然所有可能的状态极其多,但终究是有限的,可以用图灵机模拟,虽然这台图灵机的状态转移表将会有着令人头痛的大小,以及令人偏头痛的复杂程度。但是,从原则上来说,用图灵机模拟一台电脑是完全可能的,虽然每次“读写内存”时,读写头都需要花长得令人咋舌的时间在纸带上来回奔波。

也就是说,从原则上来说,只要配备适当的输入和输出设备,以及极其好的耐心,我们完全可以用图灵机上网、玩游戏甚至执行自己写的程序。特别地,存在一台特定的编写程序专用的图灵机T,我们可以在纸带上写程序,将它输入到T,然后T就能执行这个程序。那么,如果我们将方才本科生写的那个可以模拟任意图灵机运行的程序(暂且把它称为程序P),写在纸带上输入到T中,让T去执行的话,原本的机器T就摇身一变,变成了一台可以根据输入的状态转移表来模拟任何一台图灵机的图灵机。

【乐高玩具版图灵机,图片出处:http://www.cs.cmu.edu/】

更精确地说,因为程序P的长度是有限的,我们可以将它直接写进原来机器的状态转移表,得到一台新的机器UTM。UTM会在纸带上读取两样东西:一台图灵机M的状态转移表的二进制编码,以及作为M的初始输入的纸带数据。然后,UTM会根据M的状态转移表和初始输入数据,在纸带上模拟M的运作过程。换言之,UTM是一台可以模拟任何图灵机的图灵机。它是所有机器的机器,所谓的通用图灵机(Universal Turing Machine)。当然,通用图灵机并不是唯一的,只要一台图灵机能完成根据状态转移表模拟任意图灵机的任务,它就是通用图灵机。

【一台通用图灵机,数据具体格式请参见来源:http://rendell-attic.org/gol/utm/utmprog.htm】

通用图灵机的想法,在如今这个计算机泛滥的时代,似乎并不新鲜。但在图灵的1935年,电子计算机甚至仍未问世,机械计算机还只能执行内设的一套指令。即使是Charles Babbage和Ada Lovelace的超越时代的设想,其中执行外部程序的概念也相当含混不清。在这种历史背景下,要归纳出通用图灵机这个概念,本身就需要极为丰富的想象力,而且这种图灵机是否存在,这是个远非显然的问题。而图灵不仅设想到了这个概念,而且正确地判断出它的存在性,这需要何等非凡的直觉!

但单纯的直觉终究不能令人信服,数学家讲究的是逻辑和证明。而要证明通用图灵机的存在,最直接的方法莫过于直接给出一个通用图灵机的实例。这并不简单,如果读者想尝试一下的话,我建议先尝试构造一个能做二进制加法的图灵机。为了降低难度,可以假设纸带上有第三种符号,表示空白,但即使如此,要构造一个能做加法的图灵机,远比想象中的困难。可想而知,通用图灵机的构造肯定更为复杂繁琐。即使是图灵,他在一开始给出的构造也是有问题的,而这些问题甚至在后来的勘误中也没有成功修正。比构造更麻烦的是证明给出的图灵机的确是一台通用图灵机,在图灵解决希尔伯特可判定性问题的论文中,有关通用图灵机的构造和证明占了相当大的篇幅。这部分非常繁复琐碎,而且其中还有错误,如果细细研读的话,绝对有诱发剧烈偏头痛的危险。

幸运的是,无论细节多么复杂,图灵的想法还是被逻辑学家们接受了。一旦领会到图灵机的能力,接受了通用图灵机的构想,再检查几个能完成基本任务的图灵机之后,大部分数学家都会认为通用图灵机的确存在,尽管他们并不一定会细看图灵的详细构造。而现代电子计算机的发展,更是验证了通用图灵机的存在:每一台电脑都相当于一台通用图灵机。

通用图灵机的存在,从侧面说明了图灵机这个计算模型的强大之处:图灵机作为一类机器,其中一个特例就可以模拟整个类别中的任意一台机器,宛如能折射大千世界的一滴水珠。但在这种强大的背后,隐隐也暗藏着不安定的因素。哥德尔不完备性定理告诉我们,有时候越强大的数学理论,因为能表达的概念太多,甚至连理论的命题和证明都能表达,反而会导致不能被证明的真命题的存在。如果一个系统足以描述它自己,那魔法般的自指将是不可避免的。图灵机如此强大,它的其中一台就可以模拟所有图灵机,会不会导致不能用计算来回答的问题存在呢?

很不凑巧,答案是会。

无法计算的问题

在哥德尔不完备性定理的证明中,哥德尔构造了一个描述了本身不可证明性的自指命题,通过这个命题完成了他的证明。要想照葫芦画瓢的话,那些关于图灵机本身的问题,将会是很好的候补。

关于图灵机,最简单的问题是什么呢?回想一下图灵机的运作过程,一台图灵机从初始状态开始,根据纸带上的内容,一边不断变换状态,一边更改纸带的内容,如此往复永无休止,除非它遇上了表示停机的那个状态,才能从这机械的计算过程中跳出,获得静息的安乐。一个自然的问题是:一台图灵机什么时候会停机呢?

更严格地说,会不会停机并不是图灵机本身的属性,它跟纸带的初始输入也有关系。对于同一台图灵机,不同的纸带输入也可能导致不同的结果和行为。比如说,我可以设计一台图灵机,它的任务只有一个:一步一步向右移动,寻找输入中的第一个1。如果输入纸带上全是0的话,那么,这台图灵机自然不会停止;但只要纸带上有一个1,那么它就会停止。所以,真正严谨的问题是:给定一台图灵机M以及一个输入I,如果我们将I输入M,然后让M开始运行,这时M是会不停运转下去,还是会在一段时间后停止?我们将这个问题称为停机问题。

初看起来,停机问题并不难。既然我们有通用图灵机这一强大的武器,那么只需要用它一步步模拟M在输入I上的计算过程就可以了。如果模拟过程在一段时间后停止了,我们当然可以得出“M在输入I上会停止”这个结论。问题是,在模拟过程停止之前,我们不可能知道整个计算过程到底是不会停止,它可能会在3分钟后停止,可能要等上十年八载,更有可能永远都不会停止。换句话说,用模拟的方法,我们只能知道某个程序在某个输入上会停止,但永远不能确定那些不停止的状况。所以说,单纯的模拟是不能解决停机问题的。

实际上,停机问题比我们想象中要复杂得多。

举个例子,我们可以编写一个程序GC,它遍历所有大于等于6的偶数,尝试将这样的偶数分成两个素数的和。如果它遇到一个不能被分解为两个素数之和的偶数,它就停机并输出这个偶数;否则,它就一直运行下去。用现代的工具编写GC这样的程序,对于计算机系的学生最多只能算一次大作业;用图灵机实现的话,也不是什么极端困难的事。然而,GC是否会停止可是牵涉到了哥德巴赫猜想。如果哥德巴赫猜想是正确的,每个大于等于6的偶数都能分解为两个素数之和的话,那么GC自然会一直运行下去,不会停机;如果哥德巴赫猜想是错误的话,必定存在一个最小的反例,它不能分解为两个素数之和,而GC在遇到这个反例时就会停机。也就是说,GC是否永远运行下去,等价于哥德巴赫猜想是否成立。如果我们能判定GC是否会停止,那我们就解决了哥德巴赫猜想。

数学中的很多猜想,比如说3x+1猜想、黎曼猜想等,都可以用类似的方法转化为判断一个程序是否会停止的问题。如果存在一个程序,能判断所有可能的图灵机在所有可能的输入上是否会停止的话,那么只要利用这个程序,我们就能证明一大堆重要的数学猜想。我们可以说,停机问题比所有这些猜想更难更复杂,因为这些困难的数学猜想都不过是一般的停机问题的一个特例。如果停机问题可以被完全解决,我们能写出一个程序来判断任意图灵机是否会停机的话,那么相当多的数学家都要丢饭碗了。

停机问题如此复杂,机械的计算看起来没有足够的力量来完全解决它。停机问题似乎是不可计算的。但要想严格证明这个结论,似乎仍要求助于深藏在图灵机之中,那魔法般的自指。

0
为您推荐

46 Responses to “计算的极限(一):所有机器的机器,与无法计算的问题”

  1. wanzhihui说道:

    停机问题从字面上解释就是一有故障就会停机。

  2. zxceer说道:

    《GEB》..............

  3. 鸵鸟说道:

    我居然坚持看完了,还用百度百科辅助了一下图灵机知识……

  4. ChanneW说道:

    是计算机的极限,不是计算的极限。

  5. SillyDaddy说道:

    看过一遍关于不完备定理的证明,构造真的很神奇!多么奇妙的想象力啊,把似乎不太正式的自指悖论化为一个描述公理系统局限性的证明!

  6. 匿名说道:

    作为一名业内人士,我想说你这篇文章写的狗屁不通。

  7. 皮皮说道:

    直说NP 问题呗,转了一圈不知道说什么。

  8. 100说道:

    期待鸿篇巨制哦。。。。

  9. hannibal说道:

    《数学:确定性的丧失》

  10. jjx01说道:

    現代電子計算機其實就是這樣一種通用杜林機,它能接受一段描述其他杜林機的程序,並運行程序實現該程序所描述的算法。
    http://zh.wikipedia.org/zh-hk/%E5%9B%BE%E7%81%B5%E6%9C%BA

    楼主这篇文章不属于科普,属于科幻……

    • 方弦说道:

      请指教什么地方科幻了。我是根据可计算性理论的基础来写的,没有幻想的成分。

    • TedBond说道:

      我不觉得这是科幻。这是很正统的理论。。。
      不过语言有种。。怎么说呢,为了让大家理解所以抽去了一些复杂的解释,可能会让人觉得玄乎

      • alexsx说道:

        语言表述的确不怎么样,但无任何可以科幻的地方。相反,残忍地现实(图灵还指望能造出更BT的机器)

  11. wb说道:

    计算机是数学概念与现实的匹配结合,我觉得首先要搞明白什么叫计算才能进一步探讨停机问题之类的。我有个想法,如果把宇宙比作计算机的话,它会不会停机呢?某种意义上,宇宙是最完美的计算机,为了得到某个问题的答案而永远运行下去直到停机。

  12. brills说道:

    不知道楼上喷楼主的是啥目的。。。这篇文章对图灵机的介绍很清楚啊。
    不过建议楼主先介绍计算和计算模型,以及计算模型的等价性,这样才能用图灵机来说明"计算的极限"

  13. 大脚说道:

    期待下期,楼主加油。第一次意识到停机问题为什么很重要。不过深层的思想就不是我这样的凡夫俗子能理解的了

  14. Martin说道:

    楼主其实开始的时候可以多提一下Hilbert 提出的判定性问题,也就是是否存在一系列有限的步骤,它能判定任意一个给定的数学命题的真假?
    图灵提出的构想其实就是第一次给出了一个这么一个“机械步骤”的描述,同时通过停机问题(图灵最开始在文章说的其实是,不存在这样的一个 Turing 机,它能读取任意一个 Turing 机的指令集,并判断该 Turing 机是否将会在纸条上打印出至少一个 0 )证明了Hilbert提出的问题的答案是不存在。
    图灵最神的地方在于,他在一个没有计算机的时代,不仅探索了计算能做什么,还告诉了我们计算机不能干什么。
    目前所有的计算模型还木有突破图灵机的。

    • Martin说道:

      额 木有看到楼主写的系列的第零篇,原来楼主已经写过关于可判定性的问题了。。。 我还以为这是第一篇呢 >.<

    • rinehart说道:

      意思是,用一台计算机去准确预测另外一台计算机的所有结果,是不可能的?

  15. Illusiwind说道:

    以前看过,根本不复杂……用调用自己直接否定了……两三句话就说清了。

  16. 明明说道:

    几个月才写一篇啊,博主加油啊!

  17. 大法西说道:

    写得好烂,跟自指有半毛钱关系。

  18. Leave a Reply说道:

    i=2
    机器A运算for循环{
    如果i>1
    则i++
    }
    机器B运算机器A什么时候循环停止。

    好像是个坑啊。是这样么?

  19. J说道:

    按照有限内存、存储空间、和固定计算程序来考虑,计算机无法计算出结果的问题应该存在;但是这个假设本身不合理,如果考虑计算程序本身的不断更新,和硬件的更新,这样这些问题就变得更加复杂。而单纯从理论上说,如果这个结果一定有一个1,而计算过程中这里会不断产生0,但是如果现有计算机模型无法超越这个地方,那么现有的模型是无法计算的。

  20. JF枭龙说道:

    读完此文,我知道我的大脑——这台计算机的计算能力是有限的。我也明确知道他是会停机的!

    • alexsx说道:

      大脑的能力接近无限早已有推测,绝大部分人能动用的“脑力”不超过1/10,你可以想象10x的你是什么概念。人类不缺乏能力,缺乏的是如何运用。

      • jxm说道:

        如果没有记错的话,关于“人脑潜力只发挥了1/10”的说法,是来源于19世纪末20世纪初,现代解剖学发展起来之前,对大脑严重缺乏了解的时代里,一个不严谨且错误的实验推出的错误结论。

        • 偶尔,?说道:

          是啊,我在松鼠会的一篇文章里看到人脑使用接近饱和的观点

  21. 黄某某说道:

    机器会单相思吗?机器会恼羞成怒吗?机器会莫名其妙地悲伤于:“我是谁”吗?
    机器具有情感吗?机器具有捕抓并分析情感的能力吗?

  22. 23hjkl说道:

    表示没有看懂呀!

  23. dds说道:

    图灵机的极限,其实就是人大脑思维的极限,人无法想像1,2,3...n的尽头到底是什么!
    即使耗尽宇宙所有的原子,自然数数列也数不完,说明什么了?我们所在的宇宙不足以表达所有的真理所蕴含的信息!同样道理,因为任何概念、信息都需要用脑细胞载体,人的脑细胞数量有限的,所以人的大脑所能理解和表达的信息,肯定也是有限的!所以人类的思维永远是真理的真子集!而且是非常渺小的一部分!

    • 小严说道:

      这位兄弟和我以前的一个想法的原理是一样的“简单系统无法理解复杂系统” 人类的思维作为绝对真理的子集只能永远无限接近她,不过这也是人类存在的意义和有意思的地方,要是有一天人类发现自己知道真理是什么了,那么。。。

      • alexsx说道:

        以自然数集合为例,以奇数代表正整数,非零偶数代表正整数,能证明自然数集合等价于整数集合,同样道理可以证明其等价于有理数集合。但却不能等价于实数集合。“简单系统无法理解复杂系统”,但对于实数集合,却可以用“有理数集合的子集”这个集合等价。参考《维度:数学漫步》(http://www.dimensions-math.org/),即使简单的系统,适当拓展或者“投射”之后,还是足以解析复杂的系统的,正如我们的视觉是三维(因为无法理解四维视觉,但可以理解二维视觉),但并不妨碍四维空间的研究。

  24. 海豚在赛跑说道:

    楼主能写一下黎曼猜想是如何转换成停机问题的吗?写成伪代码就成
    期待你的回复

    • 钝钝角说道:

      一个一个计算黎曼函数的零点,如果有一个零点的实部不为1/2,就停机

  25. SLR说道:

    图灵机的停机问题是这样反证的:

    如果停机问题有解,即可以判断任意程序会不会停机。

    假设有一个程序X,可以判断一个程序A是否会停机。
    如果A停机,则X运行一段死循环。
    如果A不停机,则X返回结果:A不停机。

    现在让程序X判断程序X自身是否会停机。
    如果X停机,则X运行死循环,X不会停机。X不会停机,则X有返回值,X停机。…………
    所以引起悖论。

    所以停机问题无解。

    所以哥德巴赫猜想还是得靠数学家……我等程序猿还是老老实实当码农吧……QAQ

  26. 小草说道:

    机器运算很废润滑油和冷却水.

  27. 小草说道:

    算术问题最后会遇到概率问题的.
    概率问题最后会遇到测度问题的.

Leave a Reply