オートマトンって？ （Turing machine）

♭ a2 an a1 … q0 読み書きヘッド 空白記号♭は、 普通は書かない 入力文字列

a4 a a3 a2 a1 … q 動作前

a4 a a3 a2 a1 … q 動作前 δ(q, a) = (p, b, L)

a4 a a3 a2 a1 … q 動作前 δ(q, a) = (p, b, L) a4 b a3 a2 a1 … 　… p 動作後

つまり、 次のように動く

… a1 a2 a a3 a4 　… q

… a1 a2 b a3 a4 　… p

掛け算をやってみよう

　　２ 　　３ ♭ 1 1 ♭ 1 1 1 ♭ ♭ ♭ … q0 スタート

　　２ 　　３ ♭ ＊ 1 ♭ 1 1 1 ♭ ♭ ♭ … q♭ ♭が出現するまで右へ移動

　　２ 　　３ ♭ ＊ 1 ♭ 1 1 1 ♭ ♭ ♭ … q♭

　　２ 　　３ ♭ ＊ 1 ♭ 1 1 1 ♭ ♭ ♭ … q1 １を＃に書き換える

　　２ 　　３ ♭ ＊ 1 ♭ # 1 1 ♭ ♭ ♭ … q右 ♭が出現するまで右へ移動

　　２ 　　３ ♭ ＊ 1 ♭ # 1 1 ♭ ♭ ♭ … q右 ♭が出現するまで右へ移動

　　２ 　　３ ♭ ＊ 1 ♭ # 1 1 ♭ ♭ ♭ … q右 ♭を見つけたら＠に書き換える

　　２ 　　３ ♭ ＊ 1 ♭ # 1 1 @ ♭ ♭ … q左 ＃が出現するまで左に移動

　　２ 　　３ ♭ ＊ 1 ♭ # 1 1 @ ♭ ♭ … q左 ＃が出現するまで左に移動

　　２ 　　３ ♭ ＊ 1 ♭ # 1 1 @ ♭ ♭ … q左 ＃を見つけたら、その右の１を＃に書き換える

　　２ 　　３ ♭ ＊ 1 ♭ # 1 1 @ ♭ ♭ … q1 １を＃に書き換える

　　２ 　　３ ♭ ＊ 1 ♭ # # 1 @ ♭ ♭ … q右 ♭が出現するまで右に移動

　　２ 　　３ ♭ ＊ 1 ♭ # # 1 @ ♭ ♭ … q右 ♭が出現するまで右に移動

　　２ 　　３ ♭ ＊ 1 ♭ # # 1 @ ♭ ♭ … q右 ♭を見つけたら＠に書き換える

　　２ 　　３ ♭ ＊ 1 ♭ # # 1 @ @ ♭ … q左 ＃が出現するまで左に移動

　　２ 　　３ ♭ ＊ 1 ♭ # # 1 @ @ ♭ … q左 ＃が出現するまで左に移動

　　２ 　　３ ♭ ＊ 1 ♭ # # 1 @ @ ♭ … q左 ＃を見つけたら、その右の１を＃に書き換える

　　２ 　　３ ♭ ＊ 1 ♭ # # 1 @ @ ♭ … q1 ＃を見つけたら、その右の１を＃に書き換える

　　２ 　　３ ♭ ＊ 1 ♭ # # # @ @ ♭ … q右 ♭が出現するまで右に移動

　　２ 　　３ ♭ ＊ 1 ♭ # # # @ @ ♭ … q右 ♭が出現するまで右に移動

　　２ 　　３ ♭ ＊ 1 ♭ # # # @ @ ♭ … q右

　　２ 　　３ ♭ ＊ 1 ♭ # # # @ @ @ … q左

　　２ 　　３ ♭ ＊ 1 ♭ # # # @ @ @ … q左

　　２ 　　３ ♭ ＊ 1 ♭ # # # @ @ @ … q左

　　２ 　　３ ♭ ＊ 1 ♭ # # # @ @ @ … q左

　　２ 　　３ ♭ ＊ 1 ♭ # # # @ @ @ … q1

　　２ 　　３ ♭ ＊ 1 ♭ # # # @ @ @ … q終

　　２ 　　３ ♭ ＊ 1 ♭ # # 1 @ @ @ … q終

　　２ 　　３ ♭ ＊ 1 ♭ # 1 1 @ @ @ … q終

　　２ 　　３ ♭ ＊ 1 ♭ 1 1 1 @ @ @ … q終

　　２ 　　３ ♭ ＊ 1 ♭ 1 1 1 @ @ @ … q終

　　２ 　　３ ♭ ＊ 1 ♭ 1 1 1 @ @ @ … q終

　　２ 　　３ ♭ ＊ 1 ♭ 1 1 1 @ @ @ … q0

　　２ 　　３ ♭ ＊ ＊ ♭ 1 1 1 @ @ @ … q♭

　　２ 　　３ ♭ ＊ ＊ ♭ 1 1 1 @ @ @ … q1

　　２ 　　３ ♭ ＊ ＊ ♭ # 1 1 @ @ @ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # 1 1 @ @ @ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # 1 1 @ @ @ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # 1 1 @ @ @ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # 1 1 @ @ @ ♭ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # 1 1 @ @ @ ♭ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # 1 1 @ @ @ @ … q左

　　２ 　　３ ♭ ＊ ＊ ♭ # 1 1 @ @ @ @ … q左

　　２ 　　３ ♭ ＊ ＊ ♭ # 1 1 @ @ @ @ … q左

　　２ 　　３ ♭ ＊ ＊ ♭ # 1 1 @ @ @ @ … q左

