首页 >> 数学 >> 计算机科学 >> 文章

计算无处不在。

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

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

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

计算的极限》系列

图灵的哑谜

说到底,谕示是什么呢?我们来看看图灵在他的博士论文中的定义:

“假定我们拥有某种解决数论问题的未知方法;比如说某种谕示。我们不深入这个谕示的本质,除了它不可能是一台机器这一点。通过谕示的帮助,我们可以构筑一种新的机器(叫做o-机),它的基本过程之一就是解决某个给定的数论问题。”

在这里,图灵说的“数论问题”,其实是指描述自然数的一类特殊的逻辑命题,用现在的术语来说叫\( \Pi^0_1 \)命题。“数论问题”只是图灵取的一个名字,与真正的数论研究关系不大。

图灵的这段文字其实定义了一种新的图灵机,图灵把它叫做“o-机”,而它的现代术语叫“谕示机”。一台谕示机就是一台有点特别的图灵机,仅仅多了一个新功能,就是能“免费”得到某一个特定的判定问题的答复。比如说,一个带有素数判定谕示的谕示机,除了能做普通图灵机能做的一切事情以外,还能瞬间判定纸带上写的某个自然数是否素数,而不需要实际去计算。

那么,是不是谕示机就一定比普通的图灵机强大呢?就像两位学生参加同一场范围不定的不限时开卷考试,他们的能力与掌握的知识相同,一位学生带了一本参考书,而另一位则什么资料都没带,带了书的那位是不是一定比另一位更有优势呢?

闭卷考试开卷考试

这就要看参考书到底是什么了。如果两位学生都懂参考书中的所有内容的话,那么参考书并不会带来什么优势,可能带书的学生会答得快一些,但既然考试不限时,没带书的学生多用点时间也总能答出来。但如果参考书是两位学生都没有见过的内容的话,带了书的学生自然略有优势。如果考试题目中包含了参考书中的一些内容,而两位学生本来都不懂的话,带了书的可以翻书回答,没带书的就只能干瞪眼了。

同样,在我们比较一台谕示机与一般的图灵机的能力时,也要看看谕示回答的具体问题是什么。如果谕示解决的问题本来就是可计算的话,一般的图灵机即使没有谕示,也能多花点时间把答案计算出来,这时谕示机毫无优势;但如果谕示能解决一个不可计算的问题,比如说停机问题的话,谕示机显然能解决同样的问题,而一般的图灵机则无法解决,因为问题本身是不可计算的,这时谕示机的能力显然比没有谕示的图灵机要强。

所以说,谕示机的力量蕴含在它拥有的谕示能回答的问题,而谕示机中谕示的具体问题可以是任意的。我们可以考虑带有停机问题谕示的谕示机,如果这台机器的纸带上写着一台普通图灵机的“代码”以及输入,那么它不需要计算就能可以瞬间知道,这台普通图灵机遇到指示的输入时到底会不会停机。所以,对于谕示机而言,它不受普通图灵机的可计算性的限制,能够“计算”超越机械计算本身极限的问题。当然,这也意味着,对于一个不可计算的问题,我们不可能实际地建造一台谕示机。

也就是说,谕示机这个概念,只是一个单纯的数学概念,仅仅用于数学上的探索,而不可能实实在在地出现在我们面前。图灵当然也意识到这一点,在他的论文中,也确切声明谕示机并不属于机械计算的范畴。也许这就是图灵使用“谕示”这个名字的原因。“谕示”的原文oracle,来自拉丁语中的oraculum,从orare加上物化工具后缀-oculo得到。orare的意思是“祈求”或者“祷告”,而oracle的意思就是“神的宣布”,也就是神谕。图灵是一位无神论者,他相信神是不存在的,所以神谕当然也不存在。用它来命名一台不可能实现的机器,实在是再适合不过了。

丢勒《祈祷的手》,来自Wikipedia

那么,在论文中图灵用谕示机证明了什么呢?

图灵考虑的是一类特殊的谕示机,其中的谕示能回答一切“数论问题”,也就是说,这个谕示能判断任意的“数论问题”是否为真。但除此之外,它就是一台普通的图灵机,于是我们也能考虑关于它的停机问题:给定一台这样的谕示机的代码(不包含谕示本身),以及一个输入,这台谕示机在这个输入上会不会停机呢?

对于普通的图灵机而言,停机问题是不可判定的,这早已被证明。而图灵发现,即使将证明中的所有“图灵机”三个字都换成“带有‘数论问题’谕示的谕示机”,其他部分一字不易,证明依然成立!也就是说,就像普通图灵机不能解决关于自身的停机问题,谕示机也不能解决关于自身的停机问题,无论它的谕示有多么强大。

