KreeneのT述語
定義
あるTuringマシン$ \mathcal{M}の現在の状態$ s_{\mathcal{M},i}を符号化することが出来る 次の$ f_{\mathcal{M}}(x,y)を考える
$ f_{\mathcal{M}}(x,y) = 0であるとき，
あるチューリングマシン$ \mathcal{M}に入力$ xを与えたとき，
「$ \mathcal{M}が辿る状態$ s_{\mathcal{M},1},\dots,s_{\mathcal{M},n}の有限列を符号化したもの」が$ yと等しい．
$ f_\mathcal{M}(x,y)=1なのはそうでないときである
ところで，入力アルファベットなどを固定すれば，TMは状態遷移関数によって区別することが出来ると言えよう．
TMの状態遷移関数$ \deltaを符号化したものを$ e，インデクスと呼ぶ．
$ eをインデクスに持つTMを$ \mathcal{M_e}とする．
$ eをインデクスに持つTM$ \mathcal{M_e}においての$ f_{\mathcal{M}_e}(x,y)を考える
すなわち，$ T(e,x,y) = f_{\mathcal{M}_e}(x,y)とする．
$ T(e,x,y) = 0であるとき，
$ eをインデクスとしたTM$ \mathcal{M}が入力$ xに対してのステップの符号化が$ yに等しい
$ T(e,x,y)=1であるときはそうでないときである．
性質
ステップはは有限列なので$ yが存在するなら停止するということを意味する
すなわち
$ eをインデクスとしたTM$ \mathcal{M}が入力$ xに対して停止する
$ \iff$ \exists y.(T(e,x,y)=0)