チューリングマシン
最近よく話題にあがるけど2%くらいしかわかってなかったので学んでみることにしたmiminashi.icon
順を追って動作を書いてくれているのでわかりやすかった
チューリングマシンの構成要素
テープ
左右に無限の方向に伸びている
マスで区切られている
1マスに付き1文字書き込める
書き込める文字の集合をテープアルファベットと呼ぶ
ヘッド
テープのあるマスの上に置かれている
下のマスに印字されている文字を読み取れる
下のマスに印字することができる
現在の状態
状態集合に含まれる状態の内，1つを記憶する
状態集合には，初期状態，終了状態の特別な状態が属している
テーブル
(現在の状態，ヘッドが読み取った文字) $ \longrightarrow (次の状態，印字する文字，移動先(静止も可)) というふうな対応