告子

[拼音]:nengxingxing he yiban digui

[英文]:effectiveness and general recursiveness

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

原始遞迴函式(見遞迴論)是處處可以計算的,它又包括了人們在數論中所曾使用過的數論函式,看來似乎可把“能行可計算函式”限於原始遞迴函式。對此,德國數學家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)的真假。