Turingマシンの停止性問題
チューリングマシンについて
$ \deltaに適当に一意な自然数（Gödel数）$ eを割り振り，これを（チューリングマシンの）インデクスと呼ぶことにする 動作中のチューリングマシン$ \mathcal{M}において
次の3組は高々有限である
現在の状態$ s
ヘッドの位置$ h
テープの文字列$ t
ので，$ \braket{s,h,t}に適当な自然数を割り振ることが可能，これをチューリングマシンの1ステップと呼ぶことにする
更に，チューリングマシン$ \mathcal{M}の有限のステップの列，つまり
$ \braket{s,h,t}_1,\braket{s,h,t}_2,\dots,\braket{s,h,t}_n
にもやっぱり適当な自然数を割り振ることが可能．
今，$ \mathcal{M}に依存して定まる関数$ f_\mathcal{M}(x,y)を以下のように定義する．
$ f_\mathcal{M}(x,y) = 0$ \iff
チューリングマシン$ \mathcal{M}に入力$ xを与えると，ある状態で停止するとする．
停止するまでに通った一連のステップ列のGödel数が，$ yに等しい．
$ f_{\mathcal{M}}(x,y) = 1$ \iffそうではないとき．
ここで更に，$ \mathcal{M}を変数として組み込み直した関数$ Tを考える．KreeneのT述語と呼ばれる 自然数$ eをインデクスとして解釈した際に一意に定まるチューリングマシンを$ \mathcal{M}_eとして，
$ T(e,x,y) = f_{\mathcal{M_e}}(x,y)
この$ Tを使って，
$ eで定まるチューリングマシン$ \mathcal{M}が入力$ xに対して停止する．$ \iff$ \exists y, T(e,x,y)=0
停止性判定関数
停止性判定関数$ halt(e,x)を
$ halt(e,x) = 0$ \iff$ \exists y, T(e,x,y)=0
$ halt(e,x)=1$ \iff$ \lnot\exists y, T(e,x,y)=0
直感的には，$ \mathcal{M}_eが入力$ xに対して停止するなら0を，そうでないなら1を返す関数である
$ halt(e,x)は計算可能ではない．
端折っているが，$ fが計算可能ならそれを再現するチューリングマシンを構成出来る，という命題を用いる
背理法で示す．
1. $ haltは計算可能であるとする．
2. $ haltを使って次の$ \mathcal{M_0}を構成することが出来る
入力$ xに対し，
$ halt(x,x) = 0なら停止しない．
$ halt(x,x)=1なら停止する．
3. $ \mathcal{M}_0のインデクスを$ e_oとする
4. 今，$ halt(e_0,e_0)=0とする
停止性判定関数の定義より，$ halt(e_0,e_0) = 0$ \iff$ \mathcal{M_0}が入力$ e_0に対して停止する
ところが，$ halt(e_0,e_0)=0であるので$ \mathcal{M}_0の定義より$ \mathcal{M}_0は停止しない．
矛盾が発生する．
5. 他方，$ halt(e_0,e_0)=1とする
停止性判定関数の定義より，$ halt(e_0,e_0) = 1$ \iff$ \mathcal{M_0}が入力$ e_0に対して停止しない
ところが，$ halt(e_0,e_0)=1であるので$ \mathcal{M}_0の定義より$ \mathcal{M}_0は停止する．
矛盾が発生する．
6. したがって$ haltは計算可能ではない．