1742年,一个不那么有名的数学家哥德巴赫给超级有名的大神欧拉的信中提出了以下猜想:“任一大于5的整数都可写成三个质数之和。”并请求欧拉来给予证明。欧拉回信又加强了一下命题,改为“任一大于2的偶数都可写成两个质数之和。”前一个命题叫弱哥德巴赫猜想,后一个称为强哥德巴赫猜想,欧拉至死都没有证明这个问题。
哥德巴赫
这个有名的猜想在最初的280年间几乎毫无进展,人们只知道通过验算,一直都没有发现反例,很多人也坚信这个猜想是正确的。
20世纪以后,人们改用步步推进的方式来围攻哥德巴赫猜想。用“a+b”来表示如下命题:每个大偶数N都可表示为A+B,其中A和B的素因子个数分别不超过a和b。于是,终极目标就是证明偶数满足1 + 1。
沿着这个思路,1920年,挪威的布朗率先证明了9 + 9,显然这个结果离最终的结论很远,但终究是迈出了第一步,所以意义仍然重大。接着7 + 7,6 + 6,5 + 9陆续都出来结果,中国数学家在哥德巴赫猜想的研究上独占鳌头。王元在1956年证明了3 + 4,3 + 3,2 + 3。1962年,潘承洞证明了1 + 5,同年,王元又攻破了1 + 4。直到1966年,陈景润用改进的筛法证明了1 + 2,距离终极目标仅有一步之遥。然而至此之后的50年,数学界对于哥德巴赫猜想的研究再也没有重大进展。很多数学家认为,用筛法作为武器来对付哥德巴赫猜想其实已经弹尽粮绝了。
中国解析数论三驾马车——王元陈景润潘承洞
电子计算机的逐步发展,给各个行业带来了脱胎换骨的改变。有人在对停机问题的研究上给出了不一样的角度构造了一个精巧的理想实验来应对哥德巴赫猜想问题。
计算机刚刚诞生之初,人们就考虑过停机问题。最初时代的程序员都幻象着,有位大牛能够发明一套算法,用这个算法可以检测任意程序代码,并分析这些代码段是会在某个节点停止执行,还是陷入死循环一直执行。如果真的有这样的一套算法,那么今天的程序员会省掉很大一部分精力来检查代码的有效性,他们只要把精力集中在方法的实现上就可以。
我们编写一个简单的验证哥猜小程序,从6开始进行验证,并且不限制上限值。如果这样的超级算法存在,那么我们将这个小程序用超级算法检验,当验算到某个数值时,如果超级算法给出的结果是程序将永不停机,那么我们也就不用继续下去,换句话说,这样就已经证明了哥德巴赫猜想了。
而实际上停机问题的产生是一种逻辑上的矛盾性。1936年,图灵(又是图灵)证明这样的超级算法不存在,你永远用自身的逻辑体系去评价自身的逻辑正不正确。虽然这样的超级算法不存在,我们还可以继续去开拓一种思路,那么任意程序停机的概率总是存在的吧,而且这个概率是个定值,也就是蔡廷常数。
下面我们来一场头脑风暴吧。
“异形计算机”
假设我们有一台无穷算力,无限内存,并且无尽寿命的超级计算机,这个计算机可以计算世界上任何复杂的问题,我们将这个计算机称为异形计算机。现在我们把所有可能排列的程序按照文件大小从1,2,3...q来分类,并且将每一类的停机概率设置为P1,P2,P3...Pq。N是已验证停机程序的个数,M是已验证总的程序个数,显然,Pq=N/M,。如果当前验证的程序是停机的,那么P=(N+1)/(M+1),如果当前验证程序不停机,那么P=N/(M+1)。注意这里的程序是广义上的,实际上我们交给异形计算机的任务是,用穷举法将任意合法字符组合成代码段,这里大部分都不能被称之为程序,因为有各种语法错误,逻辑错误等等,也就压根谈不上执行了。
我们将长度从1,2,3...q的程序做一个总的停机概率统计Ω。异形计算机开始工作,开始执行这些无比复杂艰巨的任务。我们关注显示器上Ω的值以及当前的Pq值。这两个概率值不会随着验证次数增加而上下跳跃,随着海量无穷的程序被逐渐验证,我们最终会发现这个两个数值会逐渐逼近某个值,蔡廷常数就是这个值的下限。那么我们什么时候才可以判定某个程序是否永不停机呢?
这里我们让异形增加一个判别条件,
Min函数左边表示,增加一个停机程序对于程序长度k停机概率值的正贡献,右边表示,增加一个不停机程序对于程序长度k停机概率值的负贡献。这个判别条件的意思是,若长度为k的所有程序的停机概率Pk与总体概率值Ω的差值已经比程序增加一个程序给整体概率值带来的正负贡献还要小时,我们就可以断定,那些此时还在运行着的程序,将永远不停机!
举个数学家在证明中用到的例子,类似于这里在找一个充分大的k。
2013年,法国巴黎高等师范学院的研究员哈洛德•贺欧夫各特彻底证明了弱哥德巴赫猜想。
哈洛德•贺欧夫各特
由于现实里,我们并没有异形计算机这样空前的算力,所以计算机只能验算相对有限范围的数值。前人已经证明了,充分大的奇数情况下,弱哥德巴赫猜想成立。贺欧夫各特的重大贡献在于,他第一次将这个充分大的下界降到了计算机可以验算的范围内,10的30次方。很快10的30次方以内的所有奇数通过验证,因此也弱哥猜被完全解决。异形计算机的工作也类似,它除了要执行那些复杂无限的计算任务以外,还必须时时关注什么时候程序会产生满足判别式的k,如果k值找到,那么异形计算机任务完成,我们朝思暮想的猜想也就解决了。
倘若异形在找到满足判别式的k之前,某个猜想的验证程序就已经停机了,那么显而易见,这些猜想仅对有限的数字是成立的,并不能推广到所有情况。如果异形已经找到k,此时检索当前仍然运行的程序里有哥德巴赫猜想验证程序,费马大定理验证程序,或者孪生素数验证程序。那么这些验证程序就将会被永远执行下去,不停机,换句话说,我们已经从另外一个角度上证明了这些猜想对所有的自然数都是成立的,也就是证明了这些重大问题!
在这里,我们实际上并没有用到多么高深的数论知识,我们只是拥有一台超凡算力的异形计算机,以及一些构造性的简单验证算法而已。然而这样的理想思维实验却对着所有的需要验算全体自然数的数论问题很有效,因此也有人把这样的方法称之为证明数论问题的“万能方法”。
当然了,这样的算法实际上并没有多少可执行性,但是却给我们带来了一个独特的角度来思考问题,就像是给数学证明开启了一扇新的窗户。我们相信大概很多年之后,必定会有一个人站出来给出纯理论的方法证明哥德巴赫猜想,不论采用的是陈景润的筛法还是另辟蹊径的新方法。
留言与评论(共有 0 条评论) |