好久没有读GEB了,今天兴之所致,没有看prml,而是又翻了翻这本神书,我把神书切割为六个章节,现在已经读到了第四部分,春节努把力,争取今年再结束一本书.

这次要谈的是有界循环,也就是说,在编程时,我们使用控制结构来控制某些语句的执行次数,从而编制算法,获知结果,比如求最大公约数的欧几里德算法.我们可以保证,算法肯定会在有限次数之内结束(丫的,这个有限次数是多少,稍微一算,感觉还需要再确定一下的样子.不过总不可能比被除数N还大).那么我们可以设置一个有界循环,即让算法循环N次,可以保证在N次之内,一定能够计算出结果.

如果程序中的循环结构中只包含有界循环,我们就称其为了bloop(bounded loop)程序.

那么问题就来了,是否所有的问题都可以使用bloop程序来解决?

GEB这一章给出一个非常有意思的证明,虽然证明的结果和之前一样,仍然是构造了一个无法自包含的bug来,但是这个过程本来就非常有意思了.

想象我们有一个仓库,在这个仓库中,装着所有的有界循环,很明显,这个仓库是无穷大的.但是却可以使用整数来刻画,因为不管有多少,把其一一地列举出来,并排开,总是理论上可以花费无穷的时间可以做到的事情.

我们现在来考虑各种自然数的性质,比如素性,是否是完全数,是否可以分解为两个奇素数相加,那么这种自然数的性质就可以表示成一个bloop程序.
由于这种bloop程序的目的是测试某个数的性质,因此他只需要接受一个参数就可以.

这样我们得到的仓库是这样的,里面关着无数的bloop程序,而每个bloop程序只能够执行有事先给定次数的循环,同时只接受一个参数.
把这种程序称之为怖陋朴程序.

对于这个怖陋朴程序的集合,将它写下来,然后按照字典顺序一行一个地写下去.这样我们就得到了一个怖陋朴的登记表.

在这个登记表中,每个怖陋朴和其他的怖陋朴是不同的.我们可以确保没有一个怖陋朴程序会占据两行,但是却一样.

于是形式化来说,我们的登记表,有这样的形式:

• k 怖陋朴(n)
• k+1 怖陋朴(n)

如果我们把每个怖陋朴程序的编号考虑进来,然后再使用一种统一的方式来调用这个仓库,我们可以这样做
怖陋朴{#k}(n)
也就是说,我们通过这样的形式,来调用第k个怖陋朴程序,并将参数n传递给它.

在这种情况下,我们就可以定义出一个程序,它是一个怖陋朴程序,然后这个程序却不在这张无穷的登记表中!

• 怖恐程序(n) = 1+怖陋朴{#n}(n) (我们定义某个怖陋朴程序”怖恐”)

也就是说,在这样我们使用了二义性,本来{#n}这个超参数,是登记表的编号,可是我们却将它当做一个内置参数来使用.从而将编号传递给函数自身进行处理,就像构造了一条咬着自己尾巴的蛇一样.
这个怖恐程序怖恐在那里呢?

你会发现这个怖恐程序是不可能出现在那张号称登记了所有怖陋朴程序的登记表中的,虽然这个怖恐程序,满足怖陋朴程序的所有定义:它只包含有界循环,它只接受一个参数.它衡量某种自然数的性质…….

来看为什么怖恐程序不可能出现在登记表中.

假设怖恐程序出现的登记表中的话,那么,根据我们的登记表的格式,我们可以说怖恐程序会拥有一个编号,而这个编号可能是x.

也就是说:

• 怖恐程序(n) = 怖陋朴{#x}(n) (根据登记表得出的定义)

你会发现,这个根据登记表推导出来的结果,与怖恐程序是不相容的.
比如,假设怖恐程序在登记表是第72号.
当我们把72传递给怖恐时,就出现这么个情况.
怖恐(72)=怖陋朴{#72}(72)
然而同时.
怖恐(72)=1+怖陋朴{#72}(72)

这两者是矛盾的.

也就是说,我们定义的某种数的性质,是无法通过有界循环来证明的.
这也就是与哥德尔定理一种非常浅显的表达.
当我们,构造一个东西,这个东西同时在两个层次之间存在意义,那么这个东西就可以破坏人们对一个形式化系统的幻想.
要么我们像罗素一样,禁止一个东西同时存在于两个层次之间,而这会带来极大的不方便,以及表达的局限性,要么我们就必须承认,在整个系统中,肯定存在某种矛盾的不自洽性.

….感觉没有说明白…..
不过还好,GEB神书如果如此容易被表述清楚,也枉为神书了.

下次继续讲,层次这个问题太有意思了.