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