一个被证伪的数学难题如何点燃计算革命？希尔伯特之问与图灵的回答

luyuanhong

一个被证伪的数学难题如何点燃计算革命？希尔伯特之问与图灵的回答

原创  歪睿老哥  歪睿老哥   2025 年 07 月 02 日 20:00  北京

第一幕：1900 年的两次学术会议

1900 年 8 月 6 日，巴黎。

第二届国际数学家大会。

38 岁的德国数学家大卫·希尔伯特发表了一场演讲。

奇怪的是，这篇演讲中没有提出新的证明。

这不是因为希尔伯特能力不行，作为开创哥根廷学派的数学家，希尔伯特在数学上的贡献有目共睹。

希尔伯特解释说，数学的生命力，系于那些“最活跃、最关键、最有影响力”的未解之谜。

所以他并非展示一项成果，而是抛出了一份战书。

23 个数学问题！

这 23 个问题，是他从数学的广阔疆域中精准提炼的结晶，触及了当时几乎所有数学核心领域。

从此，“希尔伯特问题”之名响彻寰宇。

解决它们，成为几代数学家的至高追求与无上荣光。

而当然这 23 个问题，就比同年在英吉利海峡对岸的伦敦由开尔文勋爵提出的“两朵乌云”的知名度低多了。

在同一年，也就是 1900 年的皇家科学会上，开尔文勋爵宣告了物理学大厦的落成。

"……物理学的大厦已经落成，所剩下的只是些修饰工作，动力学理论肯定了光和热是运动的两种方式，然而，在这美丽晴朗的天空，却被两朵乌云笼罩，显得黯然失色。"  （'The beauty and clearness of the dynamical theory， which asserts heat and light to be modes of motion， is at present obscured by two clouds.'）

物理学后来的发展历史表明，正是 20 世纪初的这两朵小小的乌云，酿成了一场大风暴。

第一朵乌云：迈克尔逊-莫雷实验那诡异的“零结果”，刺穿了“以太”介质存在的幻梦。

第二朵乌云：黑体辐射那无法调和的“紫外灾难”，正无情地暴露出经典理论在微观尺度上的崩塌。

第二朵乌云导致量子力学的诞生。

第一朵乌云导致相对论的爆发。

开尔文勋爵的这场演讲成了整个 20 世纪物理学起点。

而同样历史的巧合，由同一年希尔伯特的提出的 23 个问题的其中一个问题，也同样间接导致了 20 世纪计算革命的爆发。

第二幕：可判定性问题

希尔伯特的这 23 个问题中，最著名应该就是第八个问题：聚焦素数分布规律。

包含三大经典猜想，

第一是黎曼猜想（Riemann Hypothesis），证明 ζ 函数的所有非平凡零点的实部均为 1/2 。

第二是哥德巴赫猜想（Goldbach Conjecture），证明任意大于 2 的偶数可表为两素数之和（“1+1”）。

第三是孪生素数猜想（Twin Prime Conjecture），证明存在无穷多对相差 2 的素数。

我国数学家陈景润主攻的哥德巴赫猜想，证明了证明“1+2”（偶数=素数+半素数），为迄今最佳结果。

而另一位近年来著名数学家张益唐则主攻孪生素数猜想，证明存在无穷多对素数间隔不超过 7000 万，方法一出，很快被学界突破到，间隔已缩至 246 。

当然，引发计算革命的不是第 8 个问题。而是第十个问题

与第八个问题相比，

第十个问题就有些默默无闻。

第 10 问题是什么？

能否设计一个算法，判定任意整系数多项式方程（丢番图方程）是否有整数解？

例如：

x^2 + y^2 = 5 有解（x=1, y=2）

x^2 + y^2 = 3 无整数解

这个问题看起来是不是比第 8 个问题简单多了。

似乎读者们也可以上手试试。

大家是不是和我一样，有一种感觉。

和黎曼猜想，哥达巴赫猜想，孪生素数猜想相比，这个第 10 个问题有些简单。

也许希尔伯特也是这么觉得。

于是，在 1928 年，希尔伯特提出这个问题 28 年后。

多说一句，希尔伯特的第十个问题在这 28 年也没有人解决。

希尔伯特又给这个第十问题上了强度，把第十个问题做了引申。

是否存在一种通用方法，能在有限步内判定任意数学命题的真假？

希尔伯特把这个问题总结为：数学是可判定的吗？

也叫作可判定性问题（Entscheidungsproblem）。

而能否设计一个算法，判定任意整系数多项式方程（丢番图方程）是否有整数解？ 这个问题就是可判定性问题的一个具体例子了。

希尔伯特的“可判定性”之问，充满了哲学意味和终极挑战。

这个问题，大家也可以自己头脑风暴一下。

看如何才能解决希尔伯特的这个问题。

首先，什么是可判定？

