作者：silverxz

人们对数学中的猜想与解决猜想的故事有一种奇妙的热衷。诸如哥德巴赫猜想与陈景润、费马大定理与 Wiles、代数方程根式解与 Abel 和 Galois……这些例子已经深入到启蒙教育。小孩子或许甚至读不懂这些问题本身的陈述，但他们喜欢阅读这样的悬而未决的猜想被一位传奇解决的故事，就像勇者与恶龙的故事一样。Hilbert的名声大概也是这样传到普通人耳中的：

David Hilbert (1862-1943) 是那个时代最负盛名的数学家。1900 年，Hilbert 汇集了 23 个当时悬而未决的数学问题。这些问题中，有些问题比较明确（比如第 8 问题就是 Riemann 猜想 ），有些则不是具体的题目，而是一个研究方向甚至一个小领域，里面可以有一大堆问题。后来这些问题就有了公认的统称：Hilbert 的 23 个问题。

大卫·希尔伯特

上述内容也算是科普中的小热门，但许多科普到此停步。毕竟这是 1900 年的前沿数学，许多问题今天还没解决呢。更何况，大部分人学习的数学大多是 18xx 年甚至更早的数学，是 Newton、Euler、Gauss、Cauchy、Riemann……这些怪物发展出来的数学。这意味着，想要理解 Hilbert 的 23 个问题在讲什么对于大部分人来说都有难度，更别说了解它们是如何解决的。

好在，这里面的确有一些问题是我们触手可及的。Hilbert 第十问题勉强算是这样的一个问题。我们先来看看这个问题说的是什么。Hilbert 当年对这个问题的陈述大致可以翻译如下：

Hilbert 第十问题

给定一个丢番图方程，带有任意数量的未知数：设计一个过程，在有限次运算内确定这个方程是否有整数解。

什么是丢番图方程？很简单，就是整系数多变量多项式的方程。比如，，或者再复杂一点，。只要是多项式，系数都是整数，就行。读者可以发现，丢番图方程蕴含了许多我们熟知的东西。比如是代表勾股数的丢番图方程，而则是费马大定理对应的丢番图方程。由此足可见，这个问题很大，表述简单但非常复杂，也很有价值。

但真正值得关注的点是后半句：设计一个过程(process)，在有限次运算内确定……

有些读者可能有些奇怪。为什么 Hilbert 不直接说，设计一个「算法」？因为 1900 年的 Hilbert 还不知道什么叫算法。虽然他的头脑里已经有一些雏形，比如这个“过程”应该在有限次运算内停止，这样的运算应该是“机械化”的……但他毕竟还不知道如何数学地刻画计算与算法的概念——那是 Turing 他们的工作，而 Turing 在 12 年后才出生呢。

对于 Hilbert 来说，他更倾向于默认这样的过程存在（他没有问是否存在，而是要求我们“设计”出来）；直到 Turing 的时代我们才知道，并不是所有问题都能设计出算法，而 Hilbert 第十问题的答案也就不出意外地是：不存在 Hilbert 想要的算法。

这就是为什么我会说，这个问题“勉强”是我们触手可及的。如果你已经用过计算机，写过程序，大致了解图灵机是怎么回事，那么你已经站在了巨人的肩膀上，见到了 Hilbert 没有见到的风景，离搞懂这个问题怎么解决也就不算太远了（虽然也不太近，所以说“勉强”）。另一方面，当你用程序解决了很多问题，那么你难免会好奇一个“程序解决不了的问题”长什么样，Hilbert 第十问题就是这样的实例。

这也是本文大致的读者定位：普通计算机本科生，或者对算法和计算有大致的朴素认知，因为本文的初稿是我本科《计算理论》课程的大作业。当然，我会将它进一步细化，并尽量降低门槛。我会尽量不回避关键步骤，写得足够深入；但仍然是科普，而非讲义。

不过，如果你不具备本文需要的一些基础知识，也不妨碍你继续阅读下一篇内容：Hilbert 第十问题的历史，当故事看就可以了，算是一份软科普。而历史之后的证明部分会默认你知道什么是图灵机（最好还知道递归集、递归可枚举集的概念），如果你不知道，也可以花一点点时间看别的科普或教材补充一下，有计算机基础这些就都不困难。如果实在有需要，我也会考虑补充一份附录，让基础没有那么扎实的读者回顾一下必要的基础知识（但我猜应该没有太多人看，所以我大概率会咕咕）。

在本文之前，中文互联网几乎只有卢昌海先生的一篇文章对 Hilbert 第十问题的历史做了较为详细的介绍，但也没有尝试介绍证明部分。我的这篇文章一方面是总结、记录一下自己的学习理解，另一方面也是（斗胆）填补这方面的空白，以我的角度叙述相关的历史、并总结其中的证明。实际上我在写作时，尽量没有读卢昌海先生的文章，而是参考原始材料，避免陷入某种思维定式；但我仍然需要向此文致谢，并附上文章链接供读者参考。