1. 練習用のチューリングマシンを作る

オートマトンシミュレータを使ってチューリングマシンを作ることもできます． オートマトンシミュレータの起動法，基本的な操作法はオートマトンシミュレータによる計算モデルの理解を参照してください．

チューリングマシン作成の開始

オートマトンシミュレータでチューリングマシンを作成するには，「File」メニューの「New」-> 「Turing Machine」を選択します．

すると，「Are you sure you want to clear everything for a new project?」と聞いてくるので(何も作っていなくても)，そこで「はい(Y)」を選ぶと，空の画面が現れます．

My First Turing Machineの入力

まずは，教科書の図6.6に掲載されている問題L₅「文字aとbからなる文字列xに現れるaの個数がbよりも多い時に真，そうでない時に偽」を解くチューリングマシン「My First Turing Machine」を作ってみます．

チューリングマシンの編集もオートマトンの編集とほぼ同じです．ただ，状態遷移の矢印につくラベルは，オートマトンでは入力文字だけだったのですが，チューリングマシンでは以下の3種類の組み合わせからなるラベルになります．

• 入力文字 (Input Symbols) : 空白は「blank」を選びます．
• 出力文字 (Output Symbol) : 変更がない場合はno change を選びます．
• 移動方向 (Head Movement) : 左(Left)に進むか右(Right)に進むかを決めます．

教科書図6.6に対応するチューリングマシンは以下のようになります．

テープへの入力

チューリングマシンへの入力が終わったら，テープへの入力を行います(オートマトンシミュレータと違って，実行開始前にテープに書き込んでおく必要があります)．既に書き込まれている時は，ボタンを押して，テープをクリアします．

実行開始時の注目点が緑の逆三角で表現されているので，入力文字列の左端がそこに来るようにして，文字列を入力していきます．"abaabba" という文字列を入力し終わった状態が，以下の図になります．

実行

文字列 "abaabba" はaが4回，bが3回使われているので，正しいチューリングマシンが作られていたら，問題L₅「文字aとbからなる文字列で，現れるaの個数がbよりも多い」が真になるはずです．実行して確かめてみましょう．

実行の制御はメニュー上のボタンでおこないます．

• : 実行開始
• : 一時停止
• : 1ステップ進む
• : 1ステップ戻る
• : 入力をクリアする．

実行開始のボタン()を押すと実行を開始します．テープを書き換えながら実行していく様子がわかると思います．そのうちに，終了して以下のようになります．

これでは，終了状態(受理状態)で停止したのか非終了状態(不受理状態)で停止したのか分かりませんね．ここで，1ステップ戻るボタン()を押すと以下のように，以下のように受理状態で停止したことがわかります．

次に"abbaba"という入力を与えてみます． 文字列 "abbaba" はaが3回，bが3回使われていて，問題L₅「文字aとbからなる文字列で，現れるaの個数がbよりも多い」は偽になるはずです．実行して確かめてみましょう．

実行終了後に， 1ステップ戻るボタン()を押すと以下のように，以下のように不受理状態で停止したことがわかります．

(注) チューリングマシンに関しては，シミュレータの中でテストする機能はありません．

ファイルへの保存

作成したチューリングマシンは「デスクトップ」に保存してください．「My first Turing machine」のファイル名は「t0.txt」とします．