希爾伯特第十問題

维基百科,自由的百科全书
跳转至: 导航搜索

希爾伯特第十個問題,就是不定方程(又稱為丟番圖方程)的可解答性。這是希爾伯特於1900年在巴黎國際數學家大會演說中,所提出的23個重要數學問題的第十題。

這個問題是問,對於任意多個未知數的整係數不定方程,要求給出一個可行的方法(verfahren),使得借助於它,通過有限次運算,可以判定該方程有無整數解。

這裡德文的方法 verfahren,就是英文所謂的演算法 algorithm。對於演算法的概念我們是不陌生的,例如遠在古希臘時代,人們就知道可以使用輾轉相除法,求兩個自然數的最大公約數。還有,任給一個自然數,也存在著一個方法,在有限步驟內,可以判定這個數是不是質數

雖然人們很早就有了演算法的樸素概念,但對於到底什麼是可行的計算,仍沒有精確的概念。一個問題的可解與不可解究竟是什麼含意,當時的人們還不得而知。然而為了研究第十問題,必須給予演算法精確化的觀念。這點還有賴於數理邏輯學對可計算性理論的發展,才得以實現。

基本觀念[编辑]

不定方程[编辑]

不定方程是指含任意數量變元整係數多項式方程

P(x_1,x_2,...,x_k)=\sum_{0 \le i_j \le n_j}a_{i_1i_2...i_k}x_1^{i_1}x_2^{i_2}...x_k^{i_k}=0     1 \le j \le k

這裡 a_{i_1i_2...i_k} 都是正整數、負整數或零,而變元 x_1,x_2,...,x_k定義域自然數整數。若能找到整數 m_1,m_2,...,m_k,使得

P(m_1,m_2,...,m_k)=0

則稱此不定方程具有整數解。例如:

P(x,y,z)=x^2+y^2-z^2

則 (3,4,5)、(5,12,13) 等都是它的整數解。事實上可找出它所有的整數解:a=k(m^2-n^2), b=2kmn, c=k(m^2+n^2),其中k, m,n\in \mathbb{N*},m>n 。這是著名的勾股定理或稱畢式定理

著名的費馬最後定理,是說當 n>2 時,方程式

P(x,y,z)=x^n+y^n-z^n=0

沒有非零整數解。

丟番圖集[编辑]

自然数,自然数对(或具有自然数的n-元组)的有丟番图定义的集合被称为丟番图集。 丟番图定义可以由方程组或单个方程给出,因为方程组

p_1=0,\ldots,p_k=0\,

等价于单个方程:

p_1^2+\cdots+p_k^2=0.\,

递归可枚举集可以被描述为一个集合,对其存在一种算法,对这个算法,当集合的一个成员被输入时最终会停机,但一个非成员被输入时会不确定的继续。是可计算性理论(亦即递归论)给出了算法可计算性的直觉符号的精确解释,因而使得递归可枚举性的符号具有完美的严格性。显然,丟番图集是递归可枚举的。因为可以排列所有可能的未知数的值的多元组为一个序列,然后对于一个给定的参数值,一个接一个的测试这些多元组,看他们是否是相应方程的解。希尔伯特第十问题的不可解性源于令人惊讶的事实──其逆命题成立:

每个递归可枚举集都是丟番图集。

这一结果即马季亚谢维奇定理(由他提供的完成证明的关键步骤)和MRDP定理(即尤里·马季亚谢维奇(Yuri Matiyasevich),朱莉娅·罗宾逊(Julia Robinson),马丁·戴维斯(Martin Davis)和希拉里·普特南(Hilary Putnam)各人姓氏的首字母缩写)。因为“存在一个递归可枚举集是不可计算的”,希尔伯特第十问题的不可解性是其直接后果。实际上,还有更多的结论:有一个多项式

p(a,x_1,\ldots,x_n)

有整数系数使对于方程

p(a,x_1,\ldots,x_n)=0

有自然数解的a的值的集合不可计算。因此,不仅没有一般的算法测试丟番图方程可解性,甚至也没有算法来测试单一参数家族的方程。

丟番圖函數[编辑]

遞歸函數[编辑]

遞歸可枚舉集[编辑]

通用丟番圖集[编辑]

歷史發展[编辑]

第十問題的解決是眾人集體的智慧結晶。其中美國數學家马丁·戴维斯(Martin Davis)、希拉里·普特南(Hilary Putnam)和朱莉娅·罗宾逊(Julia Robinson)做出了突出的貢獻。而最終的結果,是由俄國數學家尤里·马季亚谢维奇(Yuri Matiyasevich)於1970年所完成的。

年代 事件
1944 Emil Leon Post首先猜測,對於第十問題,應尋求不可解的證明。
1949 Martin Davis利用Kurt Gödel 的方法,並應用中國餘數定理的編碼技巧,得到遞歸可枚舉集的戴維斯範式
 \{a | \exists y \,\forall k \!_{\le y}\, \exists x_1,\ldots , x_n [p(a,k,y,x_1,\ldots ,x_n)=0]\}

其中 p 是不定方程。他注意到丟番圖集的補集並非丟番圖的。而遞歸可枚舉集對於補集運算也非封閉的,他因此猜測這兩個集合類是相同的。

1950 Julia Robinson 在未知 Davis 工作的情況下,試圖證明冪函數是丟番圖的
z=y^x

雖然並未成功,她發現如果存在這樣的丟番圖集 D=\{(a,b)\},使得

(a,b)\in D \Rightarrow b < a^a

而且

\forall k>0 \,\exists (a,b)\in D 使得 b>a^k

在假設這樣丟番圖集存在(稱為 J.R.)的情況下,她證明了冪函數是丟番圖的。並且如果冪函數是丟番圖的,那麼二項式係數階乘以及質數集合都是丟番圖的。

1959 David與Putnam 共同研究了指數丟番圖集,也就是以丟番圖方程所定義的集合,但其中指數可以是未知數。使用戴維斯範式與 Robinson 的方法,並且利用數論中一個當時尚未證明的假設(註:已於 2004 年由 Ben GreenTerence Tao 所證明):存在任意有限長度全由質數所組成的算數級數,他們證明了每一個遞歸可枚舉集都是指數丟番圖的。因此若是 J.R. 成立,就可以將「指數」兩字拿掉,而得到每一個遞歸可枚舉集都是丟番圖的。因而第十問題是不可解的。
1960 Robinson證明了上述的數論假設是不必要的,並且大大簡化了證明。從而可知,只要能證明冪函數是丟番圖的,第十問題就可以解決。而關鍵又是尋找滿足 J.R. 假設的丟番圖集。
1961-1969 David與Putnam提出數種可證明 J.R. 的假定。Robinson 指出,若存在一個全由質數組成的無限丟番圖集,便可證明 J.R.
1970 尤里·马季亚谢维奇指出可由十個一次和二次的聯立不定方程組,定義偶角標的斐波那契函數
 b = F_{2a}

其中 F_n 是第 n 個斐波那契數。也就是它是丟番圖的,並滿足 J.R. 假設。從而可構造出一個不定方程,它不是遞歸可解的。也就是不存在算法,可以計算該方程式的整數解。因此使得希爾伯特第十問題,得到最終否定的解答

外部链接[编辑]