計算可能関数 | 計算理論

1 部分関数と Turing 計算可能性

部分関数 $f\colon\mathbb N^k\rightharpoonup\mathbb N$ が $\vec x$ で定義されることを $f(\vec x)\mathord\downarrow$ 、定義されないことを $f(\vec x)\mathord\uparrow$ と書く。

定義 1.1. 部分関数 $f\colon\mathbb N^k\rightharpoonup\mathbb N$ が部分 Turing 計算可能 (partial Turing computable) であるとは、次を満たす決定性 TM $M$ が存在することをいう。

$f(\vec x)\mathord\downarrow$ ならば、 $M$ は入力 $1^{x_1}\#\cdots\#1^{x_k}$ から開始し、有限時間後に受理状態 $q_{\mathrm{acc}}$ で停止する。この停止配置では、ヘッドは位置 $0$ にあり、テープ内容は $0\le i<f(\vec x)$ で $T(i)=1$ 、 $i\ge f(\vec x)$ で $T(i)=\sqcup$ を満たす。
$f(\vec x)\mathord\uparrow$ ならば、 $M$ はその入力で停止しない。

(1)の停止配置を正規出力配置 (normal output configuration) という。定義域が $\mathbb N^k$ 全体である部分 Turing 計算可能関数を全域 Turing 計算可能関数 (total Turing-computable function) という。

証明中では、入力の保存領域、作業用カウンタ、および出力領域を別々のテープに置くことがある。次の補題により、このような多テープ機械から、同じ関数を定義の正規出力配置で計算する単テープ機械を構成することができる。

補題 1.2. 部分関数 $f\colon\mathbb N^k\rightharpoonup\mathbb N$ と決定性多テープ TM $N$ を考える。 $N$ の第1テープに入力 $1^{x_1}\#\cdots\#1^{x_k}$ を置き、残りのテープを空白として計算を始める。一つのテープを出力テープ、一つの状態を返却状態として指定し、次の二条件を仮定する。

$f(\vec x)=n$ ならば、 $N$ は有限時間後に返却状態へ入り、出力テープの位置 $0,\ldots,n-1$ に $1$ 、位置 $n$ に空白を置く。各テープのヘッド位置、出力テープの位置 $n+1$ 以後、および他のテープの内容は任意でよい。
$f(\vec x)\mathord\uparrow$ ならば、 $N$ は停止しない。

このとき、 $f$ を定義 1.1の正規出力配置で計算する単テープ決定性 TM $M$ を構成することができる。

証明.§E18.4 定理 2.2の構成を用いて、 $N$ の各テープを区切り記号で連結し、各ヘッド位置に印を付けた単テープ機械 $S$ を作る。ただし、 $N$ が返却状態へ入った場合には $S$ を直ちに停止させず、出力清掃局面へ移す。模倣の不変条件により、この時点の有限な整形式符号から出力テープに対応する区間と、その位置 $0$ を特定することができる。

清掃局面では、出力区間の位置 $0$ から最初の空白までを走査する。読み取った $1$ 一つにつき、整形式符号の最後の区切りより右側へ作業記号 $X$ を一つ追加する。仮定により作業記号はちょうど $n$ 個になる。次に、最後の区切りを左印へ書き換え、作業記号列の直後の位置へ右印を置く。 $f(\vec x)=0$ の場合には作業記号が一つも無いため、左印と右印は隣り合う二マスに付く。印を置いてから、左印より左側にある整形式符号を全て空白へ戻す。次に、左端位置から始まる出力前線と作業記号列の間を往復し、作業記号 $X$ を一つ消すたびに出力前線へ $1$ を一つ書いて前線を右へ移す。この反復は $n$ 回で終わり、 $n=0$ の場合には一度も実行されない。最後に両端の印と残った作業記号を消し、ヘッドを位置 $0$ へ戻して受理状態へ入る。各局面が走査する範囲と反復回数は有限なので、 $N$ が返却状態へ入った後の清掃は有限時間で終了する。終了時のテープは位置 $0,\ldots,n-1$ だけに $1$ をもち、それ以外の位置は空白である。

$f(\vec x)=n$ の場合には、 $N$ の有限な計算、その各一段に対する有限な模倣、および有限な清掃の後に、 $M$ は正規出力配置で停止する。 $f(\vec x)\mathord\uparrow$ の場合には $N$ が停止しないため、 $S$ は模倣局面にとどまり、清掃局面へ入らない。したがって $M$ も停止しない。ゆえに、この変換は定義域、発散、および出力値を保存する。▨

