查看“︁希爾伯特第十問題”︁的源代码

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

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

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

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

==基本觀念==
===不定方程===
不定方程是指含任意數量[[變數|變元]]的'''整係數多項式方程'''

::<math>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</math>　　　　　<math>1 \le j \le k</math>

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

::<math>P(m_1,m_2,...,m_k)=0</math>

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

::<math>P(x,y,z)=x^2+y^2-z^2</math>

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

著名的[[費馬最後定理]]，是說當<math>n>2</math>時，方程式

::<math>P(x,y,z)=x^n+y^n-z^n=0</math>

沒有非零整數解。

===丟番圖集===
自然数，自然数对（或具有自然数的n-元组）的有丟番图定义的集合被称为''[[丟番图集]]''。丟番图定义可以由方程组或单个方程给出，因为方程组

:<math>p_1=0,\ldots,p_k=0\,</math> 

等价于单个方程：

:<math>p_1^2+\cdots+p_k^2=0.\,</math>

[[递归可枚举集]]可以被描述为一个集合，对其存在一种算法，对这个算法，当集合的一个成员被输入时最终会停机，但一个非成员被输入时会不确定的继续。是可计算性理论（亦即[[递归论]]）给出了算法可计算性的直觉符号的精确解释，因而使得递归可枚举性的符号具有完美的严格性。显然，丟番图集是递归可枚举的。因为可以排列所有可能的未知数的值的多元组为一个序列，然后对于一个给定的参数值，一个接一个的测试这些多元组，看他们是否是相应方程的解。希尔伯特第十问题的不可解性源于令人惊讶的事实──其逆命题成立：
<blockquote>''每个递归可枚举集都是丟番图集。''</blockquote>
这一结果即[[马季亚谢维奇定理]]（由他提供的完成证明的关键步骤）和[[MRDP定理]]（即[[尤里·马季亚谢维奇]]（[[Yuri Matiyasevich]]），[[朱莉娅·罗宾逊]]（[[Julia Robinson]]），[[马丁·戴维斯]]（[[Martin Davis]]）和[[希拉里·普特南]]（[[Hilary Putnam]]）各人姓氏的首字母缩写）。因为“存在一个递归可枚举集是不可计算的”，希尔伯特第十问题的不可解性是其直接后果。实际上，还有更多的结论：有一个多项式
:<math>p(a,x_1,\ldots,x_n)</math>
有整数系数使对于方程
:<math>p(a,x_1,\ldots,x_n)=0</math>
有自然数解的<math>a</math>的值的集合不可计算。因此，不仅没有一般的算法测试丟番图方程可解性，甚至也没有算法来测试单一参数家族的方程。

===丟番圖函數===
{{Empty section|time=2020-06-07T16:43:36+00:00}}

===遞歸函數===
{{Empty section|time=2020-06-07T16:43:36+00:00}}

===遞歸可枚舉集===
{{Empty section|time=2020-06-07T16:43:36+00:00}}

===通用丟番圖集===
{{Empty section|time=2020-06-07T16:43:36+00:00}}

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

{| class="wikitable"
! 年代
! 事件
|-
|1944
|{{tsl|en|Emil Leon Post|埃米爾·萊昂·珀斯特}}首先猜測，對於第十問題，應尋求不可解的證明。
|- 
|1949
|马丁·戴维斯利用[[库尔特·哥德尔]]的方法，並應用[[中國餘數定理]]的編碼技巧，得到遞歸可枚舉集的'''戴維斯範式'''

:<math> \{a | \exists y \,\forall k \!_{\le y}\, \exists x_1,\ldots , x_n [p(a,k,y,x_1,\ldots ,x_n)=0]\}</math>
其中<math>p</math>是不定方程。他注意到丟番圖集的[[補集]]並非丟番圖的。而遞歸可枚舉集對於補集運算也非封閉的，他因此猜測這兩個集合類是相同的。
|-
|1950
|朱莉娅·罗宾逊在未知戴维斯工作的情況下，試圖證明[[冪函數]]是丟番圖的
:<math>z=y^x</math>
雖然並未成功，她發現如果存在這樣的丟番圖集<math>D=\{(a,b)\}</math>，使得
:<math>(a,b)\in D \Rightarrow b < a^a</math>
而且
:<math>\forall k>0 \,\exists(a,b)\in D</math>　使得　<math>b>a^k</math>
在假設這樣丟番圖集存在（稱為J.R.）的情況下，她證明了冪函數是丟番圖的。並且如果冪函數是丟番圖的，那麼[[二項式係數]]、[[階乘]]以及[[質數]]集合都是丟番圖的。
|-
|1959
|戴维斯與普特南共同研究了'''[[指數丟番圖集]]'''，也就是以丟番圖方程所定義的集合，但其中指數可以是未知數。使用戴維斯範式與罗宾逊的方法，並且利用數論中一個當時尚未證明的假設（註：已於2004年由{{tsl|en|Ben Green|班·格林}}和[[陶哲軒]]所證明）：存在任意有限長度全由質數所組成的[[算數級數]]，他們證明了每一個遞歸可枚舉集都是指數丟番圖的。因此若是J.R.成立，就可以將「指數」兩字拿掉，而得到每一個遞歸可枚舉集都是丟番圖的。因而第十問題是不可解的。
|-
|1960
|罗宾逊證明了上述的數論假設是不必要的，並且大大簡化了證明。從而可知，只要能證明冪函數是丟番圖的，第十問題就可以解決。而關鍵又是尋找滿足J.R.假設的丟番圖集。
|-
|1961-1969
|戴维斯與普特南提出數種可證明J.R.的假定。罗宾逊指出，若存在一個全由質數組成的無限丟番圖集，便可證明J.R.
|-
|1970
|[[尤里·马季亚谢维奇]]指出可由十個一次和二次的聯立不定方程組，定義偶角標的[[斐波那契數|斐波那契函數]]：
:<math> b = F_{2a}</math>
其中<math>F_n</math>是第<math>n</math>個斐波那契數。也就是它是丟番圖的，並滿足J.R.假設。從而可構造出一個不定方程，它不是[[遞歸]]可解的。也就是不存在算法，可以計算該方程式的整數解。因此使得希爾伯特第十問題，得到最終'''否定的解答'''。
|}

==外部链接==
*[http://www.changhai.org/articles/science/mathematics/hilbert10/index.php Hilbert第十问题漫谈] {{Wayback|url=http://www.changhai.org/articles/science/mathematics/hilbert10/index.php |date=20180219145651 }}
*[http://blog.csdn.net/linyt/archive/2009/06/25/4296663.aspx 希尔伯特第十问题：一段数学发现史]
*[http://logic.pdmi.ras.ru/Hilbert10/ Hilbert's Tenth Problem page]{{Wayback|url=http://logic.pdmi.ras.ru/Hilbert10/ |date=20120402144124 }}
*[http://www.jaworski.co.uk/m13/13_hilbert.html Hilbert's 10th Problem] {{Wayback|url=http://www.jaworski.co.uk/m13/13_hilbert.html |date=20141030052243 }}
{{Hilbert's problems}}
[[Category:丢番图方程]]
[[Category:希尔伯特问题]]