科学家用计算机破解了一道80余年的数学难题

数学星空

   据美国《物理学家组织》(phys.org)网站报道，英国计算机专家阿列克谢·利什特沙和鲍里斯·科涅夫最近借助计算机破解了一道有80余年历史的数学难题——埃尔德什差异问题(the Erdos Discrepancy Problem)。他们的论文预印本已发表在这里.

埃尔德什差异问题是由匈牙利数学天才保罗·埃尔德什于1932年提出的数学假设。其围绕着只包含1和-1的无穷数列性质进行探讨；这类数列中的模型能够通过创建有限子序列进行测度。英国数学家恩里科·斯卡拉斯通俗解释了这一假设：“假如你有一个由1和-1（例如由扔硬币随机产生）组成的数列和常数C。你要寻找到一个足够长的有限数列，使这一数列的总和大于常数C。”

利什特沙和科涅夫的论文描述了他们如何建立计算机程序来破解埃尔德什差异问题。由于证明产生的数据有13GB之多(维基百科的整个数据才10GB)，以至于不可能由人工来检验。这就产生了一个有趣的问题：如果借助计算机证明数学命题，而数据的绝对量过于庞大，以至于没有办法由人工进行验证，那么这种证明能否被验证真伪呢？

计算机的发明，是为计算而来，而计算能力始终是计算机的根本计算机的发明，是为计算而来，而计算能力始终是计算机的根本。计算机的介入改变了数学研究的方法，扩展了数学研究的领域，促进了计算数学的发展。尤其是运算量极其庞大的数学问题，大多数情况只能借助计算机来解决。例如，四色问题、E8结构、费克特(Fekete)问题、开普勒(Kepler)猜想等著名数学难题，都是借助计算机来破解的。

计算机成为数学研究的工具已是大势所趋，不可阻挡。正如我国知名学者周海中先生在“21世纪数学展望”一文中所言：计算机在数学研究中发挥的作用将越来越大；借助计算机解决数学问题将激励人们去寻求更好、更简单的方法，也加深人们对数学本质特征的认识，还推动以计算机为基础的人工智能的发展。

毫无疑问，在计算机的助力下，破解数学难题的成果今后会越来越多。

转自：http://www.cms.org.cn/cms/sxxw/20140331.htm

数学星空

关于the Erdos Discrepancy Problem：
更详细的介绍可见：
http://michaelnielsen.org/polyma ... discrepancy_problem
预印本可见：
1402.2184.pdf (96.89 KB, 下载次数: 11)

2014-4-6 19:02 上传

点击文件名下载附件

yyy_fcz

“如果借助计算机证明数学命题，而数据的绝对量过于庞大，以至于没有办法由人工进行验证，那么这种证明能否被验证真伪呢？”
这不应该叫做证明了吧~

云梦

计算机只能是去验证，不是证明！证明与数据量大小无关。

zeroieme

云梦 发表于 2015-5-15 16:29
计算机只能是去验证，不是证明！证明与数据量大小无关。

你对机器证明一点概念都没有。

282842712474

云梦 发表于 2015-5-15 16:29
计算机只能是去验证，不是证明！证明与数据量大小无关。

假如证明有$10^{10}$页呢？计算机写出来可能很简单，人工写出来几乎不可能，这就是数据量问题。

为什么计算机不能证明？且不说具有一定推理能力的计算机，单纯是具有枚举和计算能力的计算机，也可以完成证明，比如人工已经证明了某方程的整数解不超过10^{50}，那么计算机就可以一个个去验证，验证完了，就算证明。

云梦

计算机也好笨啊，受累的全是计算机。