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

Presentation on theme: "オートマトンって？ （Turing machine）."— Presentation transcript:

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

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

3 a4 a a3 a2 a1 … q 動作前

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

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

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

7 … a1 a2 a a3 a4 　… q

8 … a1 a2 b a3 a4 　… p

9 掛け算をやってみよう

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

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

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

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

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 @ ♭ ♭ … q左 ＃を見つけたら、その右の１を＃に書き換える

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 @ @ @ @ … q左

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

109 終わり 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　戻る