評論(0

能行性和一般遞歸

標籤: 暫無標籤

數學中很多定理,尤其是存在性定理往往不是能行的,如雖然已經證明了某某方程有根,但卻無法求出其根,甚至無法求得比較精確的近似值。對很多數學家尤其是採用直覺主義或構造主義觀點的數學家說來,欠缺能行性的定理是不能接受的。然而對於所謂"能行性",長期以來都未有精確的定義,以致於很難對之作深入的探討。

1 能行性和一般遞歸 -能行性和一般遞歸

 

2 能行性和一般遞歸 -正文

  數理邏輯、數學和計算機理論科學所研究的一個重要課題。數學中很多定理,尤其是存在性定理往往不是能行的,如雖然已經證明了某某方程有根,但卻無法求出其根,甚至無法求得比較精確的近似值。對很多數學家尤其是採用直覺主義或構造主義觀點的數學家說來,欠缺能行性的定理是不能接受的。然而對於所謂"能行性",長期以來都未有精確的定義,以致於很難對之作深入的探討。
  原始遞歸函數(見遞歸論)是處處可以計算的,它又包括了人們在數論中所曾使用過的數論函數,看來似乎可把"能行可計算函數"限於原始遞歸函數。對此,德國數學家W.阿克曼於1924年構造了一個數論函數,它是可計算的,但是卻不是原始遞歸函數,從而推翻了上述猜想。1932年,美國數學家A.丘奇提出了λ換位演算。在這演算內可以表示自然數,並且利用運運算元λ而作出了λ可定義函數,其中包括原始遞歸函數。1934年,K.哥德爾根據J.赫爾布蘭德的一個建議,提出了一般遞歸函數。其定義是:如果能夠作出一組方程式,使得只利用變元代以常數以及相等的數可以彼此替換兩個過程,便能夠導出函數f的一切值,而函數f便叫做一般遞歸函數。不久,美國學者S.C.克利尼證明了這個一般遞歸函數與丘奇的λ可定義全函數是相同的,並且也與使用疊置、原始遞歸式和摹狀運算元而得到的全函數相同。1936年,英國數學家A.M.圖林提出以其姓命名的圖林機器理論,並證明了可用圖林機器計算的數論全函數恰好是λ可定義全函數。由於這些函數類都比原始遞歸函數類更廣泛而又彼此相等,因此丘奇也於1936年提出了一個論題,即能行可計算的全函數類恰好是λ可定義全函數類,也就是一般遞歸函數類。後來發現,把能行可計算性推廣到部分函數更有意義也更重要。於是,丘奇的論題便成為:能行可計算的部分函數恰好是遞歸部分函數,而能行可計算的全函數也恰好是遞歸全函數,亦即一般遞歸函數。
  根據丘奇的論題,便可以對判定問題作進一步的討論。
  判定問題分問答題與求作題兩種。要求回答"是""否"的叫做問答題,要求用一個自然數回答的叫做求作題。例如,"3整除 5嗎?"是問答題,"求m,n之積"是求作題。問題又分個別題與大量題兩種。如果在問題中已給出全部數據,因而當時已有具體而明確答案的叫做個別題;問題中並未給出全部數據而含有參數,須把參數代以具體數值后才能作出答案的叫做大量題。對個別題除要求答案正確外,別無要求。對大量題則一般要求在未給出參數的值時,先有一個公共的解法,參數值給出后,即能按這個公共解法而求得答案。例如,把求作題的答案看作參數 m,n的函數f(m,n),把問答題本身看作參數m,n的謂詞P(m,n),則求作題就是求函數f(m,n)的值,而問答題則是判定謂詞P(m,n)的真假。如果函數f(m,n)是遞歸全函數即一般遞歸函數,該問題就可以完全解決。因為, m,n給出后必能求得f(m,n)之值作為答案。如果f(m,n)是遞歸部分函數,而且能夠判知f(m,n)有無定義,這時 f(m,n)叫做潛伏遞歸函數。那末,當m,n 的值給出以後,就可以判定f(m,n)有無定義,若有定義必定可求得 f(m,n) 的值作為答案,若無定義亦可用"無定義"作為答案。所以,對這個問題仍是可以完全解決的。如果f(m,n)是遞歸部分函數而且不是潛伏遞歸,則當m,n的值給出后,只能假定它有定義而計算下去。這樣,若f(m,n)有定義,必可求得其值作為答案;若f(m,n)沒有定義,計算過程則有可能永無休止地繼續下去而無法給出答案。對此,就可以說這個問題是可以半解決的,因為它只要有答案必能給出。如果f(m,n)不是遞歸半函數,即使f(m,n)有值也未必能算出,因此說這個問題是完全不可解決的。
  對於問答題P(m,n)可先引進它的特徵函數 f(m,n),當P(m,n)成立時,f(m,n)=0;當P(m,n)不成立時,f(m,n)=1。如果f(m,n)為遞歸全函數,則可以說這個問答題是完全可以判定的。因為,m,n給出后,必可判定P(m,n)的真假。如果 f(m, n)不是遞歸全函數,則不應馬上說這個問題完全不可解。這時,先引進兩個部分函數如下:f1(m,n)=0當P(m,n)成立時,否則作為無定義;f2(m,n)=0當P(m,n)不成立,否則作為無定義。如果f1(m,n) 是遞歸部分函數,則可說問答題P(m,n)是可正半判定的;如果 f2(m,n)是遞歸部分函數,則問答題P(m,n) 是可負半判定的。如果 f1與f2都不是遞歸半函數,便可說問答題是完全不可判定的。容易證明,如果 f1(m,n)與f2(m,n)都是遞歸半函數,亦即如果問答題P(m,n)既可正半判定又可負半判定,那末P(m,n)便是完全可判定的。因為,人們可以同時計算 f1(m,n)與f2(m,n),結果必有一函數有值,從而可以判定P(m,n)的真假。

 

3 能行性和一般遞歸 -配圖

 

4 能行性和一般遞歸 -相關連接

上一篇[張文偉]    下一篇 [穆切]

相關評論

同義詞:暫無同義詞