計算可能関数
自然数の集合 A が計算可能(帰納的、決定可能)であるとは、数 n に関する計算可能関数 f があり、n が A に属する場合は f ( n ) ↓= 1 {\displaystyle f(n)\downarrow =1} 、そうでない場合は f ( n ) ↓= 0 {\displaystyle f(n)\downarrow =0} となることをいう。
自然数の集合が計算可枚挙(Computably enumerable、帰納可枚挙、準決定可能)であるとは、数 n に関する計算可能関数 f があり、f(n) が n がその集合に属する場合だけ定義されていることをいう。従って、ある計算可能関数の定義域だけが計算可枚挙な集合である。enumerable(可枚挙、枚挙可能)という用語が使われるのは、自然数の空でない部分集合 B について以下が等価であるためである。
B が計算可能関数の定義域である。
B が全域計算可能関数の値域である。B が無限である場合、その関数は単射と見なされる。
集合 B が関数 f の値域である場合、その関数は B の列挙と見ることができる。というのも、f(0), f(1), ... というリストが B の全ての元を含むからである。
自然数における有限関係には自然数の有限な数列の集合が対応するので、計算可能関係(computable relation)や計算可枚挙関係(computably enumerable relation)は、集合からのアナロジーで定義できる。
このような関数は全て計算可能である。πの十進表現に '5' が任意の桁数連続して出現する場所があるかは不明なので、「どの」関数が f なのかを知ることは出来ない。けれども、どれが関数 f だろうとも、それが計算可能であることに変わりは無い訳である)
自然数の計算「不能」な数列(例えばビジービーバー関数)の有限な各部分は計算可能である。例えば、有限な数列 Σ(0), Σ(1), Σ(2), ..., Σ(n) — を計算するアルゴリズムは存在する。これはΣの数列「全体」(つまり全ての n についての Σ(n))を計算するアルゴリズムが存在しないことと対照的である。かくして、「0, 1, 4, 6, 13 を印字せよ」というアルゴリズムは、Σ(0), Σ(1), Σ(2), Σ(3), Σ(4) を計算する問題への自明な答になっている。同様に、全ての n について、Σ(0), Σ(1), Σ(2), ..., Σ(n) を計算するような自明なアルゴリズムが「存在」する(尤も、それが実際に「発見」されたり書かれたりすることは無いかも知れないが)。