再帰理論
数理論理学において、計算可能性とその一般化を研究する分野は、「再帰理論」と呼ばれてきた。Robert I. Soare は1996年、これを「計算可能性理論; computability theory」と呼ぶことを提案した。彼は、クリーネの「再帰; recursive」という用語よりもチューリングの「計算可能; computable」という用語の方が自然で判り易いと主張している。そのため、近年では計算可能性理論と呼ぶ研究者が増えている。同時に「部分計算可能関数」や「計算可枚挙」といった用語が、「部分再帰関数」や「帰納的可算」といった用語の代わりとして使われるようになっている。しかし、Fortnow や Simpson のようにまだ納得していない研究者もいる。また、「再帰理論」にしても「計算可能性理論」にしても、研究対象のほとんどが計算可能でないことを表せていない点を指摘する人もいる。
再帰理論における計算可能性の研究はチューリング(1936)に端を発している。自然数の集合と自然数 n を考える。n がその集合の元なら 1 を返して停止し、そうでないなら 0 を返して停止するチューリングマシンが存在するなら、その集合は帰納的集合(または、決定可能集合、計算可能集合、チューリング計算可能集合とも)と呼ばれる。自然数から自然数への関数 f があるとする。任意の自然数 n を入力されたときに f(n) を出力して停止するチューリングマシンが存在するとき、その関数を再帰関数あるいは(チューリング)計算可能関数と呼ぶ。ここでは定義に必ずしもチューリングマシンを持ち出す必要はない。チューリングマシンと同等の能力を持つ計算模型は他にも存在する(例えば、原始再帰関数とμ作用素からなるμ再帰関数)。
再帰関数と集合に関する用語は完全に一定しているわけではない。μ再帰関数による定義や、ゲーデルによる rekursiv(再帰)関数の定義から、伝統的に「再帰的; recursive」という言葉でチューリングマシンで計算可能な集合や関数を意味するようになった。「決定可能; decidable」という用語はチューリングらが論文で使っていたドイツ語 Entscheidungsproblem に由来する。現在では「計算可能関数; computable function」という用語には様々な定義がある。