定義 1.1で採用した一進表記は、表記の選択の一つである。次の命題により、一進表記を二進表記へ置き換えても、部分 Turing 計算可能関数のクラスは変わらない。

命題 1.3.定義 1.1の一進表記を、各引数と出力の二進表記へ置き換えて同じ形の定義を行っても、部分 Turing 計算可能関数のクラスは変わらない。

証明. 一進表記の数と二進表記の数を相互に変換する二つの全域変換は、それぞれ決定性 TM で実行することができる。一進から二進への変換は、一進列から $1$ を一つ消すたびに別領域の二進カウンタへ $1$ を加える反復であり、二進から一進への変換は、二進カウンタから $1$ を引くたびに一進列へ $1$ を一つ追加する反復である。どちらの反復も、表されている数に等しい回数で終了する。区切り記号で連結された $k$ 個の引数には、この変換をブロックごとに適用する。

部分関数 $f$ が二進表記の規約で TM $M$ によって計算されるとする。多テープ機械 $N$ を、第1テープの一進入力を二進表記へ変換し、その結果を入力として $M$ を模倣し、 $M$ が受理停止した場合には出力の二進表記を一進列へ変換して出力テープへ書き、返却状態へ入るように構成する。前後の変換は全域であるため、 $N$ が返却状態へ入ることと $M$ が停止することは同値であり、返却時の出力テープは同じ値 $f(\vec x)$ の一進列である。補題 1.2を $N$ へ適用すれば、 $f$ を一進表記の規約の正規出力配置で計算する単テープ決定性 TM を得る。逆向きも、変換の向きを入れ替えた同じ合成で従う。したがって、二つの規約が定める部分 Turing 計算可能関数のクラスは一致する。▨

2 原始再帰関数

定義 2.1. 次の関数を初期関数 (initial function) という。

\begin{aligned} Z(x)&=0 &&\text{（零関数）},\\ S(x)&=x+1 &&\text{（後続者関数）},\\ P_i^k(x_1,\ldots,x_k)&=x_i\quad(1\le i\le k) &&\text{（射影関数）}. \end{aligned}

$m$ 変数関数 $f$ と $k$ 変数関数 $g_1,\ldots,g_m$ から

h(\vec x)=f(g_1(\vec x),\ldots,g_m(\vec x))

を作る操作を合成 (composition) という。

$k$ 変数関数 $f$ と $(k+2)$ 変数関数 $g$ から

\begin{aligned} h(\vec x,0)&=f(\vec x),\\ h(\vec x,n+1)&=g(\vec x,n,h(\vec x,n)) \end{aligned}

を満たす $(k+1)$ 変数関数 $h$ を作る操作を原始再帰 (primitive recursion) という。原始再帰では $k=0$ の場合も許す。このとき、基底の $f$ の代わりに一つの自然数 $c$ を指定し、 $h(0)=c$ かつ $h(n+1)=g(n,h(n))$ を満たす一変数関数 $h$ を作る。初期関数を含み、合成と原始再帰について閉じた最小の関数クラスを原始再帰関数 (primitive recursive function) のクラスという。

命題 2.2. 全ての原始再帰関数は全域関数である。

証明. 関数を生成する式の構造に関する帰納法を用いる。初期関数は表示された式によって全ての入力で値をもつ。全域関数 $f,g_1,\ldots,g_m$ の合成では、全ての値 $g_i(\vec x)$ が定まり、 $f(g_1(\vec x),\ldots,g_m(\vec x))$ の値も定まるので、合成結果も全域である。

全域関数 $f,g$ から原始再帰で $h$ を作る場合を考える。固定した $\vec x$ について、 $h(\vec x,0)=f(\vec x)$ は定義される（ $k=0$ の場合には、指定した自然数によって $h(0)=c$ が定義される）。 $h(\vec x,n)$ が定義されるならば、 $g(\vec x,n,h(\vec x,n))$ も定義されるので $h(\vec x,n+1)$ が定義される。 $n$ に関する帰納法により、全ての $n$ で $h(\vec x,n)$ が定義される。 $\vec x$ は任意なので $h$ は全域である。したがって、有限回の生成規則で得られる全ての原始再帰関数は全域である。▨

命題 2.3. 加法、乗法、切捨て減法 $x\mathbin{\dot-}y=\max\{x-y,0\}$ 、等号の特性関数、有限の場合分け、固定底 $b\ge2$ による冪 $b^n$ 、商 $\lfloor n/b\rfloor$ と剰余 $n\bmod b$ は原始再帰関数である。さらに、原始再帰関数の有界和と有界積、原始再帰的述語に対する有界量化と有界最小化、および有限組の符号化と成分取出しを原始再帰関数によって実行することができる。

