希尔伯特第十问题
希尔伯特的第十个问题,就是不定方程(又称为丢番图方程)的可解答性。这是希尔伯特于1900年在巴黎的国际数学家大会演说中,所提出的23个重要数学问题的第十题。
这个问题是问,对于任意多个未知数的整系数不定方程,要求给出一个可行的方法(verfahren),使得借助于它,通过有限次运算,可以判定该方程有无整数解。
这里德文的方法(verfahren),就是英文所谓的演算法(algorithm)。对于演算法的概念我们是不陌生的,例如远在古希腊时代,人们就知道可以使用辗转相除法,求两个自然数的最大公约数。还有,任给一个自然数,也存在著一个方法,在有限步骤内,可以判定这个数是不是质数。
虽然人们很早就有了演算法的朴素概念,但对于到底什么是可行的计算,仍没有精确的概念。一个问题的可解与不可解究竟是什么含意,当时的人们还不得而知。然而为了研究第十问题,必须给予演算法精确化的观念。这点还有赖于数理逻辑学对可计算性理论的发展,才得以实现。
基本观念
编辑不定方程
编辑不定方程是指含任意数量变元的整系数多项式方程
这里 都是正整数、负整数或零,而变元 的定义域是自然数或整数。若能找到整数 ,使得
则称此不定方程具有整数解。例如:
则(3,4,5)、(5,12,13)等都是它的整数解。事实上可找出它所有的整数解: ,其中 。这是著名的勾股定理或称毕式定理。
著名的费马最后定理,是说当 时,方程式
没有非零整数解。
丢番图集
编辑自然数,自然数对(或具有自然数的n-元组)的有丢番图定义的集合被称为丢番图集。丢番图定义可以由方程组或单个方程给出,因为方程组
等价于单个方程:
递归可枚举集可以被描述为一个集合,对其存在一种算法,对这个算法,当集合的一个成员被输入时最终会停机,但一个非成员被输入时会不确定的继续。是可计算性理论(亦即递归论)给出了算法可计算性的直觉符号的精确解释,因而使得递归可枚举性的符号具有完美的严格性。显然,丢番图集是递归可枚举的。因为可以排列所有可能的未知数的值的多元组为一个序列,然后对于一个给定的参数值,一个接一个的测试这些多元组,看他们是否是相应方程的解。希尔伯特第十问题的不可解性源于令人惊讶的事实──其逆命题成立:
每个递归可枚举集都是丢番图集。
这一结果即马季亚谢维奇定理(由他提供的完成证明的关键步骤)和MRDP定理(即尤里·马季亚谢维奇(Yuri Matiyasevich),朱莉娅·罗宾逊(Julia Robinson),马丁·戴维斯(Martin Davis)和希拉里·普特南(Hilary Putnam)各人姓氏的首字母缩写)。因为“存在一个递归可枚举集是不可计算的”,希尔伯特第十问题的不可解性是其直接后果。实际上,还有更多的结论:有一个多项式
有整数系数使对于方程
有自然数解的 的值的集合不可计算。因此,不仅没有一般的算法测试丢番图方程可解性,甚至也没有算法来测试单一参数家族的方程。
丢番图函数
编辑此章节尚无任何内容,需要扩充。 (2020年6月7日) |
递归函数
编辑此章节尚无任何内容,需要扩充。 (2020年6月7日) |
递归可枚举集
编辑此章节尚无任何内容,需要扩充。 (2020年6月7日) |
通用丢番图集
编辑此章节尚无任何内容,需要扩充。 (2020年6月7日) |
历史发展
编辑第十问题的解决是众人集体的智慧结晶。其中美国数学家马丁·戴维斯(Martin Davis)、希拉里·普特南(Hilary Putnam)和朱莉娅·罗宾逊(Julia Robinson)做出了突出的贡献。而最终的结果,是由俄国数学家尤里·马季亚谢维奇(Yuri Matiyasevich)于1970年所完成的。
年代 | 事件 |
---|---|
1944 | 埃米尔·莱昂·珀斯特首先猜测,对于第十问题,应寻求不可解的证明。 |
1949 | 马丁·戴维斯利用库尔特·哥德尔的方法,并应用中国馀数定理的编码技巧,得到递归可枚举集的戴维斯范式
其中 是不定方程。他注意到丢番图集的补集并非丢番图的。而递归可枚举集对于补集运算也非封闭的,他因此猜测这两个集合类是相同的。 |
1950 | 朱莉娅·罗宾逊在未知戴维斯工作的情况下,试图证明幂函数是丢番图的
虽然并未成功,她发现如果存在这样的丢番图集 ,使得 而且
在假设这样丢番图集存在(称为J.R.)的情况下,她证明了幂函数是丢番图的。并且如果幂函数是丢番图的,那么二项式系数、阶乘以及质数集合都是丢番图的。 |
1959 | 戴维斯与普特南共同研究了指数丢番图集,也就是以丢番图方程所定义的集合,但其中指数可以是未知数。使用戴维斯范式与罗宾逊的方法,并且利用数论中一个当时尚未证明的假设(注:已于2004年由班·格林和陶哲轩所证明):存在任意有限长度全由质数所组成的算数级数,他们证明了每一个递归可枚举集都是指数丢番图的。因此若是J.R.成立,就可以将“指数”两字拿掉,而得到每一个递归可枚举集都是丢番图的。因而第十问题是不可解的。 |
1960 | 罗宾逊证明了上述的数论假设是不必要的,并且大大简化了证明。从而可知,只要能证明幂函数是丢番图的,第十问题就可以解决。而关键又是寻找满足J.R.假设的丢番图集。 |
1961-1969 | 戴维斯与普特南提出数种可证明J.R.的假定。罗宾逊指出,若存在一个全由质数组成的无限丢番图集,便可证明J.R. |
1970 | 尤里·马季亚谢维奇指出可由十个一次和二次的联立不定方程组,定义偶角标的斐波那契函数:
其中 是第 个斐波那契数。也就是它是丢番图的,并满足J.R.假设。从而可构造出一个不定方程,它不是递归可解的。也就是不存在算法,可以计算该方程式的整数解。因此使得希尔伯特第十问题,得到最终否定的解答。 |