目次 | 次: 2. チューリングマシン作成練習

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

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

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

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

すると，「Are you sure you want to clear everything for a new project?」と聞いてくるので（何も作っていなくても），「OK」を選ぶとチューリングマシン作成用の画面が現れます．

My First Turing Machineの作成

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

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

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

テープへの入力

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

実行開始時のテープ読込の位置が緑の逆三角で示されていますから，入力文字列の左端が一致するようにクリックしてから，文字列を入力していきます．文字を入力する枠は内部が黒く表示されます．

「abaabba」という文字列を入力すると，以下のようになります．

チューリングマシンの実行

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

実行の制御はウィンドウ左上のボタンで行います．

実行のボタンを押すと実行を開始します．テープを書き換えながら実行していく様子が確認できます．動作を1ステップずつ確認したい場合には，ボタンとボタンを利用すると良いでしょう．

実行が終了すると，以下のように終了状態（受理状態）で停止しています．

別の入力に対する実行

次にボタンを押してテープをクリアしたうえで，「abbaba」という入力を与えてみます．文字列「abbaba」は「a」が3回，「b」が3回使われていて，問題L5「文字aとbからなる文字列で，現れるaの個数がbよりも多い」は偽になるはずです．実行して確かめてみましょう．

実行が終了すると，以下のように非終了状態（不受理状態）で停止しています．

検証用自動テストの実行

チューリングマシンについても検証用の自動テストが用意されています．「Test」メニュをクリックすると，チューリグマシンの一覧が表示されますから「My First Turing Machine」を選択して，「Test」ボタンを押しましょう．用意された入力についてチューリングマシンが自動的にテストされます．すべてのテストにパスすると，次のように表示されます．

目次 | 次: 2. チューリングマシン作成練習