除非数学错误,否则这台图灵机应该永远运行

2018-01-02 13:49:10

美术图像/遗产图像/盖蒂雅各布阿隆如果一台新的计算机程序停止运行,将会证明一百五十年的数学是错误的值得庆幸的是,它不太可能发生,但它背后的代码是测试数学领域的极限该程序是一个模拟图灵机,一个由密码破解者Alan Turing创建的计算数学模型 1936年,他展示了任何计算机算法的动作都可以通过简单的机器来模仿,该机器通过处理一组状态或指令在无限长的磁带上读取和写入0和1算法越复杂,机器所需的状态就越多现在,麻省理工学院的Adam Yedidia和Scott Aaronson创造了三种模拟图灵机,其行为与数学的深层问题交织在一起这包括150年历史的黎曼假设的证明 - 被认为可以控制素数的模式图灵的机器起源于20世纪30年代震撼数学世界的一系列哲学启示首先,KurtGödel证明了某些数学陈述永远不会被证明是真或假 - 它们是不可判定的他基本上创造了句子“这句话是假的”的数学版本:一个与自身矛盾的逻辑思维扭曲哥德尔的断言有一个退出条款如果你改变了构建证据的基本假设 - 公理 - 你可以提出一个可判定的问题但这仍然会留下其他不可判断的问题这意味着没有公理可以让你证明一切根据哥德尔的观点,图灵证明必须有一些图灵机器,其行为无法在标准公理下预测 - 简称为ZFC--支撑着大多数数学但我们不知道他们会有多复杂现在,Yedidia和Aaronson已经创建了一个拥有7918个状态的图灵机器他们把它命名为“Z” “我们试图让它变得具体,并说在你进入这个无法改善的深渊之前需要多少个州”Aaronson说 Z被设计为永远循环其7918指令,但如果它最终停止,则证明ZFC不一致然而,数学家不会太恐慌 - 他们可以简单地转向一组稍微强大的公理他们还创造了两台机器,只有两个着名的数学问题(长期以来都是真的)才会停止这些是哥德巴赫的猜想,它指出每个大于2的偶数是两个素数的总和,以及黎曼假设,它表示所有素数都遵循某种模式后者构成了现代数论的部分基础,反驳它将是一个主要的,不太可能的不安 “在你进入这个无法生存的深渊之前需要多少个州”表达数学问题作为图灵机也有一个实际的好处:它有助于弄清楚它们有多复杂 Goldbach机器有4888个州,Riemann机器有5372个,而Z有7918个,这表明ZFC问题是三个中最复杂的 Yedidia和Aaronson希望看看Z是否可以用更少的指令运行 - 哥德尔和图灵可能想知道的事情 “他们可能会说'那很好,但你可以获得800个州吗 80个州呢“”Aaronson说 “我想知道是否有一台10状态机的行为与ZFC无关”这篇文章出现在标题“图灵机测试数学基础”的标题下更正:自本文发表以来,