チューリング機械のシミュレータはいろいろ作られているが,ここではBYOBのリストを利用したシミュレータを作成する。
1. チューリング機械Mは,本体とテープ及びテープから記号を読んだり書いたりするヘッドからなっている.
2. テープは両側に無限に延びていて,ます目に区切られている.また各マス目にはあらかじめ定められた有限個の入力アルファベット記号を一つだけ書くことができる.
3. テープには最初有限の長さの記号列が書かれ,その両側には無限に空白記号が書かれている.
4. 本体は各瞬間に有限種類の状態のうちのいずれか1つの状態にある.
5. Mは各瞬間にヘッドの下にあるテープのます目に着目しており,ヘッドによってそこに書いてある記号を読みとって本体へ送る.Mは本体の現在の状態と送られてきたテープ記号に応じて,本体の状態を他に変えて(同じ状態のままでもよい)現在着目している記号を書き換える(書き込む記号はあらかじめ決められた有限個の記号の中から選ぶ.同じ記号で書き換えてもよい).次にヘッドを1ます分左に動かすか(Lで記す),右に動かす(Rで記す).
5で述べたような,現在の状態 sとテープ記号cに対し,次の瞬間に状態をt に変え,cをdに書き換え,ヘッドの移動(左,右)を行う規則をscdmt (ただし,mはRかL)と表現し,このチューリング機械の基本操作と呼ぶ.基本操作をどのように定めるかは,実行したい計算による.記号や状態の集合はいずれも有限であるから,これらの基本操作も高々有限個である.
本体の動作は初期状態と呼ばれる状態からヘッドをテープ上の指定されたます目において開始し,停止状態と呼ばれる状態になったとき停止する.停止状態は複数あってもよい.
次にチューリング機械の基本操作を読み込んで動く部分のスクリプトの作成である。
本体の1番目の文字が本体の状態を表すことになるが,可読性をよくするためブロックを作成して「本体の状態」で使えるようにする。ブロックの作成は変数カテゴリー内の最後尾にあるボタン「ブロックを作る」をクリックする。レポーター型を選び,「本体の状態」と名前を付ける。カテゴリはその他のままでよい。
なお,変数やリストのブロックで変数名やリスト名を変えるには▼の部分をクリックすると定義済みの変数やリストに変更できます。
ヘッドの位置は変数「テープ位置」に記憶するので,ヘッドが見ている文字は「テープのテープ位置番目」で表すことができる。これも見やすくするためにレポータ型のブロックで「ヘッドの見ている文字」を作る。(カテゴリーはリストにする。)
求める基本操作を見つけるために基本操作のリストを順番に探していくが,着目している基本操作は変数「基本操作位置」に記憶するので,着目している基本操作は「基本操作の基本操作位置番目」で表すことができる。これもわかりやすくするためレポータ型のブロックで「着目している基本操作」を作る。(カテゴリーはリストにする。)
次の準備5と本体のスクリプトの作成のときに同じブロックを何度も組み立てるのであらかじめよく使うブロックを作成しておいてそれを複製するようにすると便利である。
本体の状態と見ているテープ記号に一致するかどうか(今着目している基本操作の1番目の文字が本体の状態と一致しかつ2番目の文字がヘッドが見ているテープの記号と一致するかどうか)判定する述語をブロックエディタで作る。最初に右のようにブロックを組み立てる。
スクリプトは本体の状態と現在見ているテープ記号にマッチする基本操作を探し,見つけたらその基本操作の定義に従って動作するようにする。また,本体の状態が停止状態(ここではhを停止状態としている)になったらスクリプトをストップする。
最初にテープの位置と基本操作の位置を1にし本体の状態を初期状態にする。
本体の状態が停止状態(ここではh)になるまでスクリプトは繰り返される。探している基本操作が現れるまで基本操作を探す。探している基本操作が見つかれば以下のことを行う。
探している基本操作なので,その後に書かれている情報を読んでテープの書換,ヘッドの移動,状態の遷移を行う。テープ位置の文字を基本操作で指定される文字に書換し,テープのカーソル位置をヘッドの移動に応じて1増減し,最後に本体の状態を書き換えて基本操作の位置を先頭に戻す。
なお,テープ位置が右端や先頭にある場合には,それぞれヘッドを右や左に動かす場合そこには空白文字があると考えるので,空白記号のbを挿入する。
BYOBではリストは縦にのびるのでテープ上の記号の遷移を確認しやすいとはいえない。テキストを表示するブロックを使うとテープ表示が見やすくなる。具体的には,リストをテキスト化するブロックとテキストを言うブロックを組み合わせる。
次の基本操作は与えられた数を3で割ったときの余りを求めるものである。ただし,ここでは自然数nを表すために1をn+1個並べた文字列をとることにする。
s1bRu
u11Rv
v11Rw
w11Ru
ubbLx
x1bLx
xb1Rh
vbbLy
y1bLy
yb1Rz
zb1Rh
wbbLp
p1bLp
pb1Rq
qb1Rr
rb1Rh
実行例はテープに7(1が8個)を書き込んでいる。
リストの要素はテキストファイルから読み込むことができるので,上記の基本操作をファイルに書いておいて読み込んでも良い。