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

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

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

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

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

4 つまり、 次のように動く

5 … a1 a2 a a3 a4 　… q

6 … a1 a2 b a3 a4 　… p

7 掛け算をやってみよう

8 　　２ 　　３ ♭ 1 1 ♭ 1 1 1 ♭ ♭ ♭ … q0

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

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

11 　　２ 　　３ ♭ ＊ 1 ♭ 1 1 1 ♭ ♭ ♭ … q1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

59 途中省略

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

80 　　２ 　　３ ＠が5個 ♭ ♭ ♭ ♭ ♭ ♭ ♭ 1 @ @ …

81 　　２ 　　３ ＠が4個 ♭ ♭ ♭ ♭ ♭ ♭ ♭ 1 1 @ …

82 　　２ 　　３ ＠が3個 ♭ ♭ ♭ ♭ ♭ ♭ ♭ 1 1 1 …

83 途中省略

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

85 1が6個 　　２ 　　３ ♭ ♭ ♭ ♭ ♭ 1 1 1 1 1 1 …

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

87 終わり 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　戻る