原始再帰関数
この行列の対角線部分に注目する。
関数 g ( x ) := f x ( x ) + 1 {\displaystyle g(x):=f_{x}(x)+1} を考える。 g {\displaystyle g} は上記の行列の対角線上の値に 1 を加えた値を返す関数である。この関数は計算可能だが、如何なる原始再帰関数もこの関数を計算できないことが明らかである。何故ならどのような原始再帰関数も、この関数とは対角線部分において値が異なるからである。従って原始再帰的でない計算可能関数が存在する。
この論法は枚挙可能な(全域)計算可能関数の任意のクラスに適用できる。別記事 (en) を参照のこと。ただし、部分計算可能関数は、例えばチューリングマシンでの符号化を使って番号付けするなどの方法で、明確に枚挙可能である。
全域再帰的だが原始再帰的でない関数として、他にも次のような例が知られている:
アッカーマン関数 A ( x , y ) {\displaystyle A(x,y)} や2つの引数に同じ値を与えた関数 A ( x , x ) {\displaystyle A(x,x)} は全域再帰的だが原始再帰的ではない。
クヌースの矢印記法は全域再帰的だが原始再帰的でない。アッカーマン関数はクヌースの矢印記法による表示を持つ。
グジェゴルチク階層の初期関数 E i ( x ) {\displaystyle E_{i}(x)} は2変数関数として全域再帰的だが原始再帰的ではない。
パリス・ハリントンの定理は、原始再帰的でない全域再帰関数に関わる。この関数はラムゼー理論に基づいているため、アッカーマン関数よりも「自然」だと言われることがある。
スーダン関数
グッドスタイン関数(英語版)