私は、数学の専門家ではないので、本 エッセー のなかに示した いくつかの計算可能関数を詳しく研究した訳ではないことを断っておきます。帰納的関数を学習するには、以下の書物を読んで下さい。

　（1） 「帰納的関数」、廣瀬 健、共立出版、1989年。
　（2） 「帰納的関数と述語」、篠田寿一、河合文化教育研究所、1997年。

　いずれの書物も 「本格的な」 入門書です──「数学基礎論」 を専門的に志すひと向けの書物でしょうね。私は、いずれも、途中で挫折して読破していないことを正直に告白しておきます。私が習得している知識は、前々回 （160ページ 参照） に記述した 「原始帰納的関数」 （と 「帰納的に可算」の概念） 程度です。そして、本 エッセー で述べた いくつかの計算可能関数を丁寧に学習しないまま、 「計算可能関数 ＝ アルゴリズム」 として覚えて──数学の専門家たちが それを証明しているので、ただただ、信んじて──、それを前提にして、チューリング・マシーン を やや丁寧に学習した、という次第です。数学者に怒られるかもしれないのですが、数学を専門にしていない エンジニア は、本 エッセー で示した計算可能関数のすべてを丁寧に学習しなくてもいいでしょう。

　N を自然数の全体として、集合 S ⊆ Nⁿ に対して、(x₁, x₂, ... , x_n) ∈ S のとき 0 、そうでないとき 1 を対応させる関数 C_p (x₁, x₂, ... , x_n) を S の 「特徴関数 （characteristic function）」 と云い、C_p が 「原始帰納的」 なら、P を 「原始帰納的述語」 と云います。
　原始帰納的関数は、ほとんどの関数をふくんでいて、コンピュータ で扱う関数のほとんどが原始帰納的関数であるといっても良いそうです。ただし、原始帰納的関数は計算可能な すべての関数をふくんでいる訳ではないそうです──たとえば、アッケルマン 関数は原始帰納的関数ではないとのこと。

　さて、P を n ＋ 1 変数述語として、(x₁, x₂, ... , x_n) に対して、P (x₁, x₂, ... , x_n, y) を真にする最小の y を考えて、y が存在しないときには、無定義 （undefined） である n 変数関数を μyP (x₁, x₂, ... , x_n, y) とします。なお、μy を μ-operator と云います。

　「帰納的部分関数」 とは、原始帰納的関数の初期関数からはじめて、原始帰納的関数を作る操作を適用して、さらに、以下の関数 f を作る操作を有限回適用して得られる関数を云います。なお、「無定義・部分関数・全域関数」 の定義については、本 ホームページ 144 ページ を参照して下さい。

　　　　g (x₁, x₂, ... , x_n, y).
　　　　f (x₁, x₂, ... , x_n) ＝ μy (g (x₁, x₂, ... , x_n, y) ＝ 0).

　もし、g (x₁, x₂, ... , x_n, y) ＝ 0 となる y が存在しなければ、関数 g が全域的であっても、関数 f は定義されないので、関数 f は全域的であるとは限らないでしょうね。
　さて、任意の (x₁, x₂, ... , x_n) ∈ Nⁿ に対して、g (x₁, x₂, ... , x_n, y) ＝ 0 となる y が、つねに、存在するとき、関数 g を 「正則 （regular）」 であると云います。そして、μ-operator を正則関数に対して適用して得られる帰納的部分関数を 「帰納的関数」 または 「一般帰納的関数」 と云います。集合や述語が 「帰納的」 であるという意味は、その特徴関数が帰納的であるということです。

　集合 N の部分集合 S が 「帰納的に可算」 であるとは、以下の帰納的関数 f が存在するときです （空集合もふくみます）。

　　　　f (N) ＝ { f (0), f (1), ・・・ } ＝ S.

　ちなみに、このとき、 f は、S を列挙する （enumerate） と云います。
　さて、帰納的集合 S ⊆ N は帰納的に可算ですが、その逆は真ではない。すなわち、「帰納的に可算な集合」 と 「帰納的集合」 は、ちがう、という点に注意して下さい。「帰納的に可算な集合」 A において、x ∈ A であるかどうかは、列挙していけば、x が、いずれ、現れるかもしれないのですが、もし、列挙が 「無限」 に続くのであれば、¬ （x ∈ A） を判断できないかもしれない。「帰納的集合」 であれば、その特徴関数 C_Sが計算可能であるので、x ∈ S であるか、¬ （x ∈ S） であるかを判断できます。
　なお、S ⊆ N が帰納的に可算であって、かつ、その補集合 S^c ＝ N − S が帰納的に可算であれば、S は帰納的です。

　「任意の (x₁, x₂, ... , x_n) ∈ Nⁿ に対して、P (x₁, x₂, ... , x_n) が成立するかどうかを決定する」 アルゴリズム の作成を 「決定問題 （decision problem）」 と云います。もし、このような アルゴリズム を作ることができるなら、P は帰納的 （計算可能） であるということです。同じように、集合 S ⊆ Nⁿ についても、「任意の (x₁, x₂, ... , x_n) ∈ Nⁿ に対して、(x₁, x₂, ... , x_n) ∈ S が成立するかどうかを決定する」 アルゴリズム の作成も 「決定問題」 と云います。ちなみに、もし、自然数以外の集合 （あるいは、述語） であれば、ゲーデル 数を使って、自然数の対応することができます。そして、決定できる アルゴリズム を作ることができれば 「決定可能 （decidable、あるいは solvable）」 と云い、そうでなければ 「決定不能 （undecidable、あるいは unsolvable）」 と云います。