証明. 加法と乗法は

\begin{aligned} \operatorname{add}(x,0)&=x,& \operatorname{add}(x,n+1)&=S(\operatorname{add}(x,n)),\\ \operatorname{mul}(x,0)&=0,& \operatorname{mul}(x,n+1)&=\operatorname{add}(\operatorname{mul}(x,n),x) \end{aligned}

という原始再帰で得られる。前者関数を $\operatorname{pred}(0)=0$ 、 $\operatorname{pred}(n+1)=n$ と定める。この式は、基底値 $c=0$ と $g=P_1^2$ による $k=0$ の原始再帰である。さらに、 $x\mathbin{\dot-}0=x$ 、 $x\mathbin{\dot-}(n+1)=\operatorname{pred}(x\mathbin{\dot-}n)$ と再帰すれば切捨て減法を得る。

$\operatorname{sg}(0)=0$ 、 $\operatorname{sg}(n+1)=1$ と定め、 $\operatorname{iszero}(n)=1\mathbin{\dot-}\operatorname{sg}(n)$ と置く。すると

\operatorname{eq}(x,y) =\operatorname{iszero}\bigl((x\mathbin{\dot-}y)+(y\mathbin{\dot-}x)\bigr)

は $x=y$ の場合に $1$ 、それ以外で $0$ となる。値が $0$ または $1$ の特性関数 $\chi$ に対する場合分けは

\operatorname{if}(\chi,u,v)=\chi u+(1\mathbin{\dot-}\chi)v

で実行することができる。固定底の冪は $p(0)=1$ 、 $p(n+1)=b\,p(n)$ という原始再帰で得られる。原始再帰関数 $a(\vec x,j)$ に対する有界和と有界積は

\begin{aligned} \operatorname{Sum}_a(\vec x,0)&=0,& \operatorname{Sum}_a(\vec x,t+1)&=\operatorname{Sum}_a(\vec x,t)+a(\vec x,t),\\ \operatorname{Prod}_a(\vec x,0)&=1,& \operatorname{Prod}_a(\vec x,t+1)&=\operatorname{Prod}_a(\vec x,t)a(\vec x,t) \end{aligned}

という原始再帰で得られる。

原始再帰的述語 $R(\vec x,y)$ の特性関数を $\chi_R$ とする。 $y\le t$ の範囲で $R(\vec x,y)$ が真となる最小の $y$ を返し、存在しない場合には $t+1$ を返す関数 $B_R(\vec x,t)$ を、 $t$ に関する原始再帰で構成する。 $t=0$ では $\chi_R(\vec x,0)=1$ なら $0$ 、そうでなければ $1$ とする。 $B_R(\vec x,t)\le t$ なら以前の値を保ち、 $B_R(\vec x,t)=t+1$ なら $\chi_R(\vec x,t+1)$ を調べ、真なら $t+1$ 、偽なら $t+2$ とする。この更新は上の比較と場合分けだけで記述する。したがって $B_R$ は原始再帰関数である。有界存在量化は $B_R(\vec x,t)\le t$ の特性関数であり、有界全称量化は反例に対する有界存在量化の否定である。

$b$ による商は、 $qb\le n$ を満たす最大の $q\le n$ を有界探索すれば得られ、剰余は $n\mathbin{\dot-}b\lfloor n/b\rfloor$ で得られる。最大値の探索も、候補を $0$ から $n$ まで走査して条件を満たすたびに保存値を更新する原始再帰である。

有限組には Cantor の対関数

\langle x,y\rangle=\frac{(x+y)(x+y+1)}2+y

を用いる。分子は常に偶数であり、固定数 $2$ による商は既に構成した関数で計算することができる。 $\langle x,y\rangle=z$ なら $x,y\le z$ なので、 $0\le x,y\le z$ の有限範囲を有界探索して二成分を復元することができる。この探索は有界量化と場合分けの有限な入れ子であり、原始再帰的である。対を入れ子にすれば、任意の固定長の組の符号化と各成分の取出しも原始再帰的になる。▨

命題 2.4. 全ての原始再帰関数は全域 Turing 計算可能である。

証明. 生成式の構造に関する帰納法によって、各原始再帰関数を計算する多テープ TM を構成する。零関数の機械は出力テープを空にして停止し、後続者関数の機械は入力の一進列へ $1$ を一つ追加する。射影関数の機械は区切り記号を数え、指定された入力成分を出力テープへ複写する。以上の初期関数用の機械は全入力で停止する。