所以,图灵的结论是,存在带有“数论问题”谕示的谕示机也不能解决的问题,但既然这种谕示机能解决所有“数论问题”,所以不能归结为“数论问题”形式的数学问题是存在的。

这个结论,未免大材小用。不需引入谕示机,以图灵的才智,也有办法证明相同的结论。在整篇论文中,谕示机这个概念只出现在第四章,专门用于探讨“数论问题”的局限性,而这一章基本与论文全体独立,即使删去也不影响结论。用不必要的工具,证明了不必要的结论,图灵到底在想什么,其中是否别有深意?为什么要加上这一章?这些问题的答案,只有图灵自己知道。

幸而,仅仅5年后的1944年,就有人破解了谕示机的哑谜。

谕示机的谕示

让我们回到开卷考试的比喻。在日常生活中,范围不定的考试毕竟少见,多数考试的范围都是相对明确的某个科目,比如说高考语文、数学分析、考研英语、公务员考试中的申论等等。我们经常说,某某省的高考数学难度比某某省的要大,或者高等数学比数学分析要简单。那么,当我们说“某门科目的考试比另一门简单”的时候,我们到底在说什么?

我们尝试一下用数学家的思路来解决问题。

首先,我们希望比较不同的科目,给它们排个顺序。我们潜意识认为,每个科目都有它固有的难度。如果科目A比科目B要难,科目B比科目C要难,那么科目A比科目C要难。也就是说,这种顺序是有“传递性”的。于是,从数学的角度来看,我们要考察的是不同的考试之间的所谓“序关系”,也就是说它们之间两两的难度顺序关系。

其次,我们也发现并不是所有的科目都能相互比较。比如说高考理科数学和对外汉语,高三理科生对前者可能驾轻就熟,但对后者大概一筹莫展;而对外汉语专业的大学生可能恰好相反。所以,科目之间的难度不是一个绝对的数字,有些科目之间不能比较。这与日常生活中的“顺序”关系很不相同,比如说日期或者温度,总有个前后高低之分,不会有两个不能比较的日期或者温度。像日期和温度这类总能比较两个元素的序关系,在数学上被称为“全序关系”;像考试科目这类不一定能比较任意两个元素的序关系,则被称为“偏序关系”。这里的“偏”跟“以偏概全”中的意思差不多,指的是“不全面”。

学科比较图,来自Wikipedia

现在我们知道,我们要寻找的其实是考试科目之间的偏序关系。那么,给定两个考试科目,有什么办法能分辨两者孰难孰易,又或者无法比较呢?

有一些科目之间是很容易比较的,比如说小学数学当然比中学数学要容易,这是因为中学数学包含了小学数学的内容。一名能完成中学数学考试的学生,必定能完成小学数学考试。但有一些科目就不那么好比较了。线性代数和简单电路计算,初看风马牛不相及,一个是数学一个是物理,似乎没法比较。一个会线性代数的学生,如果没学过电路,似乎也没有理由能进行电路的计算。但如果这位学生知道基尔霍夫定理的话,他就能将电路计算的问题转化为线性方程组,从而用线性代数的知识去解决电路计算的问题。从这一点上来看,似乎电路计算要比线性代数容易,因为存在一种机械而固定的方法(电路的基尔霍夫定理),将电路计算的问题转化为线性代数的问题,而线性代数的问题则不一定能表达成电路的形式来求解。

把这种直觉抽象成数学语言的话,如果对于两门科目A和B,存在一种简单的方法P,能将科目A中的任意问题转化为科目B中的问题的话,那么B就不比A更简单,因为如果我们能解决科目B中的问题,那么面对科目A中的一个问题,我们只需要先用P将这个问题转化到我们能解决的科目B中,再用我们的知识去解决转化后的问题,那么就相当于间接解决了科目A中的原问题。如果这种转化是双向的,也就是说如果存在另一种方法能将科目B中的任意问题转化为科目A中的问题,那么我们就说A与B难度相当,否则我们就说B比A难。

问题规约示意图

这种将一个领域的问题变换到另一个领域来处理的方法,在数学中被称为化归或者规约(reduction),是数学家们常用的手段。将组合计数问题化归成连续函数的计算与展开,将代数方程的解空间化归成连续流形,不同的化归手法被数学家们源源不断地创造出来,一开始是神来之笔,但经过几代数学家的努力,最后积淀下来的就是一门全新的数学分支。通过规约,数学家能借用不同领域的各种工具来解决千变万化的各种问题。可以说,对于规约这一门手段,数学家们是再熟悉不过了。但将“规约法”本身抽象出来,则需要真正的数学洞见。

