再帰理論
Cutland(1980)によればそれは部分再帰関数(入力値によっては動作が未定義となる関数)を意味し、Soare(1987)によれば、それは全域再帰関数(一般再帰関数)を意味する。この記事では後者の意味で用いる。Soare(1996)には、他にも用語についてのコメントがある。
自然数の集合は常に計算可能という訳ではない。チューリングマシンの停止問題は、0を入力したとき停止するチューリングマシン(についての記述)の集合だが、計算不可能な集合のよく知られた例である。計算不可能な集合が多数存在することは、次の事実から明らかである。つまり、チューリングマシンは枚挙可能(可算)な個数しか存在しないから、計算可能集合も枚挙可能な個数しか存在しないが、自然数から作る集合は枚挙不可能(非可算)な数だけ存在する。
停止問題は計算可能ではないが、プログラムの実行をシミュレートし、実際に停止するプログラムの無限のリストを作成することは可能である。すなわち、停止問題は帰納的可算集合(計算枚挙可能、半決定可能などとも)の例であり、チューリングマシンによって枚挙可能な集合である。同様に、ある集合が帰納的可算であることの必要十分条件は、それが空であるか、または何らかの計算可能関数の値域に等しいことである。帰納的可算集合は一般には決定不能だが、再帰理論が最も詳しく研究してきた領域である。
チャーチ(1936a、1936b)とチューリング(1936)はゲーデルの不完全性定理の証明(1931)で用いられた技法に触発され、それぞれ独立に、ダフィット・ヒルベルトが1928年に提示した Entscheidungsproblem(決定問題)(en)が実効的に決定できないことを示した。この結果は、任意の数学的命題が真か偽かを正しく判定するアルゴリズムが存在しないことを明らかにした。
これらの初期の例に続いて、多くの数学問題が決定不能であることが示された。1947年、Markov とポストはそれぞれ独立に半群の word problem が実効的に決定できないことを示す論文を発表した。その結果に基づき、1950年代、Pyotr Sergeyevich Novikov (en)と William Boone はそれぞれ独立に群の word problem (en)が実効的に解けないことを示した。これは有限に表現された群におけるある語(word)が与えられたとき、その語が指す元がその群の単位元かどうかを実効的に決定する手続きが存在しないということである。1970年、ユーリ・マチャセビッチはマチャセビッチの定理(en)を証明し、その系としてヒルベルトの第10問題が実効的な解法を持たないことを示した。この問題は整数上で定義されたディオファントス方程式が整数解を持つかどうかを判定する手続きを求めるものであった。
何らかの数学的行為が実効的に実行できるかを問う研究は、ときに再帰数学と呼ばれることがある。Handbook of Recursive Mathematics (Ershov他、1998)はこの分野の成果を多数紹介している。
上述のような再帰的な集合や関数の理論を出発点として、再帰理論は関連する主題を巻き込んで成長してきた。以下に挙げるのはそれぞれ独立した研究分野というわけではない。各分野は結果や考え方を相互に応用しており、再帰理論の研究者であればこれらの大半に親しんでいる。