　　２ 　　３ ♭ ＊ ＊ ♭ # 1 1 @ @ @ @ … q左

　　２ 　　３ ♭ ＊ ＊ ♭ # 1 1 @ @ @ @ … q1

　　２ 　　３ ♭ ＊ ＊ ♭ # # 1 @ @ @ @ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # # 1 @ @ @ @ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # # 1 @ @ @ @ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # # 1 @ @ @ @ ♭ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # # 1 @ @ @ @ ♭ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # # 1 @ @ @ @ ♭ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # # 1 @ @ @ @ @ … q左

　　２ 　　３ ♭ ＊ ＊ ♭ # # 1 @ @ @ @ @ … q左

　　２ 　　３ ♭ ＊ ＊ ♭ # # 1 @ @ @ @ @ … q左

　　２ 　　３ ♭ ＊ ＊ ♭ # # 1 @ @ @ @ @ … q左

　　２ 　　３ ♭ ＊ ＊ ♭ # # 1 @ @ @ @ @ … q左

　　２ 　　３ ♭ ＊ ＊ ♭ # # 1 @ @ @ @ @ … q左

　　２ 　　３ ♭ ＊ ＊ ♭ # # 1 @ @ @ @ @ … q1

　　２ 　　３ ♭ ＊ ＊ ♭ # # # @ @ @ @ @ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # # # @ @ @ @ @ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # # # @ @ @ @ @ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # # # @ @ @ @ @ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # # # @ @ @ @ @ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # # # @ @ @ @ @ ♭ … q右

　　２ 　　３ ♭ ＊ ＊ ♭ # # # @ @ @ @ @ ＠ … q左

　　２ 　　３ ♭ ＊ ＊ ♭ # # # @ @ @ @ @ ＠ … q左

　　２ 　　３ ♭ ＊ ＊ ♭ # # # @ @ @ @ @ ＠ … q左

　　２ 　　３ ♭ ＊ ＊ ♭ # # # @ @ @ @ @ ＠ … q左

　　２ 　　３ ♭ ＊ ＊ ♭ # # # @ @ @ @ @ ＠ … q左

　　２ 　　３ ＠が６個 ♭ ＊ ＊ ♭ # # # @ @ @ … q左

　　２ 　　３ ＠が６個 ♭ ＊ ＊ ♭ # # # @ @ @ … q左

　　２ 　　３ ＠が６個 ♭ ＊ ＊ ♭ # # # @ @ @ … q1

　　２ 　　３ ＠が６個 ♭ ＊ ＊ ♭ # # # @ @ @ … q終

　　２ 　　３ ＠が６個 ♭ ＊ ＊ ♭ # # # @ @ @ … q終

　　２ 　　３ ＠が６個 ♭ ＊ ＊ ♭ # # # @ @ @ … q終

　　２ 　　３ ＠が６個 ♭ ＊ ＊ ♭ # # # @ @ @ … q終

　　２ 　　３ ＠が６個 ♭ ＊ ＊ ♭ # # # @ @ @ … q終

　　２ 　　３ ＠が６個 ♭ ＊ ＊ ♭ # # # @ @ @ … q1

　　２ 　　３ 　６ ♭ ＊ ＊ ♭ # # # @ @ @ … q2

　　２ 　　３ ＠が６個 ♭ ＊ ＊ ♭ # # # @ @ @ … q0

　　２ 　　３ ＠が６個 ♭ ＊ ＊ ♭ # # # @ @ @ … q1

　　２ 　　３ ＠が６個 ♭ ＊ ♭ ♭ # # # @ @ @ … q1

　　２ 　　３ ＠が６個 ♭ ♭ ♭ ♭ # # # @ @ @ … q1

　　２ 　　３ ＠が６個 ♭ ♭ ♭ ♭ # # # @ @ @ … q2

　　２ 　　３ ＠が６個 ♭ ♭ ♭ ♭ # # # @ @ @ … q2

　　２ 　　３ ＠が６個 ♭ ♭ ♭ ♭ # # # @ @ @ … q2

　　２ 　　３ ＠が6個 ♭ ♭ ♭ ♭ ♭ # # @ @ @ … q3

　　２ 　　３ ＠が6個 ♭ ♭ ♭ ♭ ♭ ♭ # @ @ @ … q3

　　２ 　　３ ＠が6個 ♭ ♭ ♭ ♭ ♭ ♭ ♭ @ @ @ … q3

　　２ 　　３ ＠が5個 ♭ ♭ ♭ ♭ ♭ ♭ ♭ 1 @ @ @ q@

　　２ 　　３ ＠が4個 ♭ ♭ ♭ ♭ ♭ ♭ ♭ 1 1 @ @ q@

　　２ 　　３ ＠が3個 ♭ ♭ ♭ ♭ ♭ ♭ ♭ 1 1 1 @ @ … q@

　　２ 　　３ ＠が2個 ♭ ♭ ♭ ♭ ♭ ♭ ♭ 1 1 1 1 @ q@ …

　　２ 　　３ ＠1個 ♭ ♭ ♭ ♭ ♭ ♭ ♭ 1 1 1 1 1 @ q@ …

1が5個 　　２ 　　３ ♭ ♭ ♭ ♭ ♭ ♭ 1 1 1 1 1 @ … q@

1が6個 　　２ 　　３ ♭ ♭ ♭ ♭ ♭ ♭ 1 1 1 1 1 1 ♭ … q@

1が6個 　　２ 　　３ ♭ ♭ ♭ ♭ ♭ ♭ 1 1 1 1 1 1 ♭ … 受理

終わり 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　戻る