哥德巴赫猜想解决了吗?揭示数学的基本极限


哥德巴赫猜想解决了吗?揭示数学的基本极限

文章插图
  • 目前已知运行时间最长的五规则图灵机的可视化 。每一列像素代表计算中的一步,从左向右移动 。黑色方块表示机器打印了1的位置 。最右边的一列显示了当图灵机停止时的计算状态 。
程序员通常希望最小化代码的执行时间 。但在1962年,匈牙利数学家提博尔·拉多提出了相反的问题 。他问,一个简单的计算机程序在终止之前最多能运行多少步骤?拉多将这些效率最高但仍能正常工作的程序称为“忙碌的海狸” 。
自从1984年在《科学美国人》的“计算机娱乐”专栏中流行以来,对于程序员和其他数学爱好者来说,寻找这些程序一直是一个极其有趣的谜题 。但在过去的几年里,忙碌的海狸游戏已经成为一个研究的对象,因为它与数学中一些最崇高的概念和开放问题产生了联系 。
最近的工作表明,搜索长时间运行的计算机程序可以阐明数学知识的状态,甚至告诉我们什么是可知的 。根据研究人员的说法,“忙碌的海狸”游戏为评估某些问题的难度提供了一个具体的基准,例如尚未解决的哥德巴赫猜想和黎曼假设 。它甚至让我们看到,数学背后的逻辑基石在哪里崩溃了 。近一个世纪前,逻辑学家库尔特·哥德尔就证明了这种数学未知领域的存在 。但忙碌的海狸游戏可以显示它实际上在数轴上的位置,就像一幅描绘世界边缘的古老地图 。
无法计算的电脑游戏“忙碌的海狸”是关于图灵机的行为的,它是由艾伦·图灵在1936年构想出来的原始的、理想化的计算机 。图灵机在被分割成无数个正方形的带上执行操作 。它是根据一系列规则来运行的 。第一条规则是:
如果正方形包含0,则将其替换为1,向右移动一个正方形并参照规则2 。如果正方形包含1,离开1,向左移动一个正方形并参考规则3 。
每个规则都有这种分叉的“选择自己的冒险”风格 。有些规则说要回到以前的规则,最终会有一条包含“停止”指令的规则 。图灵证明,只要有正确的指令和足够的时间,这种简单的计算机就能进行任何可能的计算 。
正如图灵在1936年指出的,为了计算一些东西,图灵机最终必须停止——它不能陷入无限循环 。但他也证明了,没有可靠的、可重复的方法来区分机器停机和机器简单地无限循环运行,这个事实被称为停机问题 。
“忙碌的海狸”游戏的问题是:给定一定数量的规则,在图灵机停止运行之前,它能执行的最大步骤是多少?
  • 在这张未注明日期的照片中,提博尔·拉多发明了忙碌的海狸游戏,将理论上的不可计算性具体化 。