也许是因为太熟悉太习以为常,几乎没有人想到,规约法暗含着计算的另一重含义。

回到考试科目的比喻。如果有两门科目A与B,它们非常非常难,没有学生能不靠课本完成考卷里的任何一道题目,但只要有相应的课本,那么要拿到满分也不是特别困难。虽然两门科目都很难,但大家一般也认为B比A要更难一些。幸而这两门考试都是开卷,所以也没有人抱怨。有一天,一位学生急匆匆跑到科目A的考场,打开书包一看,才发现课本拿错了,手上只有科目B的课本。怎么办?

一般来说,开卷考试带错课本基本上就是死路一条。但我们知道科目A比科目B要容易,也就是说,存在一种方法,可以将科目A的问题转化为科目B的问题。那么,既然有科目B的课本,那么如果这位学生同时也知道问题转化的方法,那么先将试卷上的问题转化为科目B的问题,然后参考科目B的教科书解决这些问题,根据对应问题的答案,自然就能完美完成科目A的考试。

而谕示机,实际上就是一名带着课本参加开卷考试的学生。

判定问题即是考试科目,课本即是谕示,而学生本人,则是带有程序的图灵机。而我们比较考试科目相对难度的方法,实际上就是比较判定问题相对难度的方法。

我们知道,一台谕示机其实就是一台图灵机加上一个能解决某个特定判定问题的“谕示”。假设我们有两个特定的判定问题A与B,而我们希望比较两个问题的“难度”。对于判定问题A,我们将记载了A的所有解答的谕示称为谕示A。那么,我们考虑那些带有谕示A的谕示机,它们都能很快解答A的任意实例。如果存在一台这样的谕示机,它总能正确解答判定问题B的话,那么我们就说问题A至少比问题B要难。这跟开卷考试一样,不能奢求每位学生都知道怎么将科目B的问题转化到科目A中,但只要有一名学生知道怎么做,那么这种转化的方法就存在。在这种情况下,我们说问题B能够“图灵规约”到问题A,可以记作\( B \leq_T A \);如果同时问题A也能图灵规约到问题B的话,我们就说A与B是“图灵等价”的。

通过图灵规约与谕示机,我们可以比较不同的判定问题之间的相对难度。但谕示机本身就是一种计算方法,它从一个已知的问题出发,通过谕示假定这个问题已经被解决,从而探索那些相对于已知问题而言可以计算的问题。带有某个特定谕示的谕示机,它们能进行的计算是相对于某一个特定问题而言的。某个问题能否计算,取决于我们手上的谕示,换句话说,我们手上已有的知识。

作为一个概念,可计算性是相对的,而不是绝对的,这就是谕示机带给我们的谕示,也许也是图灵论文中哑谜的答案。

那么,揭示出这个谕示的,到底是怎么样的人呢?

埃米尔·波斯特,图片来自Wikipedia

0
为您推荐