$h(\vec x)=f(g_1(\vec x),\ldots,g_m(\vec x))$ について、帰納法の仮定から $f$ と各 $g_i$ の機械がある。入力 $\vec x$ を保存し、各 $g_i(\vec x)$ を順に計算して別の作業領域へ保存する。得られた $m$ 個の値を $f$ の機械へ渡して出力する。各部分機械が全入力で停止するため、合成機械も停止し、 $h(\vec x)$ を出力する。

原始再帰

h(\vec x,0)=f(\vec x),\qquad h(\vec x,n+1)=g(\vec x,n,h(\vec x,n))

については、最初に $f(\vec x)$ を計算して作業領域 $v$ へ保存する（ $k=0$ の場合には、基底値 $c$ の一進列を $v$ へ直接書き込む）。カウンタ $i$ を $0$ とし、 $i<n$ の間、 $g(\vec x,i,v)$ を計算して $v$ をその出力へ置き換え、 $i$ を一つ増やす。 $n$ 回の反復後に $v$ を出力する。 $i$ に関する帰納法により、反復開始時の $v$ は $h(\vec x,i)$ である。したがって終了時の出力は $h(\vec x,n)$ である。反復回数は有限であり、 $f,g$ の機械は全域なので、この機械も全入力で停止する。

以上で各生成規則に対応する多テープ機械を構成した。各機械の出力テープは、位置 $0$ から始まる一進列として関数値を保持する。補題 1.2によって、各機械を正規出力配置で停止する単テープ決定性 TM へ変換することができる。ゆえに全ての原始再帰関数は全域 Turing 計算可能である。▨

3 非有界最小化と部分ミュー再帰

定義 3.1. 部分関数 $g\colon\mathbb N^{k+1}\rightharpoonup\mathbb N$ に対し、

h(\vec x)=\mu y\,[g(\vec x,y)=0]

を次のように定める。 $h(\vec x)=y$ であるとは、

g(\vec x,y)=0 \quad\text{かつ}\quad \text{全ての }z<y\text{ について } g(\vec x,z)\mathord\downarrow\text{ かつ }g(\vec x,z)\ne0

が成り立つことをいう。そのような $y$ が存在しなければ $h(\vec x)$ は未定義である。この操作を非有界最小化 (unbounded minimization) という。

初期関数を含み、部分関数に対する合成、原始再帰、および非有界最小化について閉じた最小のクラスを部分ミュー再帰関数 (partial mu-recursive function) のクラスという。

最小の零点より前に未定義値がある場合にも最小化結果を未定義としたのは、 $y=0,1,2,\ldots$ を順番に計算する探索の動作と一致させるためである。

例 3.2. $g(x,y)=x+y+1$ は原始再帰関数であり、全ての $x,y\in\mathbb N$ について正である。したがって

h(x)=\mu y\,[x+y+1=0]

は全ての $x$ で未定義である。 $g(x,0),g(x,1),\ldots$ を順に計算する機械は、各値が正であることを確認して次の候補へ進み続け、停止しない。

4 Turing 機械の計算の算術化

固定した TM の一つの配置を一つの自然数で表し、一段遷移を原始再帰関数に変換する。一段遷移を表す原始再帰関数を時刻について原始再帰し、停止時刻だけを非有界最小化で探す。

補題 4.1. 固定した単テープ決定性 TM $M$ について、次の関数を原始再帰関数として構成することができる。

入力 $\vec x$ の初期配置の符号 $\operatorname{Init}_M(\vec x)$ 。
配置符号 $c$ の一段後の配置符号 $\operatorname{Step}_M(c)$ 。
$c$ が停止配置であるかを表す特性関数 $\operatorname{Halt}_M(c)$ 。
停止配置 $c$ の出力を読み取る関数 $\operatorname{Out}_M(c)$ 。

停止配置については $\operatorname{Step}_M(c)=c$ と定める。

証明. $M$ のテープ文字へ $0,\ldots,b-1$ の番号を付け、空白記号の番号を $0$ とする。配置を

(q,h,L,R)

で表す。 $q$ は状態番号、 $h$ はヘッド位置である。 $L$ の $b$ 進の最下位桁から順に、ヘッドの左隣、二つ左隣、という順序でテープ文字を記録する。 $R$ の最下位桁はヘッド位置の文字、その上位桁は右側の文字を順に記録する。末尾の空白は番号 $0$ なので省略することができる。四つ組は命題 2.3の対関数を入れ子にして一つの自然数へ符号化する。

