チューリングマシンの定義

チューリングマシンの定義を試みます。
以後、TMと略します。

TMは、物理的には次のものから成ります。
①有限個の文字が用意されていて、テープへの読み書きに使われる
②有限個の遷移状態が用意されている
③現在の遷移状態を保持する領域を持つ
④前後に無限に伸びるテープ領域を持つ
⑤テープへの読み書き位置を保持する領域を持つ
⑥有限サイズの状態遷移関数を保持する領域を持つ

とても注意しなければならないことがあって、
テープへの読み書き位置を保持する領域は実は無限のサイズの領域が必要だったりします。
もしその領域が有限なサイズならば、それが無限に伸びるテープへの読み書き位置の限界になるからです。

用意される文字の数は1個以上とします。もし1個の場合は、TMの処理がどんだけ進もうがテープが常に1文字一色になるだけのことと開き直ります。
文字には空白文字という特別な文字が必ずあるとします。
用意される遷移状態は2個以上とします。
遷移状態には、始まりの状態と終わりの状態という特別な状態があります。それらは別々の遷移状態に割り当てられるものとします。
TMの使われ方によっては終わりの状態は、受領状態と拒否状態の2種類が必要になることもあるようです。

文字の集合をCh、空白文字をSpとします。
遷移状態の集合をSt、始まりの状態をBgn、終わりの状態をEndとします。
Zを整数全体とし、
ZからChへの写像でテープ上の文字配列を表わします。
Map(Z,Ch)でZからChへの写像全体を表わします。
テープ上の文字配列に上限と下限があって、下限より下と上限より上で空白文字が続くような場合、有界な文字配列ということにします。

遷移状態、テープの読み書き位置、テープの文字配列の組が、TMの物理状態です。
St×Z×Map(Z,Ch)
がTMの物理状態の全体となります。
たいていの場合、TMの初期の物理状態は、ρを0を下限とする有界な文字配列として、
TM-init(ρ):=(Bgn,0,ρ)∈St×Z×Map(Z,Ch)
になります。

TMには決定性と非決定性の2種類あり、最初に決定性の方を考えます。
決定性TMでは状態遷移関数は次のような写像σになります。
σ∈Map(St×Ch,St×Ch×Mov)
ただし、Mov:={1,-1}
Movはテープの読み書き位置を前後に1スライドさせることに使うことを意図しています。

