Main

Math's Fundamental Flaw

Not everything that is true can be proven. This discovery transformed infinity, changed the course of a world war and led to the modern computer. This video is sponsored by Brilliant. The first 200 people to sign up via https://brilliant.org/veritasium get 20% off a yearly subscription. Special thanks to Prof. Asaf Karagila for consultation on set theory and specific rewrites, to Prof. Alex Kontorovich for reviews of earlier drafts, Prof. Toby ‘Qubit’ Cubitt for the help with the spectral gap, to Henry Reich for the helpful feedback and comments on the video. ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ References: Dunham, W. (2013, July). A Note on the Origin of the Twin Prime Conjecture. In Notices of the International Congress of Chinese Mathematicians (Vol. 1, No. 1, pp. 63-65). International Press of Boston. — https://ve42.co/Dunham2013 Conway, J. (1970). The game of life. Scientific American, 223(4), 4. — https://ve42.co/Conway1970 Churchill, A., Biderman, S., Herrick, A. (2019). Magic: The Gathering is Turing Complete. ArXiv. — https://ve42.co/Churchill2019 Gaifman, H. (2006). Naming and Diagonalization, from Cantor to Godel to Kleene. Logic Journal of the IGPL, 14(5), 709-728. — https://ve42.co/Gaifman2006 Lénárt, I. (2010). Gauss, Bolyai, Lobachevsky–in General Education?(Hyperbolic Geometry as Part of the Mathematics Curriculum). In Proceedings of Bridges 2010: Mathematics, Music, Art, Architecture, Culture (pp. 223-230). Tessellations Publishing. — https://ve42.co/Lnrt2010 Attribution of Poincare’s quote, The Mathematical Intelligencer, vol. 13, no. 1, Winter 1991. — https://ve42.co/Poincare Irvine, A. D., & Deutsch, H. (1995). Russell’s paradox. — https://ve42.co/Irvine1995 Gödel, K. (1992). On formally undecidable propositions of Principia Mathematica and related systems. Courier Corporation. — https://ve42.co/Godel1931 Russell, B., & Whitehead, A. (1973). Principia Mathematica [PM], vol I, 1910, vol. II, 1912, vol III, 1913, vol. I, 1925, vol II & III, 1927, Paperback Edition to* 56. Cambridge UP. — https://ve42.co/Russel1910 Gödel, K. (1986). Kurt Gödel: Collected Works: Volume I: Publications 1929-1936 (Vol. 1). Oxford University Press, USA. — https://ve42.co/Godel1986 Cubitt, T. S., Perez-Garcia, D., & Wolf, M. M. (2015). Undecidability of the spectral gap. Nature, 528(7581), 207-211. — https://ve42.co/Cubitt2015 ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ Special thanks to Patreon supporters: Paul Peijzel, Crated Comments, Anna, Mac Malkawi, Michael Schneider, Oleksii Leonov, Jim Osmun, Tyson McDowell, Ludovic Robillard, Jim buckmaster, fanime96, Juan Benet, Ruslan Khroma, Robert Blum, Richard Sundvall, Lee Redden, Vincent, Marinus Kuivenhoven, Alfred Wallace, Arjun Chakroborty, Joar Wandborg, Clayton Greenwell, Pindex, Michael Krugman, Cy 'kkm' K'Nelson, Sam Lutfi, Ron Neal ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀ Executive Producer: Derek Muller Writers: Adam Becker, Jonny Hyman, Derek Muller Animators: Fabio Albertelli, Jakub Misiek, Ivy Tello, Jonny Hyman SFX & Music: Jonny Hyman Camerapeople: Derek Muller, Raquel Nuno Editors: Derek Muller Producers: Petr Lebedev, Emily Zhang Additional video supplied by Getty Images Thumbnail by Geoff Barrett ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀

Veritasium

2 years ago