入力は一進ブロック $1^{x_1}\#\cdots\#1^{x_k}$ である。各ブロックの開始位置は $x_1+\cdots+x_{i-1}+i-1$ という加法で表され、その位置へ対応するテープ記号を置いた $b$ 進整数 $R$ は、入力長を上界とする $b^j$ の有界和で表される。各位置の記号番号は、固定個数 $k$ のブロック境界との比較と場合分けによって原始再帰的に定まる。したがって、命題 2.3の有界和により $R$ は原始再帰関数である。初期状態番号、 $h=0$ 、 $L=0$ とこの $R$ を組にすることで $\operatorname{Init}_M$ を得る。

現在の走査記号は $a=R\bmod b$ である。 $M$ の遷移表は有限なので、各組 $(q,a)$ に対する $(q',a',D)$ は、等号の特性関数と有限の場合分けによって原始再帰的に選ぶことができる。 $R_0=\lfloor R/b\rfloor$ と置く。書込み後に右へ動く場合には

q_{\mathrm{new}}=q',\qquad h_{\mathrm{new}}=h+1,\qquad L_{\mathrm{new}}=a'+bL,\qquad R_{\mathrm{new}}=R_0

とする。左へ動き、 $h>0$ である場合には、 $\ell=L\bmod b$ を左隣の記号として

q_{\mathrm{new}}=q',\qquad h_{\mathrm{new}}=h-1,\qquad L_{\mathrm{new}}=\lfloor L/b\rfloor,\qquad R_{\mathrm{new}}=\ell+b(a'+bR_0)

とする。左端で左へ動く場合と、その場にとどまる場合には、 $h,L,R$ を定義どおりに更新する。表示した更新式は、加法、乗法、固定数による商と剰余、および有限の場合分けからなるので原始再帰的である。停止状態では入力四つ組をそのまま返す場合分けを加える。以上の場合分けで定めた関数が $\operatorname{Step}_M$ である。

$q$ が有限個の停止状態番号の一つと等しいかどうかは、等号の特性関数の有限和で判定することができる。この停止状態の特性関数が $\operatorname{Halt}_M$ である。

出力規約では、停止時のテープは位置 $0$ から $1$ が $n$ 個並び、その次が空白である。位置 $i$ のテープ文字は、 $i<h$ なら $L$ の第 $h-1-i$ 桁、 $i\ge h$ なら $R$ の第 $i-h$ 桁であり、固定底の冪、商、および剰余によって原始再帰的に取り出す。最初の空白位置は $h+R+1$ 以下にある。実際、 $i<h$ の位置はこの上界未満であり、 $i\ge h$ の非零桁数は $R+1$ 以下である。したがって、位置 $0$ から $h+R+1$ までの有界最小化によって最初の空白位置を求めることができる。正しい停止出力では、最初の空白位置が出力 $n$ である。この最初の空白位置を返す関数を $\operatorname{Out}_M(c)$ とする。不正な配置符号には値 $0$ を返す有限の場合分けを加えれば、四つの関数は全ての自然数上で全域な原始再帰関数になる。▨

次の同値は、「計算手続き」という未定義の直観からではなく、二つの形式体系の間の相互変換から従う。

定理 4.2. 部分関数 $f\colon\mathbb N^k\rightharpoonup\mathbb N$ について、次の二条件は同値である。

$f$ は部分ミュー再帰関数である。
$f$ は部分 Turing 計算可能である。

証明.(1) $\Rightarrow$ (2)を示す。全ての部分ミュー再帰関数について、生成式の構造に関する帰納法を用いる。以下の $f,g,h,k$ は定義 2.1と定義 3.1の記号であり、主張の $f,k$ とは別である。初期関数に対応する停止機械は命題 2.4の証明で構成した。

部分関数の合成 $h(\vec x)=f(g_1(\vec x),\ldots,g_m(\vec x))$ では、入力を保存し、 $g_1,\ldots,g_m$ の機械を順に実行する。いずれかが停止しなければ合成機械も同じ呼出しで停止しない。この停止しない動作は、合成が未定義である場合と一致する。全てが値を出力した場合には、値 $g_1(\vec x),\ldots,g_m(\vec x)$ を $f$ の機械へ渡す。 $f$ が停止すれば $f(g_1(\vec x),\ldots,g_m(\vec x))$ の値を出力し、停止しなければ合成機械も停止しない。したがって、定義域と値の両方が合成の定義に一致する。

