原始再帰関数
原始再帰関数は、計算可能関数とはどのようなものである筈か、という直観と密接に関連する。出発点となる原始再帰関数は(非常に単純なので)直観的に計算可能であり、そこから新たな原始再帰関数を作るための二種類の操作に関しても、具体的に関数値を計算する手続きを与えている。しかし、原始再帰関数の集合に全ての計算可能(全域)関数が含まれるわけではない。(この節の最後に列挙してある具体例を反例として示すことでも証明にはなるが、)カントールの対角線論法を応用して、原始再帰的でない計算可能関数が存在することを証明できる。証明の概略は次の通り:
原始再帰関数の全体は計算的枚挙可能(=帰納的可算)である。すなわち、2変数の計算可能関数 f {\displaystyle f} であって、 f ( i , ⋅ ) ( i ∈ N ) {\displaystyle f(i,\cdot )(i\in \mathbb {N} )} がちょうど原始再帰関数全体と一致するようなものが存在する。この f ( i , ⋅ ) {\displaystyle f(i,\cdot )} を f i {\displaystyle f_{i}} と書くことにする。原始再帰関数 g {\displaystyle g} に対して g = f i {\displaystyle g=f_{i}} なる i {\displaystyle i} は一意的とは限らない。。
次のような無限×無限行列を考える。第 i {\displaystyle i} 行の第 j {\displaystyle j} 列には f i ( j ) {\displaystyle f_{i}(j)} の値が書かれているものとする。