希尔伯特第十问题
维基百科,自由的 encyclopedia
希尔伯特的第十个问题,就是不定方程(又称为丢番图方程)的可解答性。这是希尔伯特于1900年在巴黎的国际数学家大会演说中,所提出的23个重要数学问题的第十题。
这个问题是问,对于任意多个未知数的整系数不定方程,要求给出一个可行的方法(verfahren),使得借助于它,通过有限次运算,可以判定该方程有无整数解。
这里德文的方法(verfahren),就是英文所谓的演算法(algorithm)。对于演算法的概念我们是不陌生的,例如远在古希腊时代,人们就知道可以使用辗转相除法,求两个自然数的最大公约数。还有,任给一个自然数,也存在著一个方法,在有限步骤内,可以判定这个数是不是质数。
虽然人们很早就有了演算法的朴素概念,但对于到底什么是可行的计算,仍没有精确的概念。一个问题的可解与不可解究竟是什么含意,当时的人们还不得而知。然而为了研究第十问题,必须给予演算法精确化的观念。这点还有赖于数理逻辑学对可计算性理论的发展,才得以实现。