部分関数 $f,g$ からの原始再帰では、入力 $(\vec x,n)$ を保存し、最初に $f(\vec x)$ を実行して値 $v$ を得る（ $k=0$ の場合には基底値 $c$ を $v$ とする）。停止しなければ全体も停止しない。次に $i=0,\ldots,n-1$ について $g(\vec x,i,v)$ を実行し、停止して得た値で $v$ を更新する。途中の呼出しが停止しなければ全体も停止しない。全ての $n$ 回が停止すれば最後の $v$ を出力する。 $i$ に関する帰納法により、 $i$ 回の更新後の $v$ は、再帰式によって定義される $h(\vec x,i)$ と一致する。したがって、構成した機械は $h(\vec x,n)$ が定義される場合に限って停止し、値 $h(\vec x,n)$ を出力する。

最後に $h(\vec x)=\mu y[g(\vec x,y)=0]$ を考える。機械は $y=0$ から開始し、 $g(\vec x,y)$ の機械を実行する。計算が停止して値 $0$ を出力したら $y$ を出力して停止し、正の値を出力したら $y$ を一つ増やして次の計算を始める。ある $g(\vec x,y)$ が未定義ならば機械はその呼出しで停止しない。したがって、この機械が $y$ を出力するための必要十分条件は、全ての $z<y$ で $g(\vec x,z)$ が定義されて正であり、 $g(\vec x,y)=0$ であることである。以上で構成した最小化機械の停止条件は、非有界最小化の定義と一致する。

各構成は有限個の作業テープをもつ中間機械として実行することができ、停止する場合には、出力テープの位置 $0$ から始まる一進列として値を返す。補題 1.2を適用すれば、定義域、発散、および出力を保ち、正規出力配置で停止する単テープ決定性 TM が得られる。ゆえに全ての部分ミュー再帰関数は部分 Turing 計算可能である。

(2) $\Rightarrow$ (1)を示す。部分関数 $f\colon\mathbb N^k\rightharpoonup\mathbb N$ を計算する TM $M$ を固定する。補題 4.1の関数を用い、

\begin{aligned} C_M(\vec x,0)&=\operatorname{Init}_M(\vec x),\\ C_M(\vec x,t+1)&=\operatorname{Step}_M(C_M(\vec x,t)) \end{aligned}

と定める。表示した再帰式は $t$ に関する原始再帰であるから $C_M$ は原始再帰関数である。 $t$ に関する帰納法により、 $C_M(\vec x,t)$ は $M$ の入力 $\vec x$ 上の $t$ 段後の配置を正確に符号化する。停止後には $\operatorname{Step}_M$ が配置を固定するため、この主張は停止時刻以後についても成り立つ。

次に

G_M(\vec x,t) =1\mathbin{\dot-}\operatorname{Halt}_M(C_M(\vec x,t))

と置く。 $G_M$ は原始再帰関数であり、 $M$ が時刻 $t$ までに停止している場合に限って値 $0$ をとる。したがって

\tau_M(\vec x)=\mu t\,[G_M(\vec x,t)=0]

は、 $M$ が $\vec x$ で停止する場合には最初の停止時刻を値とし、停止しない場合には未定義となる部分ミュー再帰関数である。

最後に

F_M(\vec x) =\operatorname{Out}_M\bigl(C_M(\vec x,\tau_M(\vec x))\bigr)

と定める。部分ミュー再帰関数は合成について閉じているため $F_M$ も部分ミュー再帰関数である。 $M$ が停止しない入力では $\tau_M$ が未定義なので $F_M$ も未定義である。 $M$ が停止する入力では、 $C_M(\vec x,\tau_M(\vec x))$ が最初の停止配置であり、 $\operatorname{Out}_M$ はその出力 $f(\vec x)$ を返す。したがって $F_M$ と $f$ は定義域と値が一致する。ゆえに $f$ は部分ミュー再帰関数である。

いずれの構成も、定義される入力では同じ値を返して停止し、定義されない入力では停止しない。したがって、部分関数として両クラスが一致する。▨

5 原始再帰関数の評価器と対角線論法

原始再帰関数は全域なので、命題 2.4によって全域 Turing 計算可能関数の部分クラスをなす。真の包含を示すため、全ての一変数原始再帰関数を列挙して対角線上で異なる全域関数を構成する。

補題 5.1. 一変数原始再帰関数の有限記述には有効な符号化 $e\in\mathbb N$ があり、次を満たす全域 Turing 計算可能関数 $E\colon\mathbb N^2\to\mathbb N$ が存在する。

$e$ が一変数原始再帰関数 $\varphi_e$ の正しい符号なら、 $E(e,x)=\varphi_e(x)$ である。
全ての一変数原始再帰関数 $\varphi$ に対し、 $\varphi=\varphi_e$ となる正しい符号 $e$ が存在する。
$e$ が正しい符号でなければ $E(e,x)=0$ である。

