數理邏輯、數學和電腦理論科學所研究的一個重要課題。數學中很多定理，尤其是存在性定理往往不是能行的，如雖然已經證明瞭某某方程有根，但卻無法求出其根，甚至無法求得比較精確的近似值。對很多數學傢尤其是採用直覺主義或構造主義觀點的數學傢說來，欠缺能行性的定理是不能接受的。然而對於所謂“能行性”，長期以來都未有精確的定義，以致於很難對之作深入的探討。
原始遞迴函數(見遞迴論)是處處可以計算的，它又包括瞭人們在數論中所曾使用過的數數論函數，看來似乎可把“能行可計算函數”限於原始遞歸函數。對此，德國數學傢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)的真假。