希爾伯特第十問題

维库，知识与思想的自由文库

希爾伯特的第十個問題，就是不定方程(又稱為丟番圖方程)的可解答性。這是希爾伯特於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 = 2 k m n, 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

沒有整數解。

[编辑] 丟番圖集

[编辑] 丟番圖函數

[编辑] 遞歸函數

[编辑] 遞歸可枚舉集

[编辑] 通用丟番圖集

[编辑] 歷史發展

第十問題的解決是眾人集體的智慧結晶。其中美國數學家 Davis、Putnam 和 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 Green 和 Terence Tao 所證明)：存在任意有限長度全由質數所組成的算數級數，他們證明了每一個遞歸可枚舉集都是指數丟番圖的。因此若是 J.R. 成立，就可以將「指數」兩字拿掉，而得到每一個遞歸可枚舉集都是丟番圖的。因而第十問題是不可解的。
1960	Robinson 證明了上述的數論假設是不必要的，並且大大簡化了證明。從而可知，只要能證明冪函數是丟番圖的，第十問題就可以解決。而關鍵又是尋找滿足 J.R. 假設的丟番圖集。
1961-1969	David 與 Putnam 提出數種可證明 J.R. 的假定。Robinson 指出，若存在一個全由質數組成的無限丟番圖集，便可證明 J.R.
1970	Matiyasevich 指出可由十個一次和二次的聯立不定方程組，定義偶角標的斐波那契函數： $b = F 2 a$ 其中 $F n$ 是第 $n$ 個斐波那契數。也就是它是丟番圖的，並滿足 J.R. 假設。從而可構造出一個不定方程，它不是遞歸可解的。也就是不存在算法，可以計算該方程式的整數解。因此使得希爾伯特第十問題，得到最終否定的解答。