希尔伯特第十问题：丢番图方程没有通用判据

破除误解：这不是哥德尔不完备的复述#

哥德尔不完备定理 说的是：足够强的形式系统里，有真命题无法在系统内证明。第十问题说的是：有一个具体的数论判定问题，没有任何算法能对所有实例给出对错。两者都打击希尔伯特纲领里“一切数学问题终将可机械解决”的乐观，机制不同。不完备性可以与大量可判定片段共存；第十问题给出的是一个从输入多项式到“有根/无根”的不可判定语言。

第二个误解，是把“不可判定”读成“每一道具体方程都永远不知道”。对许多固定方程，人仍然能证明它有根或没有根。不可判定的是统一程序。给定一条方程，你仍可尝试因式分解、局部—整体原则、或计算机辅助搜索；你不能指望有一台机器，吃进任意系数，保证停机并说真话。

第三个误解，是把它和 P vs NP 混成同一个“难”。P vs NP 问的是：可在多项式时间验证的东西，能否在多项式时间找到。第十问题已经在可计算性的层级上失败——不是慢，是没有算法。复杂度类是在“算法存在”之后才开始数步数。

希尔伯特要的手续，后来被翻译成什么#

用现代语言：输入是 $f \in \mathbb{Z}[x_1,\ldots,x_n]$，输出是它在 $\mathbb{Z}^n$ 上是否有零点。n 不固定。丢番图集是能被一多项式“存在量化”刻画的集合：

$$a \in A \iff \exists x_1,\ldots,x_m\ (p(a,x_1,\ldots,x_m)=0).$$

Davis 在 1950 年代猜想：可枚举集都是丢番图集。若猜想成立，再取一个不可判定的可枚举集，第十问题就失败。工作于是变成：用多项式模拟计算。

1961 年，Davis、Putnam 与 Robinson 证明：每个可枚举集都有指数丢番图表示——允许指数出现在方程里。剩下的瓶颈，是 Julia Robinson 的假设：若能找到一个丢番图关系，增长足够快（指数级），指数就能被多项式吸收。1970 年 Matiyasevich 证明，斐波那契数的关系 $y=F_{2x}$ 是丢番图的。JR 假设落地，指数可被消去，Davis 的猜想变成定理。

这条链的教学价值，在于它不是一个人的灵光。Davis 给出战略，Robinson 给出增长条件，Putnam 参与指数阶段，Matiyasevich 用斐波那契补上算术。否定解是一份二十年的构造，不是一句“图灵停机问题因此显然”。停机问题提供的是不可判定可枚举集的存在；把计算塞进多项式，才是数论这边的工作。

定理到底禁止了什么#

MRDP 有一个更强的形状：存在一个固定的多项式 $p(a,x_1,\ldots,x_n)$，使得“$a$ 属于某不可判定可枚举集”当且仅当该多项式在 $x$ 上有根。于是连带一个参数的方程族都没有判据。后来还出现“未知数个数可以压到很小”的加强：存在一个固定的、未知数不太多的方程形状，已经足够编码任意可枚举集。课堂里不必记住最小未知数的世界纪录；要记住的是：困难不是来自“未知数太多”，而是来自多项式可以模拟计算。

整数环上的否定解，不自动搬到每一个环。有理数上的第十问题（$\mathbb{Q}$ 上是否有根）在此后几十年仍开放。实数与复数上，塔斯基等人给出的是另一套可判定理论。对象必须带着论域：$\mathbb{Z}$ 上没有算法，不等于“数论没有算法”。把 1970 年的结果写成“方程都不可判定”，会把论域擦掉。

对数学实践的影响是选择性的。椭圆曲线、二次型、低次少变元，仍然有结构可用。通用判据的消失，把研究推向分类：哪些子类可判定，哪些继承了全部可枚举集的困难。这与复杂度理论在 NP 完全出现之后的分工相同——先证明一般情形无望，再在结构上找岛屿。

斐波那契怎样把指数变成多项式#

Julia Robinson 要的不是任意快的增长，而是一个可用多项式方程刻画的、增长足够快的关系。斐波那契数列满足线性递推，看起来很“多项式友好”，但它的下标落在指数位置上。Matiyasevich 证明 $y=F_{2x}$ 是丢番图的，等于给出一座桥：指数丢番图表示里的指数，可以被这座桥替换成多项式约束。

