本 エッセー では、チューリング・マシーン の考えかたを 「簡単な」 例題で示しました。前回、「帰納的」 という概念と 「帰納的に可算」 という概念はちがうことを述べました。「帰納的」──S ⊆ N が空でないとして── を チューリング・マシーン M を使って言い換えれば、特徴関数 C_Sが計算可能なので、x ∈ S あるいは ¬ （x ∈ S） の いずれの場合でも、チューリング・マシーン は、C_Sを有限の時間内で判断できる、ということです。

　「instruction （q, s, q’, s’, x）」──あるいは、M による 「特徴関数の 『計算 （computation）』」──は、δ├ M の 2項関係として、「閉含 （closure）・外点 （exterior point）」 という概念を使って考えることもできます。├ M に対して、反射的・推移的閉含 ├ M^* を考えます。「閉含」 とは、位相空間 S の部分集合 M に対して、M の 「外点」 の集合 M^e ＝ (M^c)ⁱ の補集合 （M^e)^c ＝ ((M^c)ⁱ)^c　のことを云い、Mで表します。したがって、M⊃M が成り立ちます。簡単に云えば、「M は M をふくむ最小限の閉集合」 のことです。なお、S の点 p が M の 「外点」 であるとは、p が M の補集合 M^c の内点になっていることです。

　チューリング・マシーン で計算可能ということは、S ⊆ N のなかで、δ├ M の初期状態で始まり、├ M^* の内点に終わる関数がある、ということです。すなわち、(x1,・・・, xn) q₀B ├ M^* f (x1,・・・, xn) q_hB となる q_h が存在する、ということです。逆の言いかたをすれば、上述した式を満たす チューリング・マシーン が存在するとき、関数 f は 「部分的に計算可能 （partially computable）」 であると云います。そして、関数 f が全域的かつ部分的に計算可能であるとき、チューリング・マシーン は f を計算する （compute） と云います [ 「全域的」 は、「ベーシックス」 144ページ を参照されたい。]

　チューリング・マシーン で数論的関数を計算するためには、対象を ゲーデル 数化すれば良いでしょう。
　以下の n ＋ 2 変数述語を考えてみます。

　　　　T_n (z, x₁,・・・, x_n, y).

　y は、ゲーデル 数 z である チューリング・マシーン M による初期状態 (x1,・・・, xn) q₀B に始まり、wq_hB に終わる ゲーデル 数です。そして、x が ゲーデル 数であるとき、その最後の関数値を取り出す原始帰納的関数 U を用意します。そして、f (x₁,・・・, x_n) を部分的に計算可能な関数として、それを部分的に計算する チューリング・マシーン を M として、M の ゲーデル 数を k とすれば、以下が成立します。つまり、f は、帰納的部分関数です。

　　　f (x₁,・・・, x_n) ←→ U (μyT_n (k, x₁,・・・, x_n, y)).

　ちなみに、チューリング・マシーン は、「計算する」 configuration なので、プログラム のことであると言って良いでしょう。ただ、任意の チューリング・マシーン M と、その入力 データ を前提にして、M が データ に対する動作を 「解釈」 する チューリング・マシーン U を考えることができます──言い換えれば、U が存在します。その U のことを 「universal machine （万能機械）」 と云います。この U が、現代の コンピュータ です。

　さて、応用問題として、以下の事態が 「決定可能」 かどうか を考えてみましょう。

　　　　任意に与えられた チューリング・マシーン （Q, M, t, q₀, F） に対して、xq₀B で始まり、wq_hB に
　　　　終わる M による計算が存在するかどうかを決定する アルゴリズム を作りなさい。