简单说，就是存在一个自动化的、机械式的过程，对于输入的任何数学命题，都能在有限时间内给出明确的“是”（真）或“否”（假）的答案。

现在是不是有些思路了。

不知道大家有没有思路，有个年轻人已经有了思路。

但是在希尔伯特提出这个问题 8 年之后，有个年轻人把目光投向了这个难题。

他的头脑中的闪念，决定构造一个思想的工具来尝试解决这个问题。

构造思想工具是常用的解决问题的手段，比如薛定谔的猫，爱因斯坦的光速火车。

和他们一样，这个年轻人的思想实验也被载入科学史册。

第三幕：图灵的机器

在 1936 年的一个深夜，伦敦国王学院的一间房间仍然亮着灯。

一个年轻人坐在桌前，他消瘦的身影被柔和的灯光投射在墙上，形成一个沉思的剪影。桌上的草稿纸被他涂改得满满当当，各种复杂的公式和图形交织在一起，像是一幅未完成的拼图。

年轻人的眉头紧锁，显然正在经历一场思维的激战。突然，他的眼神中闪过一丝亮光，像是捕捉到了什么重要的灵感。他迅速拿起笔，开始在一张新的草稿纸上疾书。他的笔尖在纸上飞舞，像是在编织一段魔法咒语。当最后一个符号落下，他长长地呼出一口气，仿佛刚刚完成了一场心灵的马拉松。

他不知道知道自己已经迈出了历史性的一步，这将极大的改变计算机科学的未来。

这个年轻人，就是瞄准希尔伯特的数学的可判定性的问题进行研究。

不同的是，他打算另辟蹊径，制造一种机器来解决这个可判定性的问题，这个机器就是日后在计算机领域最为出名的机器，图灵机。

而这个年轻人正是艾伦·图灵，而这台机器的名字也以他的名字命名。

顺便说一句，虽然这台机器从来没有造出来，但这一定也不损害图灵这个思想实验的伟大。

1931 年，十九岁的图灵进入剑桥大学国王学院，开始了他的学术生涯。

剑桥大学国王学院由亨利六世国王亲自设计并下令创办，以自由和独立精神著称而著称。

国王学院师生们曾经抵制过国王对院长的人选任命，而他们居然成功了，而这位被国王物色并打算任命为院长的人选，就是大名鼎鼎的科学家牛顿，看来即使是牛顿这样声名显赫的大佬，也不一定获得师生的青睐。

也正是在国王学院，艾伦.图灵深入研究数学和逻辑学，在这里，他接触到了希尔伯特的问题。

1936 年，图灵发表了一篇题为《论可计算数，及其在判定性问题上的应用》的论文。（On Computable Numbers, with an Application to the Entscheidungsproblem）。

Entscheidungsproblem：德语，判定性问题。

在这篇论文中，他提出了一种名为“A-Machine”或“自动机器”的假设计算装置，这就是我们现在所说的“图灵机”。图灵设计这种机器的初衷就是为了解决希尔伯特的判定性问题。

什么是可判定的问题？

“可判定的”是指对于某个特定的问题或语言，存在一种算法或程序能够在有限的时间内给出明确的答案或判定结果。对于数学语言，如果存在一种方法或程序能够让机器自动地判断某个数学命题的真假，并将结果显示出来，那么这个问题就可以被认为是可判定的。

举例来说，如何证明大于 1 的整数都可以表示为质数的乘积。

为了证明这个问题，可以使用数学归纳法。

首先，我们知道 2 是最小的质数，因此 2 可以表示为质数的乘积，即 2=2 。

接下来，我们假设对于所有大于 1 且小于等于 n 的整数，它们都可以表示为质数的乘积。

现在，我们考虑 n+1 这个整数。有两种情况：

1）  如果 n+1是质数，那么它本身就是一个质数的乘积，因此得证。

2）  如果 n+1 不是质数，那么它可以表示为两个大于 1 且小于 n+1 的整数的乘积，即 n+1=a×b 。由于 a 和 b 都小于 n+1 ，根据归纳假设，a 和 b 都可以表示为质数的乘积。因此，n+1也可以表示为质数的乘积。

综上所述，无论 n+1 是质数还是合数，它都可以表示为质数的乘积。因此，根据数学归纳法，我们证明了大于 1 的整数都可以表示为质数的乘积。

那么问题判定为真。

图灵机的目标就是通过机器最终判断这个问题是不是最终可以地得到真假的判断。

现在我们回到希尔伯特的判定性问题本身，那么所有的问题都是可判定性的吗？

他设想了一个场景，其中即图灵机根据纸带上的指令进行运算。然后，他提出了一个问题：我们能不能判断这台机器会一直不停地计算（也就是陷入死循环），还是会在某个时候停下来并给出结果？

