在希爾伯特看來，一個像費馬猜想這樣的數(shù)學(xué)問題對數(shù)學(xué)的價值是無可估量的。希爾伯特不僅舍不得“殺鵝”，還懷著極大的熱誠為20世紀(jì)的數(shù)學(xué)界做了一回“尋鵝之人”。1900年，在巴黎舉行的第二屆國際數(shù)學(xué)家大會上，希爾伯特做了一次堪稱數(shù)學(xué)史上影響最為深遠(yuǎn)的演講，題目是“數(shù)學(xué)問題”。在演講中，希爾伯特列舉了23個他認(rèn)為最具重要意義的數(shù)學(xué)問題，這些問題被后人稱為“希爾伯特問題”。解決希爾伯特問題成了許多數(shù)學(xué)家終生奮斗的目標(biāo)，在解決這些問題的過程中，源源不斷地產(chǎn)生出的“金蛋”為20世紀(jì)的數(shù)學(xué)發(fā)展注入了極大的生機(jī)。
什么是希爾伯特第十問題
希爾伯特第十問題是一個與解方程有關(guān)的問題。在中學(xué)時我們就解過許多簡單的方程，比如2x－2y＝1，x2＋y2＝z2。這兩個簡單方程有一個共同特點，只包含未知數(shù)的整數(shù)次冪，系數(shù)也都是整數(shù)，這類方程被稱為整系數(shù)代數(shù)多項式方程。數(shù)學(xué)家們對這類方程的研究有著漫長的歷史。
公元3世紀(jì)，希臘數(shù)學(xué)家丟番圖發(fā)表了一部長篇巨著《算術(shù)》。這部13卷的著作，經(jīng)過1700多年的漫長歲月，流傳至今的只有六卷。丟番圖在這部著作中對整系數(shù)代數(shù)多項式方程進(jìn)行的大量研究，對代數(shù)與數(shù)論的發(fā)展有著先驅(qū)性的貢獻(xiàn)。后人為紀(jì)念他，把整系數(shù)代數(shù)多項式方程稱為丟番圖方程。
對于丟番圖方程，數(shù)學(xué)家們最感興趣的是它是否有整數(shù)解（或自然數(shù)解）。對于簡單的方程這是很容易找到答案的，比如x2＋y2＝z2有整數(shù)解（早在3000多年前，我國古代的數(shù)學(xué)家就知道這個方程的一組解：即勾三股四弦五）；2x－2y＝1則沒有整數(shù)解（因為方程的左邊為偶數(shù)，右邊卻為奇數(shù)）。但對于一般的丟番圖方程來說，判斷它是否有整數(shù)解卻是件極困難的事，其中最著名的例子就是費馬猜想，即xn＋yn＝zn在n＞2時沒有非零整數(shù)解，直到300多年后才得到證明。
長期以來，人們對丟番圖方程是否有整數(shù)解的研究都是針對特定形式的丟番圖方程進(jìn)行的。有沒有辦法對一般的丟番圖方程是否有整數(shù)解進(jìn)行研究呢？或者，是否可以找到一種普遍的算法，用來判定一個任意的丟番圖方程是否有整數(shù)解，從而一勞永逸地解決這類問題呢？這便是著名的希爾伯特第十問題。這樣的問題在數(shù)學(xué)上被稱為判定問題（Decision Problem），因為它尋求的是對數(shù)學(xué)命題進(jìn)行判定的算法。
希爾伯特是一位對數(shù)學(xué)充滿樂觀信念的數(shù)學(xué)家。他提出這一問題時，沒有用“是否存在這樣的算法”作為問題的表述，而是直接要求數(shù)學(xué)家們尋找這樣的算法，可見他對存在一個肯定的答案懷有期待。這種期待與他在其他方面對數(shù)學(xué)的樂觀看法一脈相承。
不可判定命題的啟示
希爾伯特第十問題要求尋找判定丟番圖方程是否有解的算法。究竟是什么算法呢？當(dāng)時沒有明確的定義。這一困難使希爾伯特第十問題在提出后整整30年沒有取得任何實質(zhì)性進(jìn)展。
直到20世紀(jì)30年代，對算法的研究才逐漸深入。
數(shù)學(xué)上，算法是（通過有限多的步驟）對數(shù)學(xué)函數(shù)進(jìn)行有效計算的方法。因此算法研究的一個重要的切入點，是尋找可以有效計算的函數(shù)。到底什么樣的函數(shù)是可以有效計算的呢？數(shù)學(xué)家們開始并沒有普遍的結(jié)論，只知道一些最簡單的函數(shù)，以及用這些函數(shù)通過若干簡單規(guī)則組合出的函數(shù)是可以有效計算的。數(shù)學(xué)家們把這類函數(shù)叫做遞歸函數(shù)。
1931年，年輕的法國數(shù)學(xué)家赫爾布蘭德（JacquesHerbrand，1908～1931）對遞歸函數(shù)進(jìn)行了研究，并給著名邏輯學(xué)家哥德爾（1906～1978）寫信敘述了自己的研究結(jié)果。哥德爾當(dāng)時正處于自己一生中最重大的成果——哥德爾不完全性定理的研究時期，沒有立即對赫爾布蘭德的工作做出回應(yīng)。那一年的夏天，年僅23歲的赫爾布蘭德在攀登阿爾卑斯山時不幸遇難，他的工作因此被暫時埋沒了。
與赫爾布蘭德的研究差不多同時，20世紀(jì)30年代初，普林斯頓大學(xué)的美國邏輯學(xué)家丘奇（AlonzoChurch，1903～1995）也在積極從事邏輯及算法的研究，并且發(fā)展出了一種新的邏輯體系。他讓自己的兩個學(xué)生克林（StephenKleene，1909～1994）與羅瑟（JohnRosser，1907～1989）對這一體系做細(xì)致的研究。兩個學(xué)生都是一流好手，克林后來還成為一流的邏輯學(xué)家。他們的研究很快就有了結(jié)果，但這結(jié)果大大出乎丘奇的意料。他們發(fā)現(xiàn)丘奇的那套體系竟然是自相矛盾的！命運似乎只有一個：放棄。幸運的是，丘奇的那套體系中有一個組成部分是自洽的，因此可以保留下來，這部分叫做蘭姆達(dá)運算（λ－calculus）。
這種蘭姆達(dá)運算可以用來定義函數(shù)，而所有用蘭姆達(dá)運算定義的函數(shù)都是可以有效計算的。在對蘭姆達(dá)運算做了研究之后，丘奇提出了一個大膽的猜測，他猜測所有可以有效計算的函數(shù)都可以用蘭姆達(dá)運算來定義。
1934年，丘奇向到普林斯頓大學(xué)訪問的哥德爾介紹了這一猜測，哥德爾卻不以為然。丘奇不服氣，請哥德爾給出一個他認(rèn)為合適的描述。一兩個月后，哥德爾就給出了一種完全不同的描述，這種描述的基礎(chǔ)正是3年前赫爾布蘭德在給他的信中敘述的結(jié)果。哥德爾對這一結(jié)果進(jìn)行了完善，這一結(jié)果被人們稱為赫爾布蘭德－哥德爾遞歸函數(shù)。
這樣，丘奇與哥德爾各自給出了一種體系，描述可以有效計算的函數(shù)。丘奇與克林很快證明，這兩種看上去完全不同的描述方式實際上是彼此等價的。兩位著名邏輯學(xué)家的工作殊途同歸，大大增強(qiáng)了丘奇的信心。他相信人們已經(jīng)找到了可以有效計算的函數(shù)的普遍定義。但哥德爾及其他一些人對此卻仍然懷有疑慮。最終打消這種疑慮的是英國數(shù)學(xué)家圖靈。
圖靈當(dāng)時對丘奇及哥德爾在這方面的研究并不知情。他所研究的課題是什么樣的運算可以用機(jī)器來實現(xiàn)。他的這一研究對后來計算機(jī)科學(xué)的發(fā)展起到了深遠(yuǎn)的影響。在圖靈的研究接近完成的時候，他的導(dǎo)師注意到了丘奇與哥德爾的工作。于是圖靈對彼此的工作進(jìn)行了比較，發(fā)現(xiàn)丘奇與哥德爾所定義的那些函數(shù)與他的抽象計算機(jī)可以計算的函數(shù)恰好吻合！圖靈把這一結(jié)果作為附錄加進(jìn)了自己的論文。這下就連哥德爾也心悅誠服了，畢竟，有什么能比在計算機(jī)上計算更接近“可以有效計算”以及算法的基本含義呢？
在這些有關(guān)算法的研究中，數(shù)學(xué)家們還提出了一個重要的概念：遞歸可枚舉集，即由可以有效計算的函數(shù)所生成的自然數(shù)的集合。對于一個集合來說，一個很基本的問題就是判斷一個元素是否屬于該集合。遞歸可枚舉集也不例外。當(dāng)數(shù)學(xué)家們研究遞歸可枚舉集的時候，發(fā)現(xiàn)了一個十分微妙的結(jié)果：對于某些遞歸可枚舉集來說，我們無法判定一個自然數(shù)是否屬于該集合！換句話說，有一些遞歸可枚舉集是不可判定的。這一結(jié)果把對算法的研究與判定問題聯(lián)系了起來，為后來解決希爾伯特第十問題埋下了重要的伏筆。
這一系列結(jié)果出現(xiàn)在1936～1937年間。那時候，在數(shù)學(xué)中存在無法判定的命題已經(jīng)不是一件新鮮事了。早在5年前哥德爾就已經(jīng)證明了他的不完全性定理，即任何足夠復(fù)雜并且自洽的數(shù)學(xué)體系都必定包含不可判定的命題。當(dāng)時已知的不可判定命題大都集中在邏輯領(lǐng)域內(nèi)。在數(shù)學(xué)的其他領(lǐng)域中，究竟哪些命題是不可判定的呢？這個問題在整整10年之后才開始有答案。
1947年美國數(shù)學(xué)家波斯特（EmilPost，1897～1954）找到了第一個邏輯領(lǐng)域以外的不可判定命題。波斯特是一位有著深刻洞察力的邏輯學(xué)家，7歲時隨父母從波蘭移民到美國，是美國邏輯學(xué)的先驅(qū)之一。他早將近10年就得到了與哥德爾不完全性定理相似的結(jié)果，由于想對結(jié)果作更全面的分析而沒有及時發(fā)表。1936年，幾乎與哥德爾、丘奇及圖靈同時，波斯特獨立提出了類似于圖靈的結(jié)果，他也是最早意識到希爾伯特第十問題可能會有否定答案的數(shù)學(xué)家之一。1944年，他在一篇文章中明確提出希爾伯特第十問題“期待一個不可解性證明”。
當(dāng)時波斯特在紐約市立大學(xué)任教，他的這一觀點深深打動了一位學(xué)生，使后者走上了畢生鉆研希爾伯特第十問題的征途。這位學(xué)生名叫戴維斯，是解決希爾伯特第十問題的關(guān)鍵人物。
