計算言語３（チューリングマシン）
このページはマス旅の一部です。
前回スタック付きのオートマトン（PDA)をやりました。
今回はチューリングマシンをやろう。
PDAのスタックの代わりに無限に長いテープを使うのがチューリングマシンだ。
スタックではStackStrというスタック自体と、最上位topSを用意した。読み取れるのは
いつもtopSだけなので、PushとPopという２つの動作と使ったね。
では、チューリングマシンの場合はどうだろうか。
長い固定テープをマス目に区切り、ヘッドがマス目を1マスずつ前進後退の動きをすることでデータの読み書きができる。ヘッダ付近以外では左右に無限に続くデータ空白があるとする。
Γにはテープの読み書き用の文字[0,1,+,x,"Λ"]が入る。
遷移関数は(Q,Γ)⇒(Q,Γ,{L,R})
スタックに比べるとテープとヘッドの使い方は単純ですね。
＜テープとヘッドの使い方＞
両側に無限の空白があるとするのではなく、右だけ無限の空白があるとしても
チューリングマシンは実現できる。
入力文字列があると右の端に空白("Λ")とくっつけます。
スタートは左はしの1文字目です。いきなり読み込みを開始します。
ヘッドの動きは{L,R}がありますが、原則はRと思って大丈夫。
Σ={0,1,+,x}について、N,M.P∊[0,1],C,D∊[+,x]とラベルを貼って、実験してみよう。
1演算記号式"NMC"の計算は
①Nを読んで、ヘッドはRへ。
②Mを読んで、ヘッドはRへ。
➂Cを読んで、NとMとCの情報を状態遷移をうまく使って2*2*2=8通りの経路に
対して、答えが出るように仕組んでおきます。その答えA∊[0,1]でCを上書きして
ヘッドはRへ。
④Cの右は""なのでヘッドはLへ。
⑤L方向に戻った状態でAを読むとそれが答えで、ヘッドは停止します。
2演算記号式"NMCPD"の計算はどうなるだろうか。
"NMC"まで済んでいるとしたら、
NMCの次
④Cの右がPなので、Pを読んでヘッドはRへ。
⑤は➂と同様にDを読んで、Dを（A,P,D）の組み合わせから答えBに書き換えて
ヘッドはRへ。
⑥は④と同様、Dの右は""なのでヘッドはLへ。
⑦はL方向に戻った状態でAを読むとそれが答えで、ヘッドは停止します。
ヘッドが停止の反対はヘッドが動き続ける。
エラーがあると２つの状態をヘッドが行き来する。
つまり、停止できるループからエラーループにワープすると永遠に止まらない。
＜推移関数を作る＞
状態Q＝{q1,q2,q3,q4,q5,q6,q7,q8,q9}
状態の意味づけは次の通り、この通りコード化する必要はない。
q1="",q2="0",q3="1",q4="00",q5="01|10",q6="11",q7="stop",
q8="err",q9="err"
δ関数は、
2要素⇒2要素のしくみになる。
ヘッドの動く方向dir={R,L},書き換え文字rewrite={0,1,_}
（現在状態、入力記号）＝>(次の状態、rewrite、dir）
エラーにならない対応表を作ってみよう。
状態q1は書き換えなしにRへ移動。行先は入力記号が0ならq2,1ならq3。
状態q2は書き換えなしにRへ移動。行先は入力記号が0ならq4(00),1ならq5(01)。
ただし、入力記号が""なら書き換えなしでLで戻り、状態をq7へ。
状態q3は書き換えなしにRへ移動。行先は入力記号が0ならq5(10),1ならq6(11)。
ただし、入力記号が""なら書き換えなしでLで戻る、状態をq7へ。
状態q4(00)は入力記号が+なら0+0=0だから、「0」に書き換えてRへ移動,状態はq2へ。
状態q4(00)は入力記号がxなら0x0=0だから、「0」に書き換えてRへ移動,状態はq2へ。
状態q5(01|10)は入力記号が+なら0+1=1だから、「1」に書き換えてRへ移動,状態はq3へ。
状態q5(01|10)は入力記号がxなら0x1=0だから、「0」に書き換えてRへ移動,状態はq2へ。
状態q6(11)は入力記号が+なら1+1=0(mod 2)だから、「0」に書き換えてRへ移動,状態はq3へ。
状態q6(11)は入力記号がxなら1x1=1だから、「1」に書き換えてRへ移動,状態はq3へ。
状態q7(stop)は入力記号を答えとして表示して、停止。
これらの状態でこれ以外の入力があると、エラーループに飛ぶ。
状態q8(err)は入力記号が何でも書き換えなしでLへ移動。
状態q9(err)は入力記号が何でも書き換えなしでRへ移動。
課題：以上の以上のM＝（Q,Σ、Γ、δ、q1,F)で、F={q7}すると、"01+1x"はチューリングマシンが停止することを確かめよう。
＜手動デバッグ＞
ヘッド位置:[現在状態、現在記号列s] 更新（現在状態、入力記号）＝>(次の状態、rewrite、dir）
参考に読み取り履歴をつけました。
1:[q1,"0 1 + 1 xΛ"] 更新 (q1,0)=>(q2,_,R) 読み取り履歴0
2:[q2,"0 1 + 1 xΛ"] 更新 (q2,1)=>(q5,_,R) 読み取り履歴01
3:[q5,"0 1 + 1 xΛ"] 更新 (q5,+)=>(q3,1,R) 読み取り履歴01+
4:[q3,"0 1 1 1 xΛ"] 更新 (q3,1)=>(q6,_,R) 読み取り履歴01+1
5:[q6,"0 1 1 1 xΛ"] 更新 (q6,x)=>(q3,1,R) 読み取り履歴01+1x
6:[q3,"0 1 1 1 1Λ"] 更新 (q3,Λ)=>(q7,_,L) 読み取り履歴01+1x""
5:[q7,"0 1 1 1 1Λ"] 更新 (q7,1)=>停止、答え1。 読み取り履歴01+1x""1
予想通り、スタックを使わずに連続演算ができましたね。
＜geogebraでコード化＞
「作成」ボタン
#必要な変数を用意します。クリック時のスクリプトに貼り付けてください。
pos = 1
nextPos = 1
InputStr = "01+1x"
Len = Length(InputStr)
Input = InputStr+"Λ"
q1 = "q1"
q2 = "q2"
q3 = "q3"
q4 = "q4"
q5 = "q5"
q6 = "q6"
q7 = "q7"
q8 = "err"
q9 = "err"
curQ = q1
nextState = q1
charIn = ""
di = 1
dir = "R"
tapeStr = Input
overwrite = "_"
result = "result"
Process = pos + ":＜q1, " + tapeStr + "＞ ==> q1,＿.R"
「リセット」ボタン
SetValue(pos, 1)
SetValue(nextPos, 1)
SetValue(curQ, "q1")
SetValue(nextState, "q1")
SetValue(charIn, "")
SetValue(di, 1)
SetValue(dir, "R")
SetValue(tapeStr, Input)
SetValue(overwrite, "_")
SetValue(result, "")
Process = pos + ":＜q1, " + tapeStr + "＞ ==> q1,＿.R"
「更新」ボタン
#geogebraのif文はswitch文のようにかいてもよい。（マニュアルから）
#L,Rの代わりに最後に行先のposを更新する。
SetValue(curQ, nextState)
SetValue(pos, nextPos)
SetValue(charIn, Element(tapeStr, pos))
di = If(curQ == "q1", 1, curQ == "q2", 2, curQ == "q3", 3, curQ == "q4", 4, curQ == "q5", 5,curQ == "q6", 6,curQ == "q7", 7,curQ == "q8", 8,curQ == "q9", 9)
calcNext = If(di == 1,If(charIn == "0","q2",charIn == "1", "q3", "q8"), di == 2,If(charIn == "0","q4",charIn == "1", "q5",charIn=="Λ","q7","q8"), di == 3,If(charIn == "0" ,"q5",charIn=="1","q6",charIn=="Λ","q7","q8"),di==4,If((charIn == "+" || charIn=="x"),"q2","q8"),di==5,If(charIn == "+","q3",charIn=="x","q2","q8"),di==6,If((charIn == "+" || charIn=="x"),"q3","q8"),di==7,"stop",di==8,"q9",di==9,"q8")
SetValue(overwrite,If(di==4,"0",di==5,If(charIn == "+","1",charIn=="x","0"),di==6,If(charIn == "+","0", charIn=="x","1"),"_"))
SetValue(nextState, calcNext)
SetValue(nextPos,If((curQ == "q2"||curQ == "q3") && charIn=="Λ", pos-1, pos+1))
SetValue(dir,If(nextPos > pos,"R","L"))
SetValue(tapeStr,If(overwrite=="_",tapeStr,Take(tapeStr,1,pos-1) + overwrite +Take(tapeStr,pos+1,Length(tapeStr))) )
SetValue(Process, pos + ":[" + curQ + ", " + tapeStr + "] 更新==> " + nextState +","+ overwrite+","+ dir + ")" )
SetValue(result, If(curQ == "q7", "受理 (ANSWER = " + charIn + ")", result))
タイトルは「チューリングマシンのテープのようすを確かめよう」