希爾伯特第十問題

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

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

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

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

基本觀念

不定方程

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

P(x_{1},x_{2},...,x_{k})=\sum _{0\leq i_{j}\leq n_{j}}a_{i_{1}i_{2}...i_{k}}x_{1}^{i_{1}}x_{2}^{i_{2}}...x_{k}^{i_{k}}=0

1\leq j\leq k

這裡 $a_{i_{1}i_{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）（Julia Robinson）做出了突出的貢獻。而最終的結果，是由俄國數學家尤里·馬季亞謝維奇（Yuri Matiyasevich）於1970年所完成的。

年代	事件
1944	埃米爾·萊昂·珀斯特（英語：Emil Leon Post）首先猜測，對於第十問題，應尋求不可解的證明。
1949	馬丁·戴維斯利用庫爾特·哥德爾的方法，並應用中國餘數定理的編碼技巧，得到遞歸可枚舉集的戴維斯範式 $\{a\|\exists y\,\forall k\!_{\leq y}\,\exists x_{1},\ldots ,x_{n}[p(a,k,y,x_{1},\ldots ,x_{n})=0]\}$ 其中 $p$ 是不定方程。他注意到丟番圖集的補集並非丟番圖的。而遞歸可枚舉集對於補集運算也非封閉的，他因此猜測這兩個集合類是相同的。
1950	朱莉婭·羅賓遜在未知戴維斯工作的情況下，試圖證明冪函數是丟番圖的 $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	戴維斯與普特南共同研究了指數丟番圖集，也就是以丟番圖方程所定義的集合，但其中指數可以是未知數。使用戴維斯範式與羅賓遜的方法，並且利用數論中一個當時尚未證明的假設（註：已於2004年由班·格林（英語：Ben Green）和陶哲軒所證明）：存在任意有限長度全由質數所組成的算數級數，他們證明了每一個遞歸可枚舉集都是指數丟番圖的。因此若是J.R.成立，就可以將「指數」兩字拿掉，而得到每一個遞歸可枚舉集都是丟番圖的。因而第十問題是不可解的。
1960	羅賓遜證明了上述的數論假設是不必要的，並且大大簡化了證明。從而可知，只要能證明冪函數是丟番圖的，第十問題就可以解決。而關鍵又是尋找滿足J.R.假設的丟番圖集。
1961-1969	戴維斯與普特南提出數種可證明J.R.的假定。羅賓遜指出，若存在一個全由質數組成的無限丟番圖集，便可證明J.R.
1970	尤里·馬季亞謝維奇指出可由十個一次和二次的聯立不定方程組，定義偶角標的斐波那契函數： $b=F_{2a}$ 其中 $F_{n}$ 是第 $n$ 個斐波那契數。也就是它是丟番圖的，並滿足J.R.假設。從而可構造出一個不定方程，它不是遞歸可解的。也就是不存在算法，可以計算該方程式的整數解。因此使得希爾伯特第十問題，得到最終否定的解答。