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