実際の動作を見る
チューリングマシン図の例。
同じツールに4つの依頼。以下の図はすべて実際に生成されたものです。
入力する内容
単項インクリメントを行うチューリングマシンを描いてください。q0では1を読み、1を書き、右に移動します。空白Bでは1を書き、その場にとどまり、受理状態qaに入ります。
次に試す最後の単項1を消去するようにマシンを変更してください。入力記号0に対する拒否状態を追加してください。
状態遷移図 · OMG UML 2.5.1 §14 + Harel (1987) statechart · schematex-state
生成された図
チューリングマシン図とは。
チューリングマシン図は、無限に続くテープ上の記号を読み書きするマシンの状態遷移図です。遷移ラベルには通常、読み取り／書き込み／移動が記録されます。たとえば1/0,Lは、1を読み、0を書き、ヘッドを左に移動することを表します。
この図では、制御状態と、次の状態を選択するテープ操作を示します。受理および拒否の停止状態を設けることで、計算結果を明確に表せます。
- Standard
- OMG UML 2.5.1 §14 + Harel (1987) statechart
- Engine
- schematex-state
- Editable
- Double-click text, drag nodes
- Export
- SVG · PNG · PDF
利用者
チューリングマシン図を使う人。
遷移関数やテープ操作の読み方を練習するための、小規模な単項マシン。
有限オートマトンを超えて、a^n b^n などの言語を認識するアルゴリズム。
ある入力ブロックから別の入力ブロックへ移る仕組みを示す、2段階のテープ走査。
使い方
3ステップでチューリングマシン図を作成する方法。
01
説明する
まずは1段落で十分です。
“単項インクリメントを行うチューリングマシンを描いてください。q0では1を読み、1を書き、右に移動します。空白Bでは1を書き、その場にとどまり、受理状態qaに入ります。”
02
図を確認
最適なエンジンで描画します。
03
変更点を伝える
編集のたびにバージョンを保存します。
最後の単項1を消去するようにマシンを変更してください。
V2 · DRAWN FROM V1, NOTHING RETYPEDよくある質問
よくある質問
チューリングマシンの遷移ラベルには何が示されますか？
テープから読み取る記号、書き込む記号、ヘッドの移動方向を示します。たとえば1/B,Rは、1を読み、空白を書き、右に移動することを表します。
受理状態と拒否状態はどのように示しますか？
受理状態は停止する最終状態で、通常は二重丸で描きます。マシンが失敗時の停止を明示する必要がある場合は、別の拒否状態を設けられます。
チューリングマシンはどのように説明すればよいですか？
入力アルファベット、対象の言語やタスクを示し、各段階でマシンが何を読み、何を書き、どの方向に移動し、いつ停止するかを説明します。
L、R、Sは何を意味しますか？
テープヘッドの移動を表します。Lは左、Rは右、Sは現在のテープセルにとどまることを意味します。
チューリングマシン図でマーキングアルゴリズムを表せますか？
はい。マーカー記号を示し、どの入力記号を対応付けるか、または読み飛ばすかを説明します。状態遷移図には、走査、マーキング、戻り、確認の各段階を表せます。
関連ツール
