Copyright 2002 守屋悦朗 オートマトンって？ （Turing machine） （アニメーションで実行のこと）

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

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 @ ♭ ♭ … 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右

途中省略

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

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

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

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

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

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

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

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

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

　　２ 　　３ 　６ ♭ ♭ ♭ ♭ # # # @ @ @ … 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@

途中省略

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

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

　　２ 　　３ ２×３ ♭ ♭ ♭ ♭ ♭ 1 1 1 1 1 1 … 受理

終わり 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　戻る