状態遷移関数σを一つ定めます。
σ∈Map(St×Ch,St×Ch×Mov)
TMの物理状態が(s,i,ρ)∈St×Z×Map(Z,Ch)のとき、
ρ(i)によりテープから文字を読み取り、
現在の遷移状態sから、次のようにして次の遷移状態s'、書き込み文字c'、テープの読み書き位置の移動m'をもとめます。
((s,ρ(i)),(s',c',m'))∈σ

(s,i,ρ)∈St×Z×Map(Z,Ch)は現在のTMの物理状態で、
状態遷移関数は((s,ρ(i)),(s',c',m'))∈σで、
(s,i,ρ)の次の物理状態は、(s',i',ρ')∈St×Z×Map(Z,Ch)とします。
s'は状態遷移関数からすでに得られていて、残りは次のように得られます。
i' := i + m'
ρ' := ((ρ ＼ {(i,ρ(i))}) ∪ {(i,c')})
文字配列ρは次のような集合と考えます。
ρ = { (j,ρ(j)) | j∈Z }
(A＼B) := { z | z∈A ∧ ￢(z∈B) }は差集合演算です。

(s,i,ρ)から(s',i',ρ')への移行がTMの1ステップ実行となります。
s'が終了の状態ならば、TMはそれを検知して終了します。
まとめると、
TM-exec := { (σ,step) | σ∈Map(St×Ch,St×Ch×Mov) ∧ step∈MapClass
∧ step={ ((s,i,ρ),(s',i',ρ')) | (s,i,ρ),(s',i',ρ')∈St×Z×Map(Z,Ch)
∧ ∃c'∃m'((s',c',m')=σ(s,ρ(i)) ∧ i'=i+m' ∧ ρ'=ρ＼{(i,ρ(i))}∪{(i,c')}) }
}
※stepの定義域がSt×Z×Map(Z,Ch)になるとは限らないことに注意
TMのステップ実行はすべて一つのσの影響下にあって、
TM-exec(σ)(s,i,ρ)=(s',i',ρ')
となります。
TMの初期の物理状態TM-init(ρ)からTM-exec(σ)をn回繰り返して、終わりの状態に達したらTMは終了です。
TM-exec(σ)^n(TM-init(ρ))=(End,*,*)
もちろん、永遠に終わりの状態に達しないこともあり得ます。

fは写像とするとき、f^n(x)=yはfをn回繰り返す写像の合成を表わします。
f^1(x)=f(x)
f^2(x)=f(f(x))
f^3(x)=f(f(f(x)))

TMのテープの初期文字配列ρの文字分布の広がりがm文字の規模で、TMの終了へのステップ回数がnの規模で、1より大きいある自然数kがあって、
nはm^kに比例するならば、σはP問題を解く状態遷移関数、
nはk^mに比例するならば、σはNP問題の可能性のある問題を解く状態遷移関数、
となる。

Pow(A):={x|x⊂A}はべき集合演算子です。

非決定性TM(NTM)では、状態遷移関数σは次のような写像になります。
σ∈Map(St×Ch,Pow(St×Ch×Mov))
遷移先への候補が複数あるようなTMとなります。
St、Ch、Movはどれも有限なので、Pow(St×Ch×Mov)も有限であることに注意願います。

NTMではその物理状態はSt×Z×Map(Z,Ch)の部分集合になります。
Pow(St×Z×Map(Z,Ch))＼{∅}
はNTMの物理状態全体となります。
最初は一つの物理状態から始まりますが、状態遷移先の候補が複数あれば、
その分だけコピーされたTMにそれぞれの状態遷移の候補を適用させていくことになります。
こうしてNTMの1ステップ実行ごとに状態遷移の候補ごとに並列稼働するTMが増えていくことになります。

NTM-exec := { (σ,step) | σ∈Map(St×Ch,Pow(St×Ch×Mov)) ∧ step∈MapClass
∧ step={ (G,H) | G,H∈Pow(St×Z×Map(Z,Ch))
∧ H={ (s',i',ρ') | (s',i',ρ')∈St×Z×Map(Z,Ch)
∧ ∃s∃i∃ρ∃c'∃m'((s,i,ρ)∈G ∧ (s',c',m')∈σ(s,ρ(i)) ∧ i'=i+m' ∧ ρ'=ρ＼{(i,ρ(i))}∪{(i,c')}) } }
}
※もちろんstepの定義域がPow(St×Z×Map(Z,Ch))になるとは限りません。

NTM-exec(σ)(G)=Hのとき、だいたい次のような感じで並列稼働するTMが増えていきます。
Hの個数 = { (x,y) | x∈G ∧ y∈σ(x) )}の個数

(End,*,*)∈NTM-exec(σ)^n({TM-init(ρ)})
並列稼働するTMの中で終わりの状態に達したものがあれば、全TMは終了ということになります。

並列稼働するTMを直列になるように実行するとたいていの場合、n～k^mのクラスの計算量になると思われます。

P.vs.NP問題とは、多項式時間で終わりにたどり着けるNTMの状態遷移関数を多項式時間で終了するTMの状態遷移関数に作り変えることができるか、というもののことだと考えます。

TM-exec(σ)^n(TM-init(ρ))=(End,*,ρ')
これは、TMの状態遷移関数σによって定められる関数で、TMの実行回数nにおける、テープの初期文字配列ρからρ'への関数のように見えます。
TMのアルゴリズム全体を状態遷移関数ごとの文字配列間の関数と考えることにすると、
TM-algorithms := { (σ,func) | σ∈Map(St×Ch,St×Ch×Mov) ∧ func∈MapClass ∧ func={ (ρ,ρ') | ρ,ρ'∈Map(Z,Ch) ∧ ∃n∃i(n∈Nat ∧ i∈Z ∧ TM-exec(σ)^n(TM-init(ρ))=(End,i,ρ'))} }
※Natは自然数全体を表わします。
※もちろんfuncの定義域はMap(Z,Ch)になるとは限りません。

TMの完全性は
どんなプログラミング言語で記述された関数もTMで実装出来ることのようです。

TMの万能性は
TMをTMでシミュレートできることのようです。

プログラミング言語の完全性は
TMで記述されるどんな関数も実装出来ることです。
TM-algorithmsに一対一対応する関数のクラスを持つということです。
それはTMをシミュレート出来ることと同等だということです。
もちろんTMはすべてのプログラミング言語をシミュレート出来るということになっています。
完全性を持つものは互いにシミュレート出来ます。
これにより他の言語を介して自分自身もシミュレート出来ます。
つまり、完全性をもつものは万能性をもつということになります。

しかし、万能性をもつものは完全性をもつとは限らないようです。