19 Responses to “计算的极限(七):宛如神谕”

  1. 陈志祥说道:

    3点评论:

    1
    对于普通的图灵机而言,停机问题是不可判定的,这早已被证明。而图灵发现,即使将证明中的所有“图灵机”三个字都换成“带有‘数论问题’谕示的谕示机”,其他部分一字不易,证明依然成立!也就是说,就像普通图灵机不能解决关于自身的停机问题,谕示机也不能解决关于自身的停机问题,无论它的谕示有多么强大。
    ——?从你的说法来看,这个证明感觉是有缺陷的:既然Oracle机器实际不可能存在,那么拿来做假设毫无意义,正如数理逻辑中的蕴涵怪论,False -> False为真,前提条件错误,结论可以是任意的

    2
    通过图灵规约与谕示机,我们可以比较不同的判定问题之间的相对难度。但谕示机本身就是一种计算方法,它从一个已知的问题出发,通过谕示假定这个问题已经被解决,从而探索那些相对于已知问题而言可以计算的问题。带有某个特定谕示的谕示机,它们能进行的计算是相对于某一个特定问题而言的。某个问题能否计算,取决于我们手上的谕示,换句话说,我们手上已有的知识。
    ——这个假设仍然是错误的,考虑零知识证明,即使要归约的目标问题只是回答0/1这么简单,但假如这个过程需要1000万年的话,你也不能假设它就是0或1,你只能说你不知道

    3
    以上提到到TCS著名的“归约”,有点像数学里的同调代数、范畴论,我总是在想,是否存在一种“超级归约”,即可以把一个计算问题映射到另外一个模型完全不同的思维问题。。。

    • 傅铁强说道:

      “既然Oracle机器实际不可能存在,那么拿来做假设毫无意义”
      不,假设有强于图灵机的Oracle存在根本没有任何逻辑缺陷。神谕机的不存在完全是一个经验假设,也就是丘奇-图灵论题。

      “考虑零知识证明,即使要归约的目标问题只是回答0/1这么简单,但假如这个过程需要1000万年的话……你只能说你不知道”

      神谕机就是被假定为能一步做出答复,不考虑是否有物理机制能实现这个过程。

    • 傅铁强说道:

      “考虑零知识证明,即使要归约的目标问题只是回答0/1这么简单,但假如这个过程需要1000万年的话……你只能说你不知道”

      神谕机就是被假定为能一步做出答复,不考虑是否有物理机制能实现这个过程。
      至于如何从特定问题的答复转化到原问题的解答的时间复杂度那是另一回事。不管时间复杂度再高,你也不能说解答是“不知道的”。可解性和易解性是不可混淆的东西。

    • 方弦说道:

      1. 并非因为现实中不可能而我们就不能去研究它。实际上,谕示机与数理逻辑有着紧密的联系,在系列的后文中会讲到。在现实中它不存在,但作为一种数学对象它是存在的。

      2. 首先,你举的例子与零知识证明没有关系,零知识证明在系列后面可能会讲到。其次,在数学中我们不考虑任何实际操作上的问题,我只需要知道它在有限时间内可以得出结果就可以了,无论是10秒还是一千万年。

      3. 无法置评。要做归约,起码先要把定义域和值域说清楚……

    • kyle说道:

      "从你的说法来看,这个证明感觉是有缺陷的:既然Oracle机器实际不可能存在,那么拿来做假设毫无意义"

      小小驳一下。你这句话说说了两个问题。1,证明缺陷:反证法中先假设命题不成立,也就相当于原文中说的假设存在有停机问题解决方案的谕示机,推导出有停机问题解决方案的谕示机都不能解决停机问题的矛盾。证明没看出有缺陷。2,先假设一个不存在的东西进行下一步研究也太常见了。这么比方,我们假设昨天上海地震了,然后研究今天应该做的救援行动。这个假设根本不存在,就是你说的毫无意义,但是它的研究结论在另一个问题——比如某天另一个城市广州地震了——的救援中,就起了大作用。当然,谕示机的假设在数学中有更深入的应用。

      2和3 方弦说的也是我想说的。

      求下一篇的ETA

      • 方弦说道:

        下一篇已经写出来了,但是插画师很忙……

  2. Wantal说道:

    天呐天呐天呐!终于更新了!真是十年磨一剑呀,绝对的精品中的精品。

  3. qyscw说道:

    莫非。。。某个问题是否是可计算的,未必可计算?

  4. chemhunter说道:

    感觉那人像冯•诺依曼

  5. yehg01说道:

    终于又看见极限系列了,虽然看着只是不明觉厉。

  6. why说道:

    Emil Leon Post

  7. Jacob说道:

    多少年过去了终于更了!

  8. Jacob说道:

    去年7月19日的《New Scientist》里有文章介绍,90年代曾经有位Hava Siegelmann博士试图用所谓“人工神经网络”制造喻示机,1995年甚至还在《Science《发表了喻示机的数学证明,题目是《Computation beyond the turing limit.》。此人现在是马萨诸塞大学Biologically Inspired Neural & Dynamical Systems lab的主任,又在与密苏里州立大学的Emmett Redd以及Steven Younger一起“用人工神经网络造喻示机”。他们是不是骗人的啊?

    • 方弦说道:

      也不能算骗人,但是他所说的东西其实大家都知道,并不新鲜。他实际上是说,如果我们能直接计算实数的话,每次实数运算算是一步的话,那么就能超越一般图灵机的计算极限。问题是,我们目前连一个储存实数的方法都没有,遑论计算了。这是因为实数实际上是无限精度的,而我们目前实际上并没有方法处理无限精度的东西,或者说连拥有无限精度的东西是否存在都不知道,这是由于有量子不确定性的存在。

      • Jacob说道:

        受教了,开始还以为他们要推翻哥德尔不确定性原理……

  9. Semon说道:

    这个真好难理解

  10. 不告诉你!说道:

    赞死了!

  11. fooloo说道:

    碉堡了这个专题!