在数学的世界中有着一个无底深洞 这个深洞意味着我们永远无法对所有事物都获得确切了解 数学的世界中永远存在着无法被证明的真命题 没人能确切地知道这些命题是什么 但可能是像孪生素数猜想之类的 孪生素数是指那些差值为 2 的一对素数 例如11和13,17和19 沿着数轴正方向一直走 素数的出现频率逐渐降低,孪生素数也愈发稀少 然而孪生素数猜想认为,存在无限多组孪生素数 永远数不完 到目前为止,还没有人能证明或证伪这个猜想 而最疯狂的是 我们可能永远无法知道(这个猜想的真伪) 因为已经有人证明了一个事实: 在任何能够进行基本算术的数学系统中 总会存在一些无法证明的真命题 那就是「生命」 确切的说 是在1970年由数学家约翰・康威发明的生命游戏 确切的说 是在1970年由数学家约翰・康威发明的生命游戏 很遗憾他在2020年因感染新冠病毒逝世 康威生命游戏是在一个无限大的网格上进行的 格子里的每个细胞只有死和活两种状态 规则只有两条 ①如果一个死细胞周围有三个活细胞 它下一刻会复活 ②如果一个活细胞周围的活细胞少于2个或多于3个,它下一刻会死掉 设定了网格一开始的状态后 就可根据这两条规则
计算出下一刻的场景 然后再下一刻 以此类推 这完全是自动的 所以康威称它是「零玩家游戏」 然而尽管规则很简单 但游戏里的“生命”却能够产生多种多样的行为 有的图案很稳定,形成后就不再变动 有的图案则会往复变化 有几个图案甚至可以在网格上移动 像这个滑翔机一样 许多图案则会湮灭 但有少数几个会不断生长下去 不停地生成新的细胞 现在你可能觉得,既然规则那么简单 是不是可以光看初始图案 就能判定它最后 是会到达一个稳定的状态 还是会无限地增殖下去 然而 这个问题实际上无法回答 康威生命游戏里 图案的最终命运是无法判定的 意思是 不存在哪个算法 能保证在有限的时间内判定图案的结果 意思是 不存在哪个算法 能保证在有限的时间内判定图案的结果 你当然可以试着让图案运行一下看看会发生什么 毕竟这个游戏说到底也是一种算法 然而这依然不能保证解答这个问题 因为 即使跑了一亿轮 仍不能断定 是永远循环呢 还是跑到两亿轮、十亿轮、乃至上千万亿轮再终止 生命游戏有没有什么特殊之处 导致它是无法判定的呢 并没有 实际上有很多很多的系统都是不可判定的 包括王氏砖 量子物理 机票
订票系统 乃至万智牌 包括王氏砖 量子物理 机票订票系统 乃至万智牌 要想知道 为何方方面面都存在不可判定性 我们先得回到150年前 回到数学史上的那场全面革命 1874年 德国数学家格奥尔格·康托尔 开创了被称为「集合论」的崭新数学分支 开创了被称为「集合论」的崭新数学分支 集合就是有确切定义的一堆东西 你脚上穿着的两只鞋构成了一个集合 世界上的所有天文台也构成一个集合 什么都没有的集合——空集 还有包含所有东西的集合 然后康托尔开始思考数集 例如由正整数1,2,3,4等组成的自然数集 以及包含了 1/3, 5/2 等分数 和 π, e 和 √2 等无理数的实数集 简单地说 所有能用无限小数写出来的数都在实数集里 他寻思着 「所有自然数」和「0到1之间的实数」哪个更多呢 答案看似呼之欲出 二者都包含无限多的数,所以两个集合当然也就一样大了 但为了验证这个思路 康托尔虚构了一个无限长的清单 左边是所有的自然数 右边是0和1之间的所有实数 表中的实数均为无限小数 并不能找到所谓的第一个实数 所以我们把实数随意地写下来即可 关键是保证我们不重复地列出了所有的实数 并且让它
们和所有正整数一一对应 如果我们能没有遗漏地匹配上所有实数 就证明了 自然数的集合和0到1之间的实数的集合一样大 自然数的集合和0到1之间的实数的集合一样大 假设我们成功得到了一张完整的无穷列表 假设我们成功得到了一张完整的无穷列表 里面的自然数就像索引一样 唯一的对应上了列表里的每一个实数 康托尔现在开始写下一个新的实数 写的方法是 新实数的第一位是1号实数的第一位+1 第二位是2号实数的第二位+1 第三位是3号实数的第三位+1 顺着列表一路写下去 如果某一位是9,则-1变为8 最后你又得到了一个0到1之间的实数 关键之处就在这里:这个数字必然没有在列表上出现过! 第一位不同于1号实数,第二位不同于2号实数,以此类推 第一位不同于1号实数,第二位不同于2号实数,以此类推 第一位不同于1号实数,第二位不同于2号实数,以此类推 和列表里的每一个实数对比 它必然都至少相差一位——相差了对角线上的数 因此它得名「康托尔对角线证明」 它证明了0到1之间的实数的数量必然多于全体自然数 它证明了0到1之间的实数的数量必然多于全体自然数 所以无穷和无穷之间也是不等的 康托尔将二者分别命名为「可数无穷
」和「不可数无穷」 而且事实上还存在着许许多多的不可数无穷比这更大 康托尔当时的发现绝不是数学的第一次危机 两千年以来 欧几里得的《几何原本》被公认为是几何学的基石 但进入19世纪后 罗巴切夫斯基和高斯发现了非欧几何 这促使数学家更严密地去审视他们领域的根基 这促使数学家更严密地去审视他们领域的根基 数学家看到了他们不愿看到的情形: 微积分的核心——极限的定义是有瑕疵的 微积分的核心——极限的定义是有瑕疵的 因为康托尔证明 极限本身比前人所想的要复杂得多 因为康托尔证明 极限本身比前人所想的要复杂得多 这一系列动荡让数学界变得分裂 在19世纪末,数学家之间爆发了一场巨大的辩论 一方是直觉论者 他们认为康托尔所做的事是瞎扯 他们坚信 数学纯粹是人类思想的产物 像康托尔所说的这种极限是不存在的 亨利・庞加莱称 在后人眼中 集合论是前人曾经患上的一次疾病 在后人眼中 集合论是前人曾经患上的一次疾病 利奥博德・克罗内克直斥康托尔为「科学骗子」 并说他「腐化年轻人」 他一直阻挠康托尔得到其理想工作 辩论的另一方是形式主义者 他们认为 康托尔集合论 能让数学建立在绝对安全的逻辑基础之上
这一方的代表是德国数学家大卫・希尔伯特 这一方的代表是德国数学家大卫・希尔伯特 希尔伯特是个传奇人物 是一名很有影响力的数学家 希尔伯特是个传奇人物 是一名很有影响力的数学家 他几乎涉猎过数学里所有的领域 他差点抢在爱因斯坦前面提出广义相对论 他钻研出的全新数学概念 对于量子力学至关重要 他钻研出的全新数学概念 对于量子力学至关重要 他认为康托尔的工作极为高明 希尔伯特坚信 基于集合论的一套更正式、更严谨的数学证明体系 能扫清数学界一个世纪以来积累的所有疑难问题 大部分数学家都同意这样的说法 「康托尔建造了一个数学天堂 无人能把我们从中驱逐出去」 希尔伯特如是说 但1901年 博特兰・罗素指出 康托尔集合论里存在一个严重的问题 罗素想,如果集合能包含任何事物的话 那它也能包含其他集合,甚至包含本身 比如说,一个包含所有集合的集合,必须也包含它本身 一个包含所有「大于5个元素的集合」的集合,也必须包含它本身 甚至可以构造出包含所有「包含它本身的集合」的集合 但这径直导致了一个问题 有个集合R,它包含了所有「不包含它们本身的集合」 如果R不包含自身,那它就应该包含自身 但要是R
包含自身,那按照R的定义,它就不能包含自身 因此当且仅当R不包含自身时,R才能包含自身 罗素还找到了另一种「自指」悖论 他后来用了个理发师的比方来解释 从前有个村庄全部由成年男性组成 他们还有个关于胡子的奇怪法律 法律专门规定 村庄理发师必须也只能为那些自己不刮胡子的人刮胡子 村庄理发师必须也只能为那些自己不刮胡子的人刮胡子 但问题是,理发师自己当然也是村里的一员 而且他也是男士,谁为他刮胡子呢? 如果他不为自己刮胡子,那么理发师要帮他刮胡子 但他不能为自己刮胡子 因为一个理发师不能为一个自己刮胡子的人刮胡子 因此 理发师当且仅当不自己刮胡子时 才会为自己刮胡子 这就矛盾了 直觉论者见到罗素提出的悖论欣喜若狂 认为这恰好证明了集合论错得无可救药 不过策梅洛和希尔伯特学派的其他数学家们 对集合的概念加以限制 从而解决了这个问题 不再把「所有集合所组成的集体」称作一个集合 也不把「所有不包含其本身的集合组成的集体」称作一个集合 这样就不存在由于自指而产生的悖论了 希尔伯特和形式主义者取得了辩论的胜利 但是“自指”的幽灵并未消亡 快进到20世纪60年代 数学家王浩在研究 图中这样的四
边颜色不同的方砖 数学家王浩在研究 图中这样的四边颜色不同的方砖 规则是正方形两两接触的边必须同色 移动方砖时不能旋转或者翻面,只能平移 问题就是,给定任意一组方砖 可不可以判定它们能否密铺平面 也就是按规则无缝填合无限大的平面 事实是,给定一组方砖 你无法算出它们能不能无缝填合无限大的平面 这个问题是不可判定的 正如康威生命游戏中无法预知结局的图案一样 二者事实上描述的是同一个问题 这个问题究其本源正是自指 希尔伯特和其他形式主义者即将着手于这个问题 希尔伯特想打造一个新的数学证明体系 来保证数学大厦的地基足够稳固 「证明系统」的思想由来已久 可追溯至古希腊 证明系统始于「公理」 公理就是默认为正确的陈述句 比如两点确定一条直线 接下来用推理规则 通过公理构建出证明 推理规则就是由旧有的语句得出新语句的一套方法 这保证了推理的正确性 只要现有的命题为真,新命题也会为真 希尔伯特想要一种形式证明系统 也就是一种符号化的逻辑语言 + 一些严格的操作规则 也就是一种符号化的逻辑语言 + 一些严格的操作规则 逻辑和数学命题都能用这个系统的语言来描述 「如果你丢出一本书它就会下落」可以表
述为 A ⊃ B 「没有人能永存」则表述为这样 希尔伯特和其他形式主义者 想把数学公理 通过形式系统里的符号来表达 想把数学公理 通过形式系统里的符号来表达 并且将推理规则作为这些符号的操作规则 于是 罗素和阿尔弗雷德・诺斯・怀海德 在书里阐述了他们发明的一种形式系统 这书是在1913年发表的三卷大作《数学原理》 此书信息量巨大 总共近2000页,密密麻麻的全是数学符号 它用了762页的篇幅 才得到了1+1=2的完整证明 罗素和怀海德在下面干巴巴地写道 「上面的命题偶尔会用到」 作者起初打算写第四卷 但不出所料 他们实在是累到肝不动了 诚然,这些符号密密麻麻,很折磨人,但它们极为精确 它不像自然语言 它不让错误或者模糊的逻辑有任何可乘之机 更重要的是,它使得你能证明形式系统其本身的性质 希尔伯特对于数学有三大问题 ① 数学是否是完备的—— 是否所有真命题都能得到证明 ② 数学是否是一致的—— 是否不会产生悖论 比如说,如果你能同时证明出A和非A, 那问题就大了,因为你可以想证什么就证什么 ③ 数学是否是可判定的—— 是否存在一个算法,总是可以判断是否一个论断符合规定的公理。 希
尔伯特认为这些问题的答案都是“是”, 在1930年的一次重要会议上,希尔伯特就这些问题发表了激烈的演讲 他用一句概括了他形式主义梦想的话作为结束语 与那愚蠢的“不可知”,即我们不会知道正相反, 我们的口号应是:我们必须知道,我们必将知道 这句话也铭刻在他的墓碑上 但当希尔伯特发表这个演讲时,他的梦想已趋于破灭 就在前一天,在同一个会议的一次小会议上,24岁的逻辑学家库尔特·哥德尔 解释说,他已经找到了希尔伯特三大问题中的第一个问题——完备性的答案 答案是否定的 不存在完备的形式系统 重视此事的人只有约翰·冯·诺伊曼, 希尔伯特的前学生之一,他把哥德尔拉到一边问了几个问题 但在第二年,哥德尔发表了他关于不完备性定理的证明 而这一次,所有人,连希尔伯特都重视起来了 这就是哥德尔证明如何实现的: 哥德尔想用逻辑和数学 来回答关于逻辑和数学系统本身的问题 并且他沿用了数学理论体系的基本符号 之后他给每个符号都指派了一个编号 这就是知名的哥德尔数 所以说“非”的逻辑符号对应数字1 “或”对应数字2 “如果-那么”对应数字3 现在如果你用数字去表示符号,你怎么表示数字本身? 那“0”也有它的哥德尔
数——6 假设你想表示“1”,你就需要把这个后继符放到这个“0”旁边 0的后继就是1 假设你想表示“2”,那你需要用ss0表示2,以此类推 那么你可以这样表示所有的正整数 虽然麻烦,但有效 而这正是这个系统的重点 所以现在我们有了所有基本符号对应的哥德尔数和所有我们可能会用到的数字 我们可以开始写方程了 比如我们可以写“0=0” 那么这些逻辑符号有哥德尔数的表示:6,5,6 并且我们更可以创造一个新的卡片表示这个“0=0”方程式 实现的方法是取素数 从2开始,以每一个素数为底,方程里的每一个符号对应的哥德尔数为指数 那我们就得到了2的6次方乘以3的5次方 乘以5的六次方等于2.43亿 所以2.43亿就是整个“0=0”的方程的哥德尔数 我们可以为你能想象出的任何一组符号写下哥德尔数 这其实是一副无限大的牌 任何你想要写下来的序列中的一组符号 你都可以用一个唯一的哥德尔数来表示 这个哥德尔数的美妙之处在于你做一个整数分解 你就能确切地知道这张卡片上到底有什么符号 所以在这整副牌中,有真命题,也有假命题 那你怎么证明某命题为真? 这你就需要用到公理了 公理也有自己的哥德尔数,它们以同样的方式
生成 这里有一条公理,上面说 0不是任何其他自然数的继数 这样说的原因是整个系统中不存在负数 所以任何自然数的继数不可能为0 那我们把这条公理放在一边 接下来我们可以用0替代x 说一不等于零 我们就创造了一个证明!这是我能想到的最简单的证明 这表明1并不等于0 现在这张证明1不等于0的卡 有它自己的哥德尔数 我们计算这个哥德尔数的方法,和我们之前的办法一样 我们用素数,然后以2为底公理作为指数 乘以以3为底“1不等于0”为指数 我们得到了一个巨大的数字 如果全部计算出来的话,应该有7300万位 我用指数表示法表示出来,把它放在这 正如你所看到的,这些数字变得非常大 你可能想要用一个字母去命名 那我们可以说这个是哥德尔数“a” 这是哥德尔数“b”,哥德尔数“c”,等等 哥德尔费了这么大劲才找到这张卡 上面写道:没有哥德尔数“g”语句的证明 关键是 这张牌的哥德尔数就是“g” 所以这个语句的真正意思是 这张卡是不可证的 在我们的无限卡组中没有一张卡可以证明这张卡 现在想一下,假设这是错误的并且也有一个证明 那么你刚刚证明的就是: 没有证明 你就陷入了矛盾之中 那就意味着数学系统是不一致的
另一种可能性是:没有哥德尔数“g”语句的证明 但这意味着这个数学系统有一个不可证的真命题 那你的数学系统就不具有完备性 这就是哥德尔的不完备性定理 这就是他如何证明任何基本的数学系统都符合基本算术定理 总是存在无法被证明的语句 电视节目《办公室》中有一句台词,呼应了哥德尔证明的自指悖论 Jim是我的敌人 但这也说明Jim是他自己最大的敌人 而且敌人的敌人就是我的朋友 那Jim实际上也是我的朋友 但因为他是他自己最大的敌人 我朋友的敌人是我的敌人,理所当然Jim也是我的敌人 可是。。 哥德尔不完备定理表明 「命题为真」并不意味着「命题可证」 希尔伯特错了 总会有真命题是没办法证明的 希尔伯特转而寄希望于证明数学的「自洽性」 希尔伯特转而寄希望于证明数学的「自洽性」 也就是无矛盾 但哥德尔接着发表了第二条不完备定理 他证明了 数学里任一自洽的形式系统 都无法证明其本身的自洽性 把哥德尔的两条不完备定理放到一起 我们期望的最理想的数学系统 也只能 是一个「自洽」但「不完备」的系统 并且这样的系统也无法证明本身自洽 你所用的系统将来总会冒出矛盾之处 揭示其本身的不自恰 你所用的系统将来总
会冒出矛盾之处 揭示其本身的不自恰 现在希尔伯特的构想只剩第三个 也是最后一个大问题 可判定性 是否有算法 对于任一陈述句 都能判定它能否从公理推出来 是否有算法 对于任一陈述句 都能判定它能否从公理推出来 1936年 艾伦・图灵找到了解答此问题的思路 但要完成证明 他必须得发明现代的计算机 当时的计算机并非“机器” 而是负责繁冗计算的人 女性居多 图灵想象了一种纯机械的计算机 图灵希望这机器的能力足够强 你想得到的计算它都能做 但这机器的原理又够简单 你可以根据其操作来推理 他提出了这样一个机器: 将一条无限长的纸带作为输入 纸带由方格组成 方格里包含 0 或 1 机器有一个读写磁头 一次可以读一个数位 然后可以执行仅有的几种操作之一 用新值覆盖掉原值 磁头左移、右移 或是直接停机 「停机」表明程序运行至终止状态 图灵机内含一系列指令 可以把指令想象成一个流程图 它规定了 根据机器内部的状态与输入的数位 应执行什么操作 可想而知 把相同的指令输入另一台一样的图灵机里面 其操作会跟原先那台图灵机的操作毫无二致 原理听起来挺简单 但图灵机有无限大的内存与程
序 这意味着 只要给够时间 它就能执行任何一个能跑起来的程序 小至加减法 大至整个 YouTube 的算法 现代计算机能做的一切东西 图灵机都能做到 这让图灵机在解答希尔伯特的可判定性问题时 大有用武之地 这让图灵机在解答希尔伯特的可判定性问题时 大有用武之地 图灵机停机时 程序结束运行 纸带即为程序的运行结果 但图灵机也有可能永不停机 比如说陷入了死循环 对于给定的输入纸带 有没有办法事先预测程序能否停机? 对于给定的输入纸带 有没有办法事先预测程序能否停机? 图灵意识到 停机问题与可判定性问题太相似了 图灵意识到 停机问题与可判定性问题太相似了 要是自己有办法预测图灵机能否停机 那也就有办法能判定命题能否由公理得出 举个例子 要想求解孪生素数猜想 只需要在图灵机上写个程序: 从公理开始 用推理规则 构造出所有能一步推出的定理 从公理开始 用推理规则 构造出所有能一步推出的定理 从公理开始 用推理规则 构造出所有能一步推出的定理 然后构造出再推一步得到的所有定理 层层构造下去 然后构造出再推一步得到的所有定理 层层构造下去 图灵机只要一生成新定
理 就检查它是否证明了孪生素数猜想 如果是 则停机;反之亦然 所以 只要能解决停机问题 就能把诸如孪生素数猜想之类的未解难题统统扫清 就能把诸如孪生素数猜想之类的未解难题统统扫清 所以图灵说 不妨假设我们搞出来了机器 h 它能判定任意图灵机对于任一特定输入是否会停机 把程序代码和输入纸带统统放入 h h 会模拟计算过程 最后输出结果说明程序是否会停机 先不用管 h 的原理是啥 只要知道它总能正确运行 正确给出结果 我们可以往 h 机器上增添部件 有个部件只要收到 h 的输出结果为「停机」 它就会跑个死循环 另一个部件只要收到 h 的输出结果是「不停机」 它就立刻停机 不妨把这个新的机器称为 h+ 我们可以导出这个机器的程序 把 h+ 的代码同时作为程序和输入纸带放入 h+ 会发生啥? 现在,(h+ 内部的)h 就会模拟「给 h+ 输入了 h+ 会发生什么」 h 差不多是要判定 在此特例下 把程序输入程序本身会有怎样的行为 如果 h 的结论是 h+ 永不停机 那 h+ 会立刻停机 如果 h 的结论是 h+ 永不停机 那 h+ 会立刻停机 如果 h 觉得 h+ 会停机 那 h
+ 就会陷入死循环 如果 h 觉得 h+ 会停机 那 h+ 就会陷入死循环 不管 h 判断是停机还是永不停机 看起来结果都是错的 这产生了矛盾 唯一合理的解释是 根本不存在 h 这样的机器 没有通用的办法能判定图灵机对于给定的输入是否会停机 没有通用的办法能判定图灵机对于给定的输入是否会停机 这证明了数学是「不可判定的」 不存在一个算法能对每一个命题正确判定其是否由公理推出 不存在一个算法能对每一个命题正确判定其是否由公理推出 所以像孪生素数猜想之类的问题可能是不可解的 说不定 我们永远没法知道 是否有无限个孪生素数 不可判定问题还会出现于物理学中 在量子力学中,多体系统一个最重要的性质是 基态和第一激发态的能量差 这就是所说的光谱间隔, 一些体系有比较大的光谱间隔,一些则没有间隔 它们有有连续的能级直到基态 在低温下,无间隔量子体系可以进行相变 但有间隔体系不能(相变)。 它们没有足够的能量克服光谱间隔 但是确定一个系统是有间隔还是无间隔 是一个棘手的问题, 直到2015年,数学家才证明, 通常情况下,光谱间隔问题是不可判定的, 引用一下(论文)作者:“即使完美描述了两个粒
子之间的微观相互作用, 通常也不足以推断宏观性质” 现在,我们回忆一下,图灵设计的机器尽可能的强大 现在最好的计算系统是那些可以做一切图灵机可以做的机器 这也被称作图灵完备性,有很多图灵完备系统 尽管它们很强大,但是这些图灵完备系统都有 类似停机问题的缺陷 系统的不可判定性 王氏砖是图灵完备的, 它的停机问题体现于它是否能够铺满整个平面 复杂量子系统是图灵完备的, 它们的停机问题就是光谱间隔的问题 生命游戏是图灵完备的, 它的停机问题其实就是它会不会停下来 还有很多其他的例子,比如航空售票系统, 万智牌,PPT(见av23357397)或者Excel表格 几乎所有现有的编程语言是设计成图灵完备的, 理论上你只需要一种就够了 因为你可以在任何图灵完备的系统上编程任何东西 所以在生命游戏里是可以搞出一个图灵机的 因为生命游戏本身是图灵完备的 它应该可以模拟自己,也确实如此 这就是一个在生命游戏中 运行的生命游戏 希尔伯特的理想真正留给我们的 是当今的一切计算设备 哥德尔在生命的后期因精神问题备受折磨 他坚信有人试图向他投毒 他拒绝进食, 最终饿死了 希尔伯特于1943年去世 他的墓志铭是
1930年来的口号 「我们必须知道,我们将会知道」 现实是我们不知道, 我们可能无法知道 但是在尝试的过程中,我们发现了新东西, 发现了改变了世界的新东西 图灵将他关于对于计算的想法在二战中付诸实践 带领团队在布莱切利园建立了真的计算机器,为同盟国破译纳粹的密文 据一项研究,图灵和他的同事一起破译密文, 将战争缩短了2-4年 二战结束后,依据图灵的设计,图灵和冯・诺伊曼设计了 第一台可编程电子计算机 但在此之后图灵没活多久了 在知道图灵是同性恋以后,带英政府在1952年判处他严重猥亵 他的安全权限被剥夺,并被迫服用荷尔蒙, 他于1954年自杀 图灵改变了世界, 他被公认是计算机科学最重要的创始人 所有的现代计算机都源于他的设计 而图灵的想法是源于对希尔伯特问题 数学可判断性的思考而产生的图灵机 所以图灵的解密机还有所有现代计算机 都诞生于关于自指的奇怪悖论 在数学世界中有一个黑洞, 我们永远无法准确的获知全部 总有些真命题是我们无法证明的 你也许会觉得数学家会发疯 进而导致数学界的崩溃, 但是,在思考这些问题时,我们改变了对无限的定义, 改变了世界大战的进程 还直接促进了你正在看这个视
频的设备被发明 米娜桑,这个视频是brilliant.org 赞助的, 里面有一堆互动课程和小测试,深入探究了 诸如数学,物理,计算机科学等话题 如果你坚持看到了这里 你肯定也是超爱brilliant的那类人 我已经上了它们的逻辑学的课, 真的引发了我很多思考 问题随着你的理解由浅入深 问题随着你的理解由浅入深 我就爱这个 我喜欢它引导你, 而不是直接告诉你,让你面对逐渐复杂的问题 我最终感觉上都是自己解决这些问题的, 其实就是我自己解决的 他们精挑细选的问题, 在我卡住时有益的提示和解释非常有用 本期视频中有很多事我想提到, 但是囿于时长--已经半个多小时了 如果你想继续深入这个想法, 我很推荐你康康数字理论和计算机科学基础 我很推荐你康康数字理论和计算机科学基础 brilliant给前两百位注册者打八折 去brilliant康康, 我会在简介放个链接 谢谢brilliant的赞助, 也感谢你们观看

Comments