为了解释这个问题，他举了一个简单的例子。想象一下，在纸带上的 A 点写着“移动到 B 点”，而在 B 点又写着“移动到 A 点”。如果计算机按照这些指令操作，它就会在 A 点和 B 点之间来回移动，永远停不下来。这就是一个死循环的例子。

图灵想知道的是，有没有一种方法能够判断计算机是否会遇到这种情况。因为如果计算机陷入了死循环，它就无法给出答案或完成计算任务，这在实际应用中是个大问题。所以，这个问题非常重要，也是图灵研究的关键部分。

为了解决死循环的问题，图灵想出了一个办法来判断他的机器是否会停机。他认为，如果能再造一台图灵机来检测第一台机器就好了。这台新的机器可以观察第一台机器的运行情况。如果第一台机器一直不停机，那么第二台机器就会停下来，并告诉我们“不停机”；如果第一台机器停机了，第二台机器就会继续运转。

但是，这里有一个有趣的问题。如果第二台机器也观察自己，看看自己会不会停机，会发生什么呢？

图灵仔细想了想，发现了一个奇怪的事情：如果第二台机器发现自己永远不会停机，那么它就会停机，并告诉我们“不停机”；但如果它发现自己停机了，那它就会一直运转下去。

● 若机器能够判定停机 → 根据定义，机器应死循环 → 矛盾！

● 若机器判定不停机 → 根据定义，机器应停机 → 矛盾！

这在逻辑上是不可能的，因此图灵认为:有些问题是计算机永远无法解决的——我们无法判断某些图灵机是否会停机。

虽然图灵机证明了，数学的可判定问题逻辑上不可能。

图灵的研究结果表明，有些数学问题是计算机无法解决的，与计算机的运算能力、运算速度和内存容量无关。

第四幕：图灵机的计算方式

那么图灵机如何来计算的？

图灵机由读写头、无限长的带子和控制器三部分构成。     



读写头，作为图灵机的“眼睛”和“手”，负责从带子上读取数据和写入数据。它是图灵机与外部世界交互的桥梁，通过读取带子上的信息，将外部输入转化为机器内部可处理的信号；同时，将处理后的结果再通过写操作反馈到带子上，实现了信息的输入与输出。

无限长的带子，在图灵机的设计中扮演了存储器的角色。这一设计巧妙地解决了数据存储的问题，使得图灵机能够处理任意长度的数据。带子的无限长度赋予了图灵机巨大的数据存储潜力，为复杂计算提供了可能。

控制器，作为图灵机的“大脑”，相当于计算程序，控制着整个计算过程。它根据当前的状态和读写头读取的数据，决定下一步的操作，从而实现各种复杂的计算任务。控制器的存在使得图灵机具有了通用性，能够模拟任何可计算的函数。

正是这三部分的协同工作，使得图灵机在理论上能够计算任何可以计算的函数，展现出其强大的计算能力。

然而，实际的计算机受限于物理条件，存储空间并非无限。因此，在实际应用中，计算机需要对连续的对象进行离散化处理，以适应其有限的存储空间。这种离散化处理是计算机科学中的一个重要概念，也是计算机能够处理各种复杂问题的基础。、尽管如此，图灵机的理论模型依然为计算机科学的发展奠定了坚实的基础，其深远影响至今仍在延续。

图灵机并没有制造出来，但是通用图灵机已成为世界上所有电子计算机的理论蓝图。在当今这个数字化时代，我们几乎每个人都离不开计算机。无论是在办公室、学校还是家中，计算机都是我们完成各种任务、获取信息和娱乐的主要工具。

人类一直都有用机器来代替人工解决问题的渴望。而图灵就是那个手握着计算机时代钥匙的人。

图灵的 A-Machine（图灵机）和薛定谔的猫，以及爱因斯坦的追光实验一样都是伟大的思想实验。

虽然图灵机没有造出来，这个思想却成了计算机的先驱。

可判定性问题被证伪了。

但是希尔伯特凭借超强的能力把哥廷根大学建成全球数学中心，并领衔大名鼎鼎的哥廷根学派。

1926 年，希尔伯特迎来以为年轻的数学助手，他的名字在当时无足轻重。

但 1933 年纳粹上台后，德国的犹太裔学者遭清洗，学派瓦解。

希尔伯特悲叹“哥廷根已无数学”。

他的这位助手则赴美开辟新事业。

十年以后，希尔伯特的这位曾经的助手，把图灵机从一个思想实验变成了现实，建立了第一台计算机。

这个曾经的助手就是冯诺依曼，现代计算机之父。

而此时希尔伯特已经去世，他从来没有想到，自己的数学之问，恰巧开启了信息革命的序幕。

歪睿老哥

ysr

不需要数值计算的哥德巴赫猜想和孪生素数猜想的证明（都不需要计算了还用啥高等数学啊？）：