Hilbert 第十問題漫談 (上)
- 盧昌海 -
 |
| David Hilbert |
數(shù)學(xué)問題是數(shù)學(xué)中最具魅力的部分之一， 并且也是數(shù)學(xué)史上許多思想和進(jìn)展的重要源泉。 據(jù)說有人曾建議德國(guó)著名的數(shù)學(xué)家希爾伯特 (David Hilbert, 1862-1943) 去解決費(fèi)馬猜想 (Fermat's conjecture)， 以奪取為這一猜想而設(shè)的沃爾夫斯凱爾獎(jiǎng)金 (Wolfskehl Prize)， 希爾伯特卻笑了笑回答說： “我為什么要?dú)⒌粢恢粫?huì)下金蛋的鵝呢？” 在希爾伯特看來， 一個(gè)象費(fèi)馬猜想那樣的數(shù)學(xué)問題對(duì)數(shù)學(xué)的價(jià)值是無可估量的。 希爾伯特不僅舍不得 “殺鵝”， 還懷著極大的熱誠(chéng)為 20 世紀(jì)的數(shù)學(xué)界做了一回 “尋鵝之人”。 1900 年， 在于巴黎舉辦的第二屆國(guó)際數(shù)學(xué)家大會(huì)上， 希爾伯特做了一次堪稱數(shù)學(xué)史上影響最為深遠(yuǎn)的演講， 演講的題目叫做 “數(shù)學(xué)問題” (The Problems of Mathematics)。 在那次演講中， 希爾伯特列舉了 23 個(gè)他認(rèn)為最具重要意義的數(shù)學(xué)問題[注一]。 那些問題被后人稱為 “希爾伯特問題” (problems of Hilbert)。 自那次演講之后， 解決希爾伯特問題成了許多數(shù)學(xué)家終生為止奮斗的目標(biāo)， 而在解決這些問題的過程中源源不斷產(chǎn)生出來的 “金蛋”， 則為 20 世紀(jì)的數(shù)學(xué)發(fā)展注入了極大的生機(jī)和活力。
在本文中， 我們就來講述有關(guān)這些數(shù)學(xué)問題中第十個(gè)——即所謂 “希爾伯特第十問題” (Hilbert's tenth problem)——的一些故事。
希爾伯特第十問題是一個(gè)與解方程有關(guān)的問題。 解方程大家都不陌生， 在中學(xué)時(shí)我們就已解過許多簡(jiǎn)單的方程， 比如 2x—2y=1， x2+y2=z2， 等。 我們所舉的這兩個(gè)簡(jiǎn)單方程有一個(gè)共同特點(diǎn)， 那就是都只包含未知數(shù)的整數(shù)次冪， 而且系數(shù)也都是整數(shù)， 這類方程被稱為整系數(shù)代數(shù)多項(xiàng)式方程。 數(shù)學(xué)家們對(duì)這類方程的研究有著漫長(zhǎng)的歷史。
在公元 3 世紀(jì)的時(shí)侯， 古希臘數(shù)學(xué)家丟番圖 (Diophantus, 200?-284?) 發(fā)表了一部長(zhǎng)篇巨著， 叫做 《算術(shù)》(Arithmetica)。 這部著作共有 13 卷， 經(jīng)過 1700 余年的漫長(zhǎng)歲月， 目前被公認(rèn)流傳于世的有 6 卷[注二]。 丟番圖在這部著作中對(duì)整系數(shù)代數(shù)多項(xiàng)式方程進(jìn)行了大量研究， 那些研究對(duì)代數(shù)與數(shù)論的發(fā)展有著先驅(qū)性的貢獻(xiàn)。 后人為了紀(jì)念他， 把整系數(shù)代數(shù)多項(xiàng)式方程統(tǒng)稱為丟番圖方程 (Diophantine Equation)， 而丟番圖本人， 則被一些人尊稱為 “代數(shù)學(xué)之父” (the father of algebra)。
對(duì)于丟番圖方程， 數(shù)學(xué)家們最感興趣的一個(gè)傳統(tǒng)問題乃是它是否有整數(shù)解 (或自然數(shù)解)。 對(duì)于簡(jiǎn)單的丟番圖方程來說， 這是很容易找到答案的， 比如上面提到的 x2+y2=z2 有整數(shù)解 (早在 3000 多年前， 中國(guó)古代的數(shù)學(xué)家就知道這個(gè)方程的一組特解： 即 “勾三股四弦五”)； 另一方面， 2x—2y=1 則沒有整數(shù)解 (因?yàn)榉匠痰淖筮厼榕紨?shù)， 右邊卻為奇數(shù))。 但對(duì)于一般的丟番圖方程來說， 判斷它是否有整數(shù)解卻往往是一件極其困難的事情， 其中最著名的例子就是上面提到過的費(fèi)馬猜想， 即 xn + yn = zn 在 n>2 時(shí)沒有非零整數(shù)解， 它是在隔了 300 多年后才得到的證明[注三]。
長(zhǎng)期以來， 人們對(duì)丟番圖方程是否有整數(shù)解的研究都是針對(duì)特定形式的丟番圖方程進(jìn)行的。 但是， 人們顯然也可以提出這樣一個(gè)問題， 即有沒有辦法對(duì)任意形式的丟番圖方程是否有整數(shù)解進(jìn)行研究？ 或者更具體地說， 是否能找到一種普遍的算法 (algorithm)， 可用來判定一個(gè)任意形式的丟番圖方程是否有整數(shù)解， 從而一勞永逸地解決這類問題？ 這就是著名的希爾伯特第十問題。 這樣的問題在數(shù)學(xué)上被稱為判定問題 (decision problem)， 因?yàn)樗鼘で蟮氖菍?duì)數(shù)學(xué)命題進(jìn)行判定的算法。
希爾伯特是一位對(duì)數(shù)學(xué)充滿樂觀信念的數(shù)學(xué)家。 在他提出希爾伯特第十問題的時(shí)侯， 雖然沒有明確表示那樣的算法一定存在， 但他沒有用 “是否存在那樣的算法” 作為問題的表述方式， 而是直接要求數(shù)學(xué)家們尋找那樣的算法， 可見他對(duì)存在一個(gè)肯定的答案懷有期待。 這種期待與他在其他方面對(duì)數(shù)學(xué)所表示出的樂觀看法是一脈相承的。
但是， 數(shù)學(xué)的發(fā)展卻往往是像希爾伯特那樣的數(shù)學(xué)大師都無法預(yù)料的。
希爾伯特第十問題要求尋找判定丟番圖方程是否有解的算法。 但究竟什么是算法呢？ 在希爾伯特提出問題之時(shí)卻其實(shí)并不存在一個(gè)明確定義。 這是研究希爾伯特第十問題所遇到的第一個(gè)困難。 這一困難使得希爾伯特第十問題在提出后整整 30 年沒有取得任何實(shí)質(zhì)進(jìn)展。
對(duì)算法的研究直到 20 世紀(jì) 30 年代開始才逐漸深入起來。
什么是算法呢？ 粗略且顧名思義地講， 算法就是 (通過有限多的步驟) 對(duì)數(shù)學(xué)函數(shù)進(jìn)行有效計(jì)算的方法。 反過來說， 如果一個(gè)數(shù)學(xué)問題能夠通過可以有效計(jì)算的數(shù)學(xué)函數(shù)得到答案， 那么我們就稱這一數(shù)學(xué)問題存在算法。 因此算法研究的一個(gè)重要的切入點(diǎn)便是尋找可以有效計(jì)算的函數(shù)。 但是， 到底什么樣的函數(shù)是可以有效計(jì)算的呢？ 一開始數(shù)學(xué)家們并沒有普遍結(jié)論， 只知道一些最簡(jiǎn)單的函數(shù) (比如常數(shù)函數(shù))， 以及用那些函數(shù)通過若干簡(jiǎn)單規(guī)則 (比如相加) 組合出來的函數(shù)， 是可以有效計(jì)算的。 數(shù)學(xué)家們將這類函數(shù)稱為遞歸函數(shù) (recursive function)。
1931 年， 年輕的法國(guó)數(shù)學(xué)家赫爾布蘭德 (Jacques Herbrand, 1908-1931) 對(duì)遞歸函數(shù)進(jìn)行了研究， 并給著名邏輯學(xué)家哥德爾 (Kurt G?del, 1906-1978) 寫信敘述了自己的研究結(jié)果。 不幸的是， 哥德爾當(dāng)時(shí)正處于自己一生最重大的成果——哥德爾不完全性定理 (G?del's incompleteness theorems)——的研究期間， 沒有立即對(duì)赫爾布蘭德的工作做出回應(yīng)[注四]。 更不幸的是， 那年的夏天， 年僅 23 歲的赫爾布蘭德在攀登阿爾卑斯山時(shí)不幸遇難， 他的工作因此被暫時(shí)埋沒了起來。
與赫爾布蘭德的研究差不多同時(shí)， 在 20 世紀(jì) 30 年代初的時(shí)侯， 美國(guó)普林斯頓大學(xué) (Princeton University) 的邏輯學(xué)家丘奇 (Alonzo Church, 1903-1995) 也在積極從事邏輯及算法的研究， 并且發(fā)展出了一套新的邏輯體系。 他并且讓自己的兩位學(xué)生——克林 (Stephen Kleene, 1909-1994) 與羅瑟 (John Rosser, 1907-1989)——對(duì)該邏輯體系做進(jìn)一步的細(xì)致研究。 他這兩位學(xué)生都是第一流的學(xué)生， 克林更是后來自己也成為了第一流的邏輯學(xué)家， 他們的研究很快就有了結(jié)果， 但這結(jié)果卻大大出乎丘奇的意料： 他們發(fā)現(xiàn)丘奇的那套體系竟然是自相矛盾的！ 自相矛盾的邏輯體系只能有一個(gè)命運(yùn)， 那就是被放棄。 但幸運(yùn)的是， 丘奇的那套體系中有一個(gè)組成部分仍然是自洽的， 從而可以被保留下來， 那個(gè)組成部分叫做蘭姆達(dá)運(yùn)算 (λ-calculus)。 蘭姆達(dá)運(yùn)算是做什么用的呢？ 它可以用來定義函數(shù)， 而且所有用蘭姆達(dá)運(yùn)算所定義的函數(shù)都是可以有效計(jì)算的。 在對(duì)蘭姆達(dá)運(yùn)算做了研究之后， 丘奇提出了一個(gè)大膽的猜測(cè)， 那就是所有可以有效計(jì)算的函數(shù)都可以用蘭姆達(dá)運(yùn)算來定義。
1934 年， 丘奇向到普林斯頓大學(xué)訪問的哥德爾介紹了這一猜測(cè)， 但哥德爾卻不以為然。 丘奇不服氣， 于是請(qǐng)哥德爾給出一個(gè)他認(rèn)為合適的方法， 來描述可以有效計(jì)算的函數(shù)。 哥德爾沒有讓他久等， 一兩個(gè)月后就給出了一種完全不同的描述。 哥德爾所給出的描述的基礎(chǔ)正是 3 年前赫爾布蘭德在給他的信中敘述的結(jié)果。 哥德爾對(duì)這一結(jié)果進(jìn)行了完善。 這一結(jié)果因此被人們稱為赫爾布蘭德-哥德爾遞歸函數(shù)。
就這樣， 丘奇與哥德爾各自給出了一種體系， 來描述可以有效計(jì)算的函數(shù)。 那么兩者孰是孰非呢？ 丘奇與克林經(jīng)過研究， 很快證明了這兩種看上去完全不同的描述方式實(shí)際上是彼此等價(jià)的。 這兩位著名邏輯學(xué)家的工作殊途同歸大大增強(qiáng)了丘奇的信心， 他相信這就算是找到了可以有效計(jì)算的函數(shù)的普遍定義。 但哥德爾及其他一些人對(duì)此卻仍然懷有疑慮。
最終打消這種疑慮的是英國(guó)數(shù)學(xué)家圖靈 (Alan Turing, 1912-1954)。
圖靈當(dāng)時(shí)對(duì)丘奇及哥德爾在這一領(lǐng)域中的研究并不知情。 他所研究的課題是什么樣的運(yùn)算可以用抽象計(jì)算機(jī)來實(shí)現(xiàn)[注五]。 他的這一研究對(duì)后來計(jì)算機(jī)科學(xué)的發(fā)展起到了深遠(yuǎn)的影響。 在圖靈的研究接近完成的時(shí)侯， 他的導(dǎo)師注意到了丘奇與哥德爾的工作。 于是圖靈對(duì)雙方的工作進(jìn)行了比較， 結(jié)果發(fā)現(xiàn)丘奇與哥德爾所定義的那些函數(shù)與他的抽象計(jì)算機(jī)可以計(jì)算的函數(shù)恰好吻合！ 圖靈把這一結(jié)果作為附錄加進(jìn)了自己的論文中。 這一下就連哥德爾也心悅誠(chéng)服了， 畢竟， 有什么能比在抽象計(jì)算機(jī)上可以直接計(jì)算更接近 “可以有效計(jì)算” 以及算法的基本含義呢[注六]？
在這些有關(guān)算法的研究中， 數(shù)學(xué)家們還提出了一個(gè)重要的概念， 叫做 “遞歸可枚舉集” (recursively enumerable set)。 什么是遞歸可枚舉集呢？ 就是那些由可以有效計(jì)算的函數(shù)所生成的自然數(shù)的集合[注七]。 我們知道， 對(duì)于集合來說， 一個(gè)最基本的問題就是判斷一個(gè)元素是否屬于該集合。 遞歸可枚舉集也不例外。 但是數(shù)學(xué)家們?cè)谘芯窟f歸可枚舉集的時(shí)侯， 卻發(fā)現(xiàn)了一個(gè)十分微妙的結(jié)果， 那就是對(duì)于某些遞歸可枚舉集來說， 我們無法判定一個(gè)自然數(shù)是否屬于該集合！ 換句話說， 有一些遞歸可枚舉集是不可判定的。 這一結(jié)果把對(duì)算法的研究與判定問題聯(lián)系了起來， 為后來解決希爾伯特第十問題埋下了重要的伏筆。
這一系列結(jié)果的出現(xiàn)主要集中在 1936-1937 年間。 那時(shí)侯， 在數(shù)學(xué)中存在無法判定的命題本身已經(jīng)不是一件新鮮事了。 因?yàn)樵缭?5 年前， 哥德爾就已經(jīng)證明了他那著名的不完全性定理， 即任何足夠復(fù)雜并且自洽的數(shù)學(xué)體系都必定包含不可判定的命題[注八]。 但當(dāng)時(shí)已知的不可判定命題大都集中在邏輯領(lǐng)域內(nèi)。 那么在數(shù)學(xué)的其他領(lǐng)域中究竟哪些命題是不可判定的呢？ 這個(gè)問題在整整 10 年之后才開始有答案。
1947 年， 美國(guó)數(shù)學(xué)家波斯特 (Emil Post, 1897-1954) 找到了第一個(gè)邏輯領(lǐng)域以外的不可判定命題。
波斯特是一位有著深刻洞察力的邏輯學(xué)家， 7 歲時(shí)隨父母從波蘭移民到美國(guó)， 是美國(guó)邏輯學(xué)領(lǐng)域的先驅(qū)者之一。 他比哥德爾早了將近 10 年就得到了與哥德爾不完全性定理相似的結(jié)果， 但由于想對(duì)結(jié)果作更全面的分析而沒有及時(shí)發(fā)表。 1936 年， 幾乎與上面提到的哥德爾、 丘奇及圖靈同時(shí)， 波斯特獨(dú)立提出了非常類似于圖靈的結(jié)果。 波斯特同時(shí)還是最早意識(shí)到希爾伯特第十問題可能會(huì)有否定答案的數(shù)學(xué)家之一。 他在 1944 的一篇文章中明確提出希爾伯特第十問題 “期待一個(gè)不可解性證明”。 當(dāng)時(shí)波斯特在紐約市立大學(xué) (The City College of New York) 任教， 他的這一觀點(diǎn)深深地打動(dòng)了一位學(xué)生， 使后者走上了畢生鉆研希爾伯特第十問題的征途。
那位學(xué)生名叫戴維斯 (Martin Davis, 1928-)， 是解決希爾伯特第十問題的關(guān)鍵人物。
二零零五年八月二十四日寫于紐約
二零零五年八月二十六日發(fā)表于本站
二零一三年十一月四日最新修訂
http://www.changhai.org/
站長(zhǎng)近期發(fā)表的作品
網(wǎng)友： 韓雪濤 (發(fā)表于 2009-12-02)
“《算術(shù)》…… 現(xiàn)在流傳于世的有六卷”——1973 年， 人們奇跡般地發(fā)現(xiàn)了四卷先前不為人知的阿拉伯文譯本。因此現(xiàn)在傳世的《算術(shù)》一書有十卷。
另外問盧兄： 介紹馬蒂亞塞維奇研究希爾伯特第十問題的那幾段文字， 兄的資料來自何處？ 打算在自己的書中用一下，是否可以？
網(wǎng)友： 盧昌海 (發(fā)表于 2009-12-02)
歡迎韓兄。
那段文字的資料來源很可能是 Yandell 的《The Honors Class》， 不過我現(xiàn)在不在家， 無法核實(shí)。
關(guān)于韓兄提到的丟番圖的另四卷， Wikipedia 上的說法是： “Of the original thirteen books of which Arithmeticaconsisted only six have survived, though there are some who believe that four Arab books discovered in 1968 arealso by Diophantus”。 按照該說法， 那四卷阿拉伯文發(fā)現(xiàn)于 1968 年， 是否是丟番圖的著作尚無定論。不知韓兄的資料出自何處？ 如果可靠的話， 我將在文末添一個(gè)補(bǔ)注加以說明。
網(wǎng)友： 韓雪濤 (發(fā)表于 2009-12-02)
呵呵， 其實(shí)經(jīng)常光顧兄的個(gè)人主頁。 關(guān)于丟番圖的《算術(shù)》， 看到兄的回貼倒是愣了一下。因?yàn)槲铱吹降闹形馁Y料都是如我上一貼中所說。 現(xiàn)錄李文林主編的《數(shù)學(xué)珍寶——?dú)v史文獻(xiàn)精選》181 頁的一段文字：1973 年， 在伊朗境內(nèi)的馬什哈德又發(fā)現(xiàn) 4 卷阿拉伯文抄本， 據(jù)專家鑒定應(yīng)屬原著第 4、 5、 6、 7 卷 (含 101個(gè)問題)， 而先前的希臘文本則為第 1、 2、 3、 8、 9、 10 卷 (含 189 個(gè)問題)。 另外，國(guó)內(nèi)研究世界數(shù)學(xué)史的梁宗巨在《世界數(shù)學(xué)通史》中， 杜瑞芝主編的《數(shù)學(xué)史辭典》中都是這樣介紹的?？戳诵值幕刭N， 有些不放心， 又查了一本較近出版的《數(shù)學(xué)史通論》中譯本。 書中是這樣介紹的： ……只有六卷在希臘保存下來了，另外有四卷最近發(fā)現(xiàn)了其阿拉伯文的版本， 從其內(nèi)容來看， 它似乎是整部著作中的第 4 到第 7 卷， 隨后才是希臘文的后三卷。……阿拉伯文的那幾卷在風(fēng)格上與希臘文的那幾卷略有不同， 其中對(duì)一個(gè)問題的解的每一步說明得更充分。 因此， 很有可能，這本阿拉伯的著作不是丟番圖原著的譯本， 而是從希帕蒂婭在公元400年左右所寫的《算術(shù)》的注釋本翻譯過來的。
網(wǎng)友： 盧昌海 (發(fā)表于 2009-12-02)
我核對(duì)了一下， 所引資料的確是 Yandell 的《The Honors Class》。
謝謝韓兄提供的有關(guān)《算術(shù)》另四卷的信息， 我在文末加了一個(gè)補(bǔ)注。
網(wǎng)友： 韓雪濤 (發(fā)表于 2009-12-02)
多謝盧兄。
您可在每月前七天參與對(duì)本站所有文章的討論
目前距本文的討論期滿尚有 1 天， 歡迎您
>> 發(fā)表評(píng)論 <<
聯(lián)系客服
