MathLabs

解法：MRDP定理:丢番图集合恰为递归可枚举集合(1970年)

第 1/9 步：希尔伯特第十问题:是否存在丢番图方程的算法?
上一步下一步
通俗地说

丢番图方程是一种只有整数答案才算数的多项式谜题,例如 x2+y2=z2x^2+y^2=z^2(有解——毕达哥拉斯三元组),或者著名的 xn+yn=znx^n+y^n=z^n(对 n≥3n \ge 3,费马大定理断言无解)。1900年,大卫·希尔伯特把这个问题列为他23个著名问题中的第十个,要求给出一个单一的通用配方,只要输入任意这样的方程,总能正确回答“是,它有整数解”或“不,它没有”。

在当时,“算法”还只是一个非正式的概念;直到1930年代,阿兰·图灵与阿隆佐·邱奇才把这个概念精确到足以让人证明像这样一个问题的确定性答案“不存在这样的算法”。

P(x1,…,xn)=0,P∈Z[x1,…,xn]P(x_1, \ldots, x_n) = 0, \quad P \in \mathbb{Z}[x_1, \ldots, x_n]
详细分析

希尔伯特第十问题是他在1900年国际数学家大会演讲中提出的,要求给出一个算法,对任意整数系数多项式 P(x1,…,xn)P(x_1, \ldots, x_n),判定方程 P(x1,…,xn)=0P(x_1, \ldots, x_n) = 0 是否有整数解。当时已知有些类别完全可判定:线性丢番图方程(通过欧几里得算法与 gcd⁡\gcd),以及到1920年代,两个变量的一般二次方程(通过连分数与佩尔方程理论)。

一般高次、多变量的方程抵抗了所有经典技巧,这个问题悬而未决超过半个世纪,等待着对“算法”这个概念本身给出精确的数学定义。这一定义在1930年代通过图灵机以及丘奇、哥德尔的等价形式化才姗姗来迟,终于使人们能够证明一个严格的不可能性结果,而不仅仅是找不到方法。

从1950年代起发展出来的攻克这个问题的关键,是把丢番图方程这一代数概念,直接与可计算性理论中“可枚举”集合这一概念进行比较——这正是下一步的主题。

本步骤中的术语
丢番图方程
一个整数系数的多项式方程 P(x1,…,xn)=0P(x_1, \ldots, x_n) = 0,人们只关心整数(有时是非负整数)解,以古代数学家丢番图命名。
算法(判定过程)
一种有限的、机械的、按步骤进行的过程,保证对每一个可能的输入都会停止并给出正确的是/否答案;在1930年代通过图灵机及等价形式化被数学上精确化。
本步骤用到的知识
递归函数与图灵机一次不定方程