构造很长，课堂只需抓住结构。先有可枚举集的指数表示（Davis–Putnam–Robinson，1961），再有一座增长桥，指数被消去。没有桥，第十问题仍停在“几乎”上。有了桥，Davis 猜想关闭。把 1970 年写成一个人突然想到斐波那契，会把二十年的劳动分工擦掉。

丢番图集的例子可以很具体。偶数是丢番图的：存在 $y$ 使 $x=2y$。素数集合可枚举，MRDP 之后它必须也是丢番图的——即使显式多项式又长又丑。存在性证明不自动给出好看的方程。这正是定理的风格：它保证编码存在，不保证你愿意把方程写在黑板上。

未知数个数后来被压到很小的固定数目。世界纪录会变，教学不必追。要点是：困难不来自“变元太多”，来自多项式算术已经能模拟寄存器和停机。少变元的方程仍然可以编码任意可枚举集。

希尔伯特 1900 年的表述甚至没有使用“算法”一词。他要的是一种有限次运算后必然到达的办法。图灵、丘奇把这话收成可计算函数之后，否定解才有精确定义。用 1970 年的话回看 1900 年的题面，必须承认翻译。翻译不是扭曲：他要的确实是对所有输入都有效的手续；MRDP 证明的是手续不存在。

具体方程仍然可以非常硬，却并非因为第十问题。费马方程在 $n>2$ 时没有正整数解，靠的是椭圆曲线与模形式，不是不可判定性。把费马大定理的困难说成“反正方程都不可判定”，会把两个世纪的算术几何一笔勾销。第十问题禁止的是通用机。它不给任何一道名题颁发“不必再证”的证书。

有理数点问题（希尔伯特第十问题在 $\mathbb{Q}$ 上）至今开放，说明论域一变，模拟计算的编码可能失效。整数的离散与可除性，是把递归论塞进多项式的材料。有理数更“密”，同样的编码不一定走得通。开放，不等于“大概也可判定”。它只说明：1970 年那一刀切的是 $\mathbb{Z}$，不是所有人们会写方程的地方。

希尔伯特的判定问题（Entscheidungsproblem）问的是一阶逻辑的普遍有效性，被丘奇与图灵在 1936 年否定。第十问题是数论里的一个具体语言，不是把判定问题再说一遍。两者都让“一切数学问题终将可机械解决”失败，失败点不同。一个发生在逻辑有效性，一个发生在整系数多项式的整数根。把它们收成同一句“数学不可判定”，会把对象擦掉。

后来的加强表明：存在固定的多项式形状，参数一变就能编码任意可枚举集。于是“这一族方程有没有根”已经不可判定，不只是“任意方程”这个更散的问题。课堂不必记住未知数最少的世界纪录。要记住的是：一旦多项式能模拟计算，变元再少也挡不住编码。

若干代数整数环上的第十问题已被证明不可判定；有理数仍然开放。Poonen 的综述把这条分界写得很清楚。开放问题不是对 1970 年结果的削弱。它标明模拟计算依赖哪些环论性质。没有那些性质，同样的编码走不通，问题就换了一个。

停机问题提供不可判定可枚举集的存在。第十问题的数论工作，是把那类集合写成“某个多项式有整数根”。归约方向是：若你有第十问题的算法，你就有了判定该可枚举集的算法。既然后者不可能，前者也不可能。教学上容易说反：先看见难方程，再宣称停机。正确顺序是先有计算的不可判定性，再把它编码进多项式。没有编码，停机问题停在逻辑与递归论里，进不了丢番图方程。

Davis 猜想在被证明之前，看起来像一条乐观的桥。许多人曾以为可枚举集“太大”，多项式“太硬、太瘦”，装不下计算。MRDP 的惊人处正在于：多项式够用。够用，所以数论判定问题可以和停机一样硬。不够用，第十问题本可能有算法。历史走的是够用这一支。

Julia Robinson 的假设被单独命名，是因为它把战略收成一句可检验的数论命题：是否存在增长足够快的丢番图关系。在被证明之前，它可以失败。失败的话，指数表示不必能被多项式吸收，第十问题可能仍开放。Matiyasevich 用斐波那契把它关闭，于是假设不再是假设。后人把整条定理写成四个人的缩写，正是为了不让最后一块吞掉前面的战略与条件。

