|
與圖林同時(shí)，美國(guó)數(shù)學(xué)家波斯特也發(fā)表了一篇文章，類似于圖林的可計(jì)算函數(shù)，他的文章過(guò)于簡(jiǎn)短，
一直到1943年波斯特才發(fā)表了第四個(gè)表述，結(jié)果證明他的與別人的也都一樣。
遞歸的概念并不難理解，它就是由前面的結(jié)果可以遞推得到后面的結(jié)果。哥德爾等人引進(jìn)的實(shí)際上是一般遞歸函數(shù)，一股遞歸函數(shù)都可以由原始遞歸函數(shù)算出來(lái)。
另一個(gè)復(fù)雜一些的概念稱為遞歸集合S，它的定義是存在一種能行的辦法來(lái)判斷任何正整數(shù)n是否屬于S。正數(shù)數(shù)集合是遞歸的當(dāng)且僅當(dāng)它與它在N中的補(bǔ)集都是遞歸可枚舉的。任何無(wú)窮遞歸可枚舉集都包含一個(gè)無(wú)窮遞歸集。但是，存在正整數(shù)的遞歸可枚舉集而不是遞歸集。
于是波斯特提出問(wèn)題：是否存在兩個(gè)遞歸可按舉但是非遞歸的集合，使得第一個(gè)集合相對(duì)于第二個(gè)是遞歸的，但第二個(gè)相對(duì)于第一個(gè)卻不是遞歸的。一直到十二年后的1956年，蘇聯(lián)人穆其尼克及美國(guó)人弗里德伯格才獨(dú)立地肯定地解決了這個(gè)問(wèn)題。
蘇聯(lián)數(shù)學(xué)家馬爾科夫在1947年發(fā)表《算法論》，首先明確提出算法的概念。但是它同以前定義的遞歸函數(shù)及可計(jì)算函數(shù)的計(jì)算過(guò)程都是等價(jià)的。這幾個(gè)定義表面上很不相同，并有著十分不同的邏輯出發(fā)點(diǎn)，卻全都證明是等價(jià)的。這件事看來(lái)決非巧合。它表明：所有這些定義都是同一個(gè)概念，而且這個(gè)概念是自然的、基本的、有用的。這就是“算法”概念的精確的數(shù)學(xué)定義。大家都接受了這個(gè)定義之后，判定問(wèn)題從我們平時(shí)直觀的概念也上升為精確的數(shù)學(xué)概念，判定問(wèn)題也成為一門數(shù)理邏輯的重要分支了。從這時(shí)起，判定問(wèn)題有突飛猛進(jìn)的發(fā)展。
判定問(wèn)題有了精確的數(shù)學(xué)表述之后，立即在數(shù)學(xué)基礎(chǔ)乃至整個(gè)數(shù)學(xué)中產(chǎn)生了巨大的影響。因?yàn)檫@時(shí)一些不可判定命題的出現(xiàn)，標(biāo)志著人們?cè)跀?shù)學(xué)歷史上第一次認(rèn)識(shí)到：有一些問(wèn)題是不可能找到算法解的。在過(guò)去，人們一直模模糊糊地覺(jué)得，任何一個(gè)精確表述的數(shù)學(xué)問(wèn)題總可以通過(guò)有限步驟來(lái)判定它是對(duì)還是錯(cuò)，是有解還是沒(méi)有解。找到不可判定問(wèn)題再一次說(shuō)明用有限過(guò)程對(duì)付無(wú)窮的局限性，它從另外一個(gè)角度反映了數(shù)學(xué)的內(nèi)在固有矛盾。
怎樣得到這些結(jié)果的呢？丘奇的論點(diǎn)發(fā)表之后，不難看出存在不可計(jì)算的函數(shù)，也就是非一般遞歸的函數(shù)。因?yàn)樗锌赡懿煌乃惴ü灿锌蓴?shù)無(wú)窮多(粗淺來(lái)講，算法都是用有限多個(gè)字來(lái)描述的)，可是所有數(shù)論函數(shù)的集合卻是不可數(shù)的。
不過(guò)，頭一個(gè)明顯的不可判定的結(jié)果是1936年丘奇得到的。他首先得到與λ可定義性有關(guān)的不可判定結(jié)果。然后，他把這個(gè)結(jié)果應(yīng)用到形式系統(tǒng)的判定問(wèn)題上，特別他證明，形式化的一階數(shù)論N是不可判定的。也是在1936年，丘奇證明純粹的謂詞演算也是不可判定的。當(dāng)時(shí)大家的反應(yīng)是：這種不完全性的范圍到底有多廣？
甚至于象丘奇這樣的數(shù)學(xué)家，也想找到一條出路能避開哥德爾的結(jié)果。比如說(shuō)，可以采用伺哥德爾所用的系統(tǒng)完全不同的其他的特殊系統(tǒng)。一旦算法的精確定義和丘奇論點(diǎn)出現(xiàn)之后，大家就認(rèn)識(shí)到躲不過(guò)哥德爾不完全性定理的影響，可計(jì)算性和不完全性這兩個(gè)概念是緊密聯(lián)系在一起的。
實(shí)際上克林在1936年就證明了(作為丘奇論點(diǎn)的應(yīng)用)：甚至在能夠能行地認(rèn)出公理和證明的形式系統(tǒng)中，哥德爾的定理仍然成立。消去量詞方法對(duì)許多理論行不通。一般的判定問(wèn)題是試圖找出一個(gè)能行的步驟，通過(guò)這個(gè)步驟可以決定什么東西具有某種指定的元數(shù)學(xué)特征。
在純粹邏輯演算的元理論中，有最明顯的一類判定問(wèn)題：對(duì)于給定的演算和給定類的公式，求出一個(gè)步驟，能夠在有限多步內(nèi)判定這類的任何特殊公式是否可以形式地推導(dǎo)出來(lái)。有些情形、問(wèn)題已經(jīng)得到肯定的解決，在另外一些情形，答案是否定的，可以證明不存在這樣一個(gè)步驟。這種否定的證明，特別對(duì)于數(shù)學(xué)理論，很大程度上依賴于遞歸論。
最早明確提出的數(shù)學(xué)判定問(wèn)題是希爾伯特第十問(wèn)題。他在1900年國(guó)際數(shù)學(xué)家大會(huì)上提出了著名的二十三個(gè)問(wèn)題，其中第十個(gè)問(wèn)題是：給定一個(gè)有任意多未知數(shù)的、系數(shù)為有理整數(shù)的丟番圖方程，設(shè)計(jì)一個(gè)步驟，通過(guò)它可以經(jīng)有限步運(yùn)算判定該方程是否有有理整數(shù)解。這個(gè)到1970年才被否定解決的問(wèn)題不僅解決了一個(gè)重大問(wèn)題，而且解決問(wèn)題過(guò)程中所得到的工具和結(jié)果對(duì)數(shù)理邏輯和數(shù)學(xué)發(fā)展有著極大影響，比如表示素?cái)?shù)的多項(xiàng)式，尤其與整個(gè)數(shù)理邏輯有關(guān)的是得出了一個(gè)更確切的哥德爾不完全性定理。
現(xiàn)在我們來(lái)看希爾伯特第十問(wèn)題，為了清楚起見(jiàn)，我們考慮多項(xiàng)式方程，看看一般的多項(xiàng)式丟番圖方程的次數(shù)和未定元的數(shù)目是否可以降低。
1938年斯科蘭姆證明，任何丟番圖方程的次數(shù)可約化成次數(shù)小于等于4的方程；1974年馬蒂亞謝維奇和羅濱遜證明未定元的數(shù)目可約化成小于等于3。對(duì)于齊次方程，阿德勒在1971年證明，任何齊次方程可以能行地約化為二次齊次方程組，從而等價(jià)于一個(gè)四次齊次方程。對(duì)于一次方程早就有具體方法解丟番圖方程了。對(duì)于任意多未定元的二次方程，1972年西格爾也找到一個(gè)算法。四次方程不能判定，三次方程尚不知道。
解決丟番圖方程解是否存在的判定問(wèn)題的方法是引進(jìn)丟番圖集。我們把丟番圖方程的變?cè)殖蓛捎幸唤M解。每個(gè)丟番圖集合是遞歸可枚舉集。1970年，蘇聯(lián)大學(xué)生馬蒂亞謝維奇證明了每個(gè)遞歸可枚舉集也是丟番圖集合。這樣一來(lái)，由于存在不可判定的遞歸可枚舉集，所以存在一些特殊的丟番圖方程，使得對(duì)是否有解的判定問(wèn)題不可解。當(dāng)然對(duì)一般丟番圖方程的判定問(wèn)題就更不可解了。
另一個(gè)判定問(wèn)題是半群和群論中字的問(wèn)題，半解問(wèn)題是挪威數(shù)學(xué)家圖埃在1907年首先提出來(lái)的。問(wèn)題是對(duì)于一個(gè)半群，如果給定它的有限多生成元和有限多關(guān)系，那么能否找到一個(gè)方法來(lái)判定任何一個(gè)特殊的字是否等于單位元素。1947年，波斯特否定地解決了這個(gè)問(wèn)題。
群論中字的問(wèn)題更為重要，它是在1911年由德恩首先研究的，一直到1955年才由蘇聯(lián)數(shù)學(xué)家諾維科夫否定解決。這些結(jié)果給數(shù)學(xué)家指明了新的方向：不要妄圖去解決一大類問(wèn)題。不過(guò)對(duì)于更窄的一類的對(duì)象比如一類特殊的群，群的字問(wèn)題是可解的。
|
