Tape
記憶はテープに並ぶ
1 マスずつ読むだけでも、状態と規則を組み合わせればかなり複雑な計算を表せます。ここでは空白を _ で表します。
Computation / Tape / Head / State Transition
計算は、
テープを一歩ずつ書き換える。
チューリングマシンは、無限に長いテープ、1 マスを読むヘッド、内部状態、そして 遷移規則だけで計算を表すモデルです。
このページでは、サンプル機械を切り替えながら、1 ステップ実行と自動実行で、どの規則が適用されて何が書き換わったかを追えます。
- テープ、ヘッド位置、現在状態、適用規則を同時に見られる
- 「1 の列の末尾に 1 を追加」と「0/1 を反転」のサンプルをすぐ試せる
- 規則を書き換えて、自分で別の機械を作って動かせる
Transition
次の動きは「状態」と「読んだ記号」で決まる
たとえば q0 1 1 R q0 なら、状態 q0 で 1 を読んだとき、1 を書いて右へ進み、状態は変えません。
まず見るべきこと
ヘッドがどこを読んで、どの規則を選び、その結果どの記号に書き換えたかだけを追うと、停止までの流れがかなり明瞭に見えます。
Core Idea
少数の規則でも、状態とテープがあるだけで、計算の手続きをかなり一般的に表せる。
この教材では、実機の計算機を再現する代わりに、チューリングマシンの核である「読む・書く・動く・状態を変える」をそのまま観察できるようにしています。
Viewer
チューリングマシンを動かす
サンプルを読み込んでから 1 ステップずつ進めるか、自動実行で停止まで流してください。規則を書き換えると、その場で別の機械も試せます。
代表的な規則と入力テープをすぐ読み込めます。
空白は _ として扱います。スペースを入れた場合も内部では空白記号へ変換します。
300 ms
速度を上げると計算の流れを確認しやすく、下げると規則の追跡がしやすくなります。
サンプルの狙い
見どころ
Machine State
テープと状態遷移
待機中
q0
準備完了
ステップ数
0
ヘッド位置
0
読んだ記号
_
出力テープ
111
現在適用される規則がここに表示されます。
Rules
遷移規則を編集する
形式: 現在状態 読む記号 書く記号 移動 次状態
移動は R が右、L が左、N がその場です。HALT 状態へ入るか、適用規則がないと停止します。
規則を読み込みました。
Rule Table
現在の遷移一覧
次に使う規則と、直前に使った規則を色で示します。
Reading
このモデルの読み方
チューリングマシンの本質は、強い部品の多さではなく、少ない操作を何度でも繰り返せることにあります。
Tape
テープは記憶装置
このページでは見えている範囲だけを描いていますが、理論上のテープは左右に無限です。空白も計算に参加します。
Head
ヘッドは 1 マスしか見ない
それでも、状態を切り替えながら 1 マスずつ進めば、探索、反転、末尾追加、繰り上がりのような手続きが記述できます。
Transition
規則表はプログラム本体
どの状態でどの記号を読んだかに対して、何を書くか・どちらへ動くか・次の状態は何かを決めた表が、そのまま計算手順になります。
Halting
停止の仕方も重要
HALT に入る場合と、規則不足で止まる場合では意味が違います。意図した停止か、表の抜けかを見分けてください。
Reading Tip
「答え」よりも、「どの規則が何回選ばれたか」を追うと、計算モデルとしての面白さが見えやすい
末尾に 1 を追加する機械は「右へ進み続けて空白を見つけたら書く」だけですし、反転機械は「0 を見たら 1、1 を見たら 0」を繰り返すだけです。複雑さは規則の組み合わせから立ち上がります。