例如,如果只允许一条规则,并且想要确保图灵机停止,那么这条规则里必须包含停止指令 。单规则机器的忙碌的海狸数为1,即BB(1) =1 。
但只要再增加几条规则,需要考虑的机器数量马上就会激增 。有两个规则的6561个可能的机器中,在停止运行之前的最大步骤是6步,也有些干脆无限循环了 。这些都不是忙碌的海狸,但你如何确定地排除它们呢?图灵证明了,没有办法自动判断运行1000步或100万步的机器最终会不会终止 。
这就是为什么发现忙碌的海狸如此困难的原因 。没有通用的方法来识别使用任意数量的指令运行时间最长的图灵机,你必须自己弄清楚每一种情况的具体情况 。换句话说,“忙碌的海狸”游戏一般来说是“不可计算的” 。
证明BB(2) = 6和BB(3) = 107是非常困难的,因此拉多的学生沈林在1965年获得了该研究的博士学位 。拉多认为BB(4)完全没有希望了,但这最终在1983年解决了 。除此之外,这些值实际上会暴增 。研究人员已经确定了一个具有5条规则图灵机,例如,5规则图灵机运行47,176,870步才停止,所以BB(5)至少有这么大 。BB(6)至少为7.4×10^36,534 。要证明确切的值,需要新的想法和新的见解 。
阈值马里兰大学帕克分校的计算机科学家威廉·加斯克说,他对“忙碌海狸的数量实际上无法计算这一普遍概念”更感兴趣,而不是对确定忙碌海狸的数量的前景感兴趣 。他和其他数学家主要感兴趣的是,将博弈作为衡量重要数学开放问题难度的标尺,或者用来弄清什么在数学上是可知的 。
例如,哥德巴赫猜想询问是否每个大于2的偶数都是两个素数的和 。在数论中,证明猜想的真假将是一个划时代的事件,使数学家们能够更好地理解质数的分布 。2015年,一个名匿名用户发布了一个27条规则的图灵机代码,当且仅当哥德巴赫猜想是假的时候,该代码才会停止运行 。它的工作原理是向上计算所有大于4的偶数,对于每一个整数,它都会通过将另外两个相加的所有可能方法来得到这个整数,并检查这两个整数对是否为素数 。当它找到合适的质数对时,它移到下一个偶数并重复这个过程 。如果它发现一个不能用质数对求和的偶数,它就会停止 。
运行这个无需动脑筋的机器并不是解决猜想的实际方法,因为在它停止之前,我们无法知道它是否会停止 。但忙碌的海狸游戏为这个问题提供了一些线索 。如果计算BB(27)是可能的,这将为我们等待哥德巴赫猜想自动解决的时间提供一个上限 。这是因为BB(27)对应的是这个27条规则的图灵机为了停止而必须执行的最大步骤数 。如果我们知道这个数字,我们就可以运行图灵机这么多步骤 。如果它停在那一点,我们就知道哥德巴赫猜想是假的 。但如果它永远不会停下来,那么就证明了猜想的正确性 。
问题是BB(27)是一个难以理解的巨大数字,更不用说去运行那么多步骤,在我们的物理宇宙中也根本不可能 。然而,这个不可理解的巨大数字仍然是一个精确的数字 。
2016年,三位数学家发现了一台744条规则图灵机,当且仅当黎曼假设为假时,它才会停止工作 。黎曼假设也涉及质数的分布,是克莱数学研究所价值100万美元的“千年难题”之一 。
当然,BB(744)是一个比BB(27)更大的数字 。但是,努力确定一些更简单的东西,比如BB(5),实际上可能会出现一些新的数字理论问题,这些问题本身就很有趣 。例如,数学家帕斯卡?米歇尔在1993年证明,保持纪录的5规则图灵机表现出类似于科拉茨猜想中描述的函数的行为 。科拉茨猜想是数论中另一个著名的开放问题 。
1931年哥德尔著名的不完全性定理证明,任何一组基本公理,只要能作为数学的逻辑基础,都注定会有两种命运,【即要么公理将不一致,导致矛盾(比如证明0 = 1),或者他们会不完整,无法证明一些真实陈述数据(如2 + 2 = 4)】,支撑几乎所有的现代数学的公理系统 。被称为ZF集合理论,有它自己的哥德尔边界 。
2016年,研究生亚当·耶迪迪亚和他的导师设计了一个7910条规则的图灵机,只有在ZF集合理论不一致的情况下,图灵机才会停止 。这意味着BB(7910)是一个避开了ZF集合理论公理的计算 。这些公理不能用来证明BB(7910)代表的是一个数而不是另一个数,就像不能证明2 + 2 = 4而不是5一样 。
随后,瑞娅尔设计了一个更简单的748规则机器,如果ZF不一致,它就会停止——实质上是将不可知阈值从BB(7,910)移近到BB(748) 。俄亥俄州立大学的数学逻辑学家、名誉教授哈维?弗里德曼表示:“数量并非完全荒谬,这是一件引人注目的事情 。”弗里德曼认为,这个数字还可以进一步降低 。无论远近,这种不可知的阈值确实存在 。
【哥德巴赫猜想解决了吗?揭示数学的基本极限】


    以上关于本文的内容,仅作参考!温馨提示:如遇健康、疾病相关的问题,请您及时就医或请专业人士给予相关指导!

    「四川龙网」www.sichuanlong.com小编还为您精选了以下内容,希望对您有所帮助: