チューリング機械の遷移・テープ追跡

決定性単一テープの状態・読取・書込・ヘッド移動と停止理由を有限範囲で追跡する。

決定性1テープの有限範囲シミュレーションです。10000ステップ・4096セル・処理量の上限到達は、非停止の証明ではありません。

項目を入力・選択してから「計算する」を押してください。

必要な入力・選択は5項目です。

空白以外の1文字を指定します。例:_。未使用セルはこの記号です。

最大200文字。空欄なら空テープ。空白・改行は使えません。先頭がセル0、左右には空欄セルが続きます。

例:q0。状態名は英字で始めます。

セル0が初期テープの先頭。負の位置も指定できます。

この状態に入った時点で受理します。

受理状態とは異なる名前にします。

遷移規則(状態・読取 → 書込・移動・次状態)任意
行状態読取書込移動次状態操作
1
2

5列を左端の欄へタブ区切りで貼り付けられます。200行まで。

状態+読取記号の組は一意。移動はL=左、R=右、S=動かない。空の行は無視します。最大200行。

最大100ステップを表で表示します。実行自体は終了条件まで進みます。


計算結果

値を入力して計算してください。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

δ(現在状態, ヘッド位置の読取記号) = (次状態, 書込記号, 移動L/R/S)を1回ずつ適用します。書込後にヘッドを移動します。受理・拒否状態への到達は即時停止、規則のない(状態, 読取)組は未定義遷移として停止します。表示範囲は初期テープ位置とヘッドの既訪問区間を含み、4096セル超へ広がる遷移は書換前に打ち切ります。

停止理由、到達ステップ、最終状態・ヘッド・テープ、直前に変更したセル、各ステップの実行追跡(範囲指定)。

計算例(架空の数値)

例:空欄記号_、初期テープ11、初期状態q0、ヘッド0、受理qhalt、拒否qreject。規則(q0,1)→(0,R,qhalt)なら1step後のテープは[0..1] 01で受理します。

適用対象と限界

有限の遷移規則で記述できる決定性・単一テープの抽象機械。多テープ・非決定性・任意プログラム実行、停止性の一般判定、10000ステップ超/4096セル超の実行証明、全ステップの一括ダウンロードは対象外。。

採用した方式

  • 決定性1テープの逐次シミュレーション(v1.0):対象範囲 両側へ伸びる単一テープ・部分遷移・1文字1セル、L/R/S移動、最大10000遷移・表示最大100行/回/適用地域 global

方法と出典

方法:E1349 deterministic single-tape trace v1.0 (2026-11-14)。データ記録日:2026-11-14。