avatar

HelloRusk

reading and coding ...

Blogprofile

停止性問題は決定不能

7/18/2020, 8:50:30 AM - 186 days ago

復習。

日本語で書くと

帰納関数のコードと引数に対して計算が止まるかどうかを判定する帰納述語は存在しない

である.

まず, 万能帰納関数というのが存在する. 万能帰納関数 comp\mathtt{comp} とは, 以下を満たすような関数である.
任意の自然数 mm および帰納関数 f:Nm→Nf : \mathbb{N}^m \to \mathbb{N} に対して, ある自然数 pfp_f が存在し,

λ(x0,...,xm−1).comp(pf,⟨x0,...,xm−1⟩)≐f\lambda(x_0, ..., x_{m-1}). \mathtt{comp}(p_f, \langle x_0, ..., x_{m-1} \rangle) \doteq f

ただし, ⟨x0,...,xm−1⟩\langle x_0, ..., x_{m-1} \rangle は (x0,...,xm−1)(x_0, ..., x_{m-1}) のゲーデル数で, この数列と一対一対応するような自然数である.
pfp_f は帰納関数 ff のコードと呼ばれる. comp\mathtt{comp} はいわばインタプリタのようなもので, ff に対応するようなコード pfp_f を このインタプリタに与えれば, ff が実行されるということである.

次に, 帰納関数のコードと引数に対して計算が止まるかどうかを判定する帰納述語 halt∈N2\mathtt{halt} \in \mathbb{N}^2 を考える.
すなわち

halt(p,x)  is  true≡comp(p,x)  is  defined\mathtt{halt}(p, x) \ \ is \ \ true \equiv \mathtt{comp}(p, x) \ \ is \ \ defined

と定義する.
あるプログラムがある入力に対して停止するかどうかというのは, そのプログラムに対応するコード pp と入力 xx を万能帰納関数 comp\texttt{comp} が受け取った時 undefinedundefined になるかならないかという話だから, halt\mathtt{halt} が真であるか否かという話になる. halt\mathtt{halt} が帰納述語であれば 真か偽か一意に定まり, 決定可能であることになる.
実際にはこのような帰納述語は存在せず, 停止性問題は決定不能であることを示す.

はじめに

comp+(p,x)={comp(p,x)if  comp(p,x)  is  defined0if  comp(p,x)  is  undefined\texttt{comp}^{+}(p, x) = \begin{cases} \texttt{comp}(p, x) & if \ \ \texttt{comp}(p, x) \ \ is \ \ defined \\ 0 & if \ \ \texttt{comp}(p, x) \ \ is \ \ undefined \end{cases}

を考える. これは万能帰納関数が全関数（任意の入力に対し undefinedundefined にならない関数）になるよう修正を加えたものになる.
comp+\texttt{comp}^{+} が帰納関数である（必ず停止し, 値が一意に定まる）と仮定しよう. ここで, diag:N→N\texttt{diag}: \mathbb{N} \to \mathbb{N} を

diag(x)=comp+(x,⟨x⟩)+1   ⋯(i)\texttt{diag}(x) = \texttt{comp}^{+}(x, \langle x \rangle) + 1 \ \ \ \cdots (\mathrm{i})

と定義する. comp+\texttt{comp}^{+} が全関数かつ帰納関数であることから, diag\texttt{diag} も全関数かつ帰納関数である.
ここで, diag\texttt{diag} に対応するコードを p0p_0 とおく. 万能帰納関数 comp\texttt{comp} の定義より,

comp(p0,⟨x⟩)≐diag(x)\texttt{comp}(p_0, \langle x \rangle) \doteq \texttt{diag} (x)

さらに diag\texttt{diag} が全関数であることから

comp+(p0,⟨x⟩)=diag(x)   ⋯(ii)\texttt{comp}^{+}(p_0, \langle x \rangle) = \texttt{diag} (x) \ \ \ \cdots (\mathrm{ii})

(i),(ii)(\mathrm{i}), (\mathrm{ii}) より

comp+(p0,⟨p0⟩)=diag(p0)=comp+(p0,⟨p0⟩)+1\texttt{comp}^{+}(p_0, \langle p_0 \rangle) = \texttt{diag} (p_0) = \texttt{comp}^{+}(p_0, \langle p_0 \rangle) + 1

となり, 矛盾が導けた. したがって, 背理法により comp+\mathtt{comp}^{+} は帰納関数ではない.

この事実から, 帰納述語 halt\mathtt{halt} が存在しないことも示せる. 仮に存在するとした場合,

comp+(p,x)={comp(p,x)if  halt(p,x)  is  true0if  halt(p,x)  is  false\texttt{comp}^{+}(p, x) = \begin{cases} \texttt{comp}(p, x) & if \ \ \texttt{halt}(p, x) \ \ is \ \ true \\ 0 & if \ \ \texttt{halt}(p, x) \ \ is \ \ false \end{cases}

で, 「帰納関数から帰納述語による場合分けで定義される関数も帰納関数である」という性質から comp+\texttt{comp}^{+} が帰納関数であることが言えてしまうが, これはまさに先ほど示した内容と矛盾する. よって示された.