Μ再帰関数
クリーネは以下の最終定理で、「チューリングマシンによる計算可能関数」と「部分μ再帰関数」が等価であることを示した。
次のクラスの部分関数は同一の広がりを持つ。すなわち、同じメンバーを持つ。 (a) 部分再帰関数 (b) 何らかの機械で計算可能な関数 (c) 1/1 関数(チューリングマシンを一方向のテープと1つのシンボルだけに制限したもの)
さらに、これらは私が定義した関数 Ψ とも同一の広がりを持つ。(Kleene p. 376)
クリーネはこれを証明するために、5つの原始再帰関数の作用素とμ作用素をチューリングマシンでエミュレートできることを示し、逆にチューリングマシンの動作を数値化することでその動作をμ再帰関数で表現できることを示した。