証明. 初期関数の記号を葉とし、合成と原始再帰の記号を、その引数となる有限個の関数記述を子にもつ節点とする有限構文木を考える。 $k=0$ の原始再帰の基底値は、数字列の葉として表す。各記号と括弧を有限アルファベットで表すことができるので、構文木は自然数へ符号化することができる。有限文字列の括弧対応、各節点の種類、子の個数、および入出力の項数は有限走査で検査することができる。したがって、正しい一変数関数記述であるかどうかを判定する TM が存在する。

評価器は正しい構文木を根から解釈する。零、後続者、射影の葉では定義式を直接実行する。合成節点では、各子の値を再帰的に評価してから外側の関数の子を評価する。原始再帰節点では、再帰引数が $n$ ならば基底関数を一回評価し（ $k=0$ の場合には基底値の葉を読み）、段階関数を $n$ 回評価する。構文木の高さに関する帰納法により、各子の評価は有限時間で終了する。原始再帰節点の反復回数 $n$ も有限なので、節点全体の評価も終了する。したがって、正しい符号と任意の入力 $x$ に対して評価器は停止し、記述された関数の値を返す。不正な符号では構文検査後に $0$ を返すようにすれば、評価器 $E$ は全入力で停止する。

原始再帰関数の定義は、初期関数から合成と原始再帰を有限回適用して得られる関数をちょうど集めたものである。したがって、各一変数原始再帰関数には、その有限な生成履歴を表す構文木があり、その符号 $e$ が存在する。以上で三条件が全て成り立つ。▨

定理 5.2. 原始再帰関数のクラスは、全域 Turing 計算可能関数のクラスの真部分クラスである。

証明.命題 2.4により、全ての原始再帰関数は全域 Turing 計算可能である。逆の包含が成り立たないことを示すため、補題 5.1の $E$ を用いて

d(n)=E(n,n)+1

と定める。 $E$ は全域 Turing 計算可能であり、後続者関数も全域 Turing 計算可能なので、 $d$ は全域 Turing 計算可能である。

$d$ が原始再帰関数であると仮定する。評価器の列挙性により、 $d=\varphi_e$ となる正しい符号 $e$ が存在する。 $n=e$ を代入すると、

d(e)=E(e,e)+1=\varphi_e(e)+1=d(e)+1

を得る。自然数は自分自身に $1$ を加えた数と等しくないので矛盾である。したがって $d$ は原始再帰関数ではない。原始再帰関数は全域 Turing 計算可能関数に含まれ、しかも $d$ は後者にだけ属するので、包含は真である。▨

6 同値定理と Church–Turing の提唱

注意 6.1 (定理と提唱の区別).定理 4.2は、二つの形式的に定義された関数クラスが一致することが証明された数学的定理である。この形式的同値定理に対して、人が有限の規則に従って「有効に計算することができる」という形式化以前の概念が Turing 計算可能性、したがって部分ミュー再帰性によって尽くされるという主張は Church–Turing の提唱である。「有効に計算することができる」という直観的概念は数学的定義の一方ではないため、この主張は同値定理だけから証明されない。

7 演習

問題 7.1.

$n$ 以下の素数の個数を $\pi(n)$ とする。一変数関数 $\pi$ が原始再帰関数であることを示せ。
$\operatorname{sg}(0)=0$ 、 $\operatorname{sg}(n+1)=1$ とし、 $q(x,y,z)=1\mathbin{\dot-}\operatorname{sg}(y)$ 、 $g(x,y)=\mu z\,[q(x,y,z)=0]$ とおく。 $g$ が部分ミュー再帰関数であり、 $g(x,0)\mathord\uparrow$ 、 $y\geq1$ について $g(x,y)=0$ であることを示せ。さらに、すべての $x$ について $\mu y\,[g(x,y)=0]$ が未定義であることを示せ。
全域関数 $f$ を計算する単テープ決定性 TM $M$ と原始再帰関数 $b$ があり、すべての入力 $\vec x$ について $M$ の停止時刻 $\tau_M(\vec x)$ が $b(\vec x)$ 以下であるとする。 $f$ が原始再帰関数であることを示せ。
$F\colon\N^2\to\N$ を任意の全域 Turing 計算可能関数とする。全域 Turing 計算可能な一変数関数 $h$ で、どの $e$ についても $h\neq F(e,\cdot)$ となるものを構成せよ。これにより、全域 Turing 計算可能な一変数関数の全体を一つの全域 Turing 計算可能関数 $F$ の切片 $F(e,\cdot)$ として列挙することはできないことを結論せよ。

