千葉大学理学研究科基盤理学専攻数学・情報数理学コース 2016年8月実施専門 B10

标签：

Author

祭音Myyura (co-authored with GPT 6 Astra)

$\mathbb N=\{0,1,2,\ldots\}$ とし、Ackermann 関数を

A(0,y)=y+1,\quad A(x+1,0)=A(x,1),\quad A(x+1,y+1)=A(x,A(x+1,y))

で定める。

(1) $\sigma(x,y,z)=1$ （ $A(x,y)=z$ のとき）、それ以外で $0$ と定めると、 $\sigma$ は原始帰納的であることを示せ。次は証明なしに用いてよい。

A(x,y)>x+y,\qquad A(x,y)<A(x,y+1),\qquad A(x,y)<A(x+1,y).

(2) $p:\mathbb N^2\to\mathbb N$ は原始帰納的全単射で、原始帰納的な逆座標関数 $p_1,p_2$ を持つとする。

B(A(x,y))=p(x',y')\Longrightarrow A(x,y)=A(x',y')

を満たす原始帰納的 $B:\mathbb N\to\mathbb N$ が存在することを示せ。

Ackermann 函数定义见上式。

(1) 证明其图的示性函数 $\sigma(x,y,z)=\mathbf1_{\{A(x,y)=z\}}$ 是原始递归函数。可直接使用 $A(x,y)>x+y$ 以及对两个自变量的严格单调性。

(2) 给定具有原始递归逆坐标函数的原始递归配对双射 $p$ ，证明存在原始递归函数 $B$ ，使 $B(A(x,y))=p(x',y')$ 时必有 $A(x,y)=A(x',y')$ 。

$z=0$ では $\sigma=0$ 。 $z\ge1$ を固定し、 $0\le i,j\le z$ の有限表 $T_z(i,j)$ を次の順で計算する。値 $z+1$ は「 $z$ より大きい」を表す。

\begin{aligned} T_z(0,j)&=\min(j+1,z+1),\\ T_z(i+1,0)&=T_z(i,1),\\ T_z(i+1,j+1)&= \begin{cases} T_z(i,T_z(i+1,j))&T_z(i+1,j)\le z,\\ z+1&T_z(i+1,j)=z+1. \end{cases} \end{aligned}

各行を左から右へ、行を上から下へ計算する。帰納法により

T_z(i,j)=\min(A(i,j),z+1).

実際、内側の値が $z$ 以下なら元の再帰式と一致する。内側の値が $z$ より大きい場合は $A(i,u)>u$ により結果も $z$ より大きく、打ち切り値 $z+1$ が正しい。

この表は高々 $(z+1)^2$ 個の要素からなり、各要素は $z+1$ 以下である。表を基数 $z+2$ の整数で符号化すれば、表の参照・更新は商と剰余で行え、全体は原始帰納的な回数で有界な反復計算になる。従って $T_z$ の計算は原始帰納的である。

$x>z$ または $y>z$ なら $A(x,y)>z$ なので、

\sigma(x,y,z)= \begin{cases} 1&z\ge1,\ x,y\le z,\ T_z(x,y)=z,\\ 0&\text{それ以外} \end{cases}

も原始帰納的である。

$A(0,y)=y+1$ を使い、

B(z)=p(0,z\mathbin{\dot{-}}1),\qquad z\mathbin{\dot{-}}1=\max(z-1,0)

と定めればよい。打ち切り減算と $p$ は原始帰納的なので $B$ もそうである。

$z=A(x,y)\ge1$ とする。 $B(z)=p(x',y')$ なら $p$ の単射性から $x'=0,y'=z-1$ 。従って $A(x',y')=A(0,z-1)=z=A(x,y)$ 。