指数丢番图方程允许 $a^b$ 出现。1961 年的结果已经把可枚举集放到这一层。看起来只差“再去掉指数”。这一步在数论里并不小。指数是计算里最容易写循环的地方；用多项式模拟它，需要一种本身增长得像指数的可定义关系。斐波那契满足线性递推，却能提供这种增长。桥梁选在这里，不是因为斐波那契有名，而是因为它的增长与可定义性同时够用。

否定解不禁止计算机辅助搜索具体方程。搜索可以找到根，找不到时不能下“无根”的结论——除非你另有结构证明。第十问题禁止的是那台对所有输入都停机并说真话的机器。人仍然可以证明费马、可以分类二次型、可以在椭圆曲线上数点。通用手续消失之后，数学没有停，它改成在有结构的岛屿上工作。这与 NP 完全出现之后算法研究的分工相同，只是失败发生得更早：连算法都不存在，谈不上多项式时间。

对固定的一类方程，人仍然可以发明判定手续。例如某些一次与二次情形，结构足够把搜索变成有限检查。第十问题说的是：不存在覆盖所有整系数多元多项式的那一种手续。子类可以有算法，总类没有。分类工作因此变成数论日常，而不是对 1970 年结果的不敬。

把第十问题写成“数学没有算法”，会把算术里大量可判定片段抹掉。加法、乘法、许多理想论决策问题都有手续。失败的是那一个全称量词：任意整系数多项式。全称一拿掉，工作立刻恢复。这是否定解应有的精度。全称量词一旦被证伪，正确反应是缩小问题，而不是宣布数论结束。缩小之后，岛屿上的工作才重新开始。第十问题给的不是绝望，是一张地图：哪些地方没有通用机。先看地图，再决定上哪座岛。

跨域连接#

• 可计算性：递归可枚举与递归（可判定）的差别，在这里变成丢番图与“有算法的数论问题”的差别。第十问题是停机问题的一次数论翻译，不是停机问题的推论一句带过。翻译需要模拟，模拟需要斐波那契那种增长。
• 哥德尔不完备定理：两者都让希尔伯特的“必将知道”失败。不完备性打击的是证明系统的内部；第十问题打击的是判定手续的外部输入。可以同时接受“算术不完备”和“许多具体方程已被人证完”。失败的层级不同，不能互相替代。
• P vs NP：若某子类丢番图问题既在 NP 里又被证明 NP 完全，那是复杂度；第十问题本身在更前面就停了。不要用 NP 完全当不可判定的同义词。一个问的是多项式时间，一个问的是有没有算法。
• 康托尔定理：不可数与不可判定常被外行收成“无穷所以不行”。康托尔说的是幂集严格更大；第十问题说的是自然数上的一个语言无法被算法切分。无穷集合可以完全可判定，例如偶数。困难来自编码计算，不来自集合是无限的。
• 逻辑：存在量词把计算藏进“有一组整数使多项式为零”。一阶数论的句子可以非常短，却已经足够硬。逻辑形式的长度不是难度的代理。短句子、少未知数，仍然可以编码停机。

参考文献#

• Yuri Matiyasevich, "Enumerable sets are Diophantine", Doklady Akademii Nauk SSSR 191, 1970, pp. 279–282；英译 Soviet Mathematics Doklady 11, 1970, pp. 354–358.
• Martin Davis, Hilary Putnam & Julia Robinson, "The Decision Problem for Exponential Diophantine Equations", Annals of Mathematics 74(3), 1961, pp. 425–436.
• Martin Davis, "Arithmetical Problems and Recursively Enumerable Predicates", Journal of Symbolic Logic 18, 1953, pp. 33–41. —— 后来被称为 Davis 猜想的早期表述。
• Bjorn Poonen, "Undecidability in Number Theory", Notices of the AMS 55(3), 2008, pp. 344–350. —— 面向非逻辑专家的论域分界与后续开放问题。

延伸阅读#

• Yuri Matiyasevich, Hilbert's Tenth Problem, MIT Press, 1993. 完整技术叙述与历史。
• 与 哥德尔–图灵对话、希尔伯特–哥德尔对话 对读：纲领、不完备与判定问题在同一场基础争论里，但不是同一条定理。