解答 (演習の要点).

命題 2.3を用いる。整除関係 $d\mid p$ は $\exists q\leq p\,(qd=p)$ と同値であり、乗法、等号の特性関数、有界存在量化から原始再帰的である。素数であるという述語は
$\operatorname{Prime}(p)\iff 2\leq p\ \land\ \forall d\leq p\,\bigl(d\mid p\to(d=1\lor d=p)\bigr)$
と書くことができ、比較、論理結合、有界全称量化から原始再帰的である。その特性関数を $\chi_{\mathrm{P}}$ とすると、有界和の関数 $\operatorname{Sum}_{\chi_{\mathrm{P}}}$ は原始再帰的であり、 $\pi(n)=\operatorname{Sum}_{\chi_{\mathrm{P}}}(n+1)=\sum_{j=0}^{n}\chi_{\mathrm{P}}(j)$ は後続者関数との合成として原始再帰関数である。
$\operatorname{sg}$ は $k=0$ の原始再帰であり、 $q$ は切捨て減法、定数、射影との合成であるから原始再帰関数である。 $g$ はその非有界最小化であるから部分ミュー再帰関数である。 $y=0$ ならばすべての $z$ について $q(x,0,z)=1\mathbin{\dot-}0=1\neq0$ であるから、 $q(x,0,z)=0$ を満たす $z$ は存在せず $g(x,0)\mathord\uparrow$ である。 $y\geq1$ ならば $q(x,y,0)=1\mathbin{\dot-}1=0$ であるから $g(x,y)=0$ である。

$h(x)=\mu y\,[g(x,y)=0]$ が値 $y_0$ をもつと仮定する。 $g(x,y_0)=0$ であるから $y_0\geq1$ であり、定義 3.1により $z=0<y_0$ について $g(x,0)\mathord\downarrow$ でなければならないが、これは前段に反する。よって $h(x)$ は未定義である。 $g(x,1)=0$ であるにもかかわらず未定義となるのは、定義が最小の零点より前のすべての値の定義を要求するからである。
定理 4.2の証明の $C_M$ を用いる。 $t=\tau_M(\vec x)$ とすると $C_M(\vec x,t)$ は停止配置であり、補題 4.1の規約 $\operatorname{Step}_M(c)=c$ （ $c$ が停止配置）により、 $s\geq t$ についての帰納法で $C_M(\vec x,s)=C_M(\vec x,t)$ である。仮定 $t\leq b(\vec x)$ から $C_M(\vec x,b(\vec x))=C_M(\vec x,\tau_M(\vec x))$ であり、
$f(\vec x)=\operatorname{Out}_M\bigl(C_M(\vec x,b(\vec x))\bigr)$
が成り立つ。右辺は原始再帰関数 $\operatorname{Out}_M$ 、 $C_M$ 、 $b$ と射影の合成であるから、 $f$ は原始再帰関数である。この式では非有界最小化 $\tau_M$ を用いておらず、停止配置が自分自身へ移る規約によって、停止時刻を知らなくても上界の時刻で出力を読むことができる。
$h(n)=F(n,n)+1$ と定める。 $F$ を計算する TM を $M_F$ とし、多テープ機械 $N$ を次のように作る。 $N$ は第1テープの入力 $1^n$ を走査して第2テープへ $1^n\#1^n$ を書き出し、第2テープを入力テープとして $M_F$ を模倣する。 $M_F$ が正規出力配置 $1^{F(n,n)}$ で停止したら、その末尾の空白へ $1$ を一つ書いて出力を $1^{F(n,n)+1}$ とし、返却状態へ入る。 $F$ は全域であるから $N$ はすべての入力で返却状態へ入り、補題 1.2により $h$ を正規出力配置で計算する単テープ決定性 TM が得られる。よって $h$ は全域 Turing 計算可能である。 $h=F(e,\cdot)$ を満たす $e$ が存在すると仮定すると、 $h(e)=F(e,e)$ であるが、定義により $h(e)=F(e,e)+1$ であり矛盾する。よってどの $e$ についても $h\neq F(e,\cdot)$ である。 $h$ は全域 Turing 計算可能な一変数関数であるから、 $\{F(e,\cdot)\mid e\in\N\}$ はそれらの全体を尽くさない。定理 5.2の証明は、この議論を $F=E$ に適用し、原始再帰関数の列挙に $h$ が現れないことを用いたものである。

▨

§E18.7計算可能関数