希爾伯特的第十個問題，就是不定方程（又稱為丟番圖方程）的可解答性。這是希爾伯特於1900年在巴黎的國際數學家大會演說中，所提出的23個重要數學問題的第十題。
這個問題是問，對於任意多個未知數的整係數不定方程，要求給出一個可行的方法（），使得借助於它，通過有限次運算，可以判定該方程有無整數解。
這裡德文的方法（），就是英文所謂的演算法（）。對於演算法的概念我們是不陌生的，例如遠在古希臘時代，人們就知道可以使用輾轉相除法，求兩個自然數的最大公約數。還有，任給一個自然數，也存在著一個方法，在有限步驟內，可以判定這個數是不是質數。
雖然人們很早就有了演算法的樸素概念，但對於到底什麼是可行的計算，仍沒有精確的概念。一個問題的可解與不可解究竟是什麼含意，當時的人們還不得而知。然而為了研究第十問題，必須給予演算法精確化的觀念。這點還有賴於數理邏輯學對可計算性理論的發展，才得以實現。
基本觀念
不定方程
不定方程是指含任意數量變元的整係數多項式方程
::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年所完成的。
外部链接
*[http://www.changhai.org/articles/science/mathematics/hilbert10/index.php Hilbert第十问题漫谈]
*[http://blog.csdn.net/linyt/archive/2009/06/25/4296663.aspx 希尔伯特第十问题：一段数学发现史]
*[http://logic.pdmi.ras.ru/Hilbert10/ Hilbert's Tenth Problem page]
*[http://www.jaworski.co.uk/m13/13_hilbert.html Hilbert's 10th Problem]
评论 (0)