Upgrade to PRO for Only $50/Year—Limited-Time Offer! 🔥

Lets learn Turing Machine

payanotty
May 12, 2022
590

Lets learn Turing Machine

2022/05/12に開催したオンラインセミナーの資料です。

https://studyco.connpass.com/event/245540/

payanotty

May 12, 2022
Tweet

Transcript

  1. 自己紹介
 • 名前
 ◦ 早野 康太
 • お仕事
 ◦ 自然言語モデルの改善


    • 趣味
 ◦ 猫、犬
 ◦ ゲーム
 ▪ ELDEN RING
 ▪ 遊戯王MD
 ▪ ウマ娘
 ◦ アニメ
 ▪ パリピ孔明
 ▪ まちカド2期

  2. 今日のお話
 • 今日は計算モデルの話を中心にします
 ◦ 計算モデル
 ▪ 計算機の動作を抽象化した数理モデル
 ◦ チューリングマシン
 ▪

    コンピュータで実行できる計算をすべて実行可能なモデル
 ◦ 簡単な計算モデルから始めて
 チューリングマシンの原理をざっくり理解することを目指します
 ▪ 有限オートマトン
 ▪ プッシュダウンオートマトン
 ▪ チューリングマシン
 

  3. アジェンダ
 • 「計算する」 の定義
 • 簡単な計算モデルについて
 ◦ 有限オートマトン
 ◦ プッシュダウンオートマトン


    • チューリングマシンについて
 ◦ 定義
 ◦ 万能チューリングマシン
 ◦ 停止問題から見る機械的計算の限界

  4. 計算:ある規則に基づいて機械的に実行される手続き ・ 計算を行うのにひつようなもの 1. 計算の経過のとりうる状態 2. 記号 3. 計算規則 4.

    計算の初期状態 (開始状態) 5. 計算の終了状態 (受理状態) → 有限オートマトン プッシュダウンオートマトン (線形拘束オートマトン) チューリングマシン 計算モデル 計算理論は, 形式的な計算モデルを通して 「計算すること」の本質を解き明かす
  5. 有限オートマトン q 0 b q 1 a a b a

    開始状態 受理状態 b ・aを偶数個含む文字列を受理する オートマトンの現在の状態によって , 入力文字に対する遷移先が変わる → 状態遷移関数 q 2
  6. 制御部 a b a b b 系列 q 0 q

    0 b q 1 a a b a 開始状態 受理状態 b q 2 読み取り ヘッド 状態 遷移図
  7. a b a b b 系列 q 1 q 0

    b q 1 a a b a 開始状態 受理状態 b q 2 状態 遷移図
  8. a b a b b 系列 q 1 状態 遷移図

    q 0 b q 1 a a b a 開始状態 受理状態 b q 2
  9. a b a b b 系列 q 1 状態 遷移図

    q 0 b q 1 a a b a 開始状態 受理状態 b q 2
  10. a b a b b 系列 q 2 状態 遷移図

    q 0 b q 1 a a b a 開始状態 受理状態 b q 2
  11. a b a b b 系列 q 2 状態 遷移図

    q 0 b q 1 a a b a 開始状態 受理状態 b q 2
  12. a b a b b 系列 q 2 受理 状態

    遷移図 q 0 b q 1 a a b a 開始状態 受理状態 b q 2
  13. いくつかの用語の定義 アルファベット:有限の記号の集合. 例, {0, 1}, {a, b,...,z}, {!, ?, #}など

    ギリシャ文字Σで表されるのが一般的. 系列: いくつかのアルファベットの要素を連ねた記号列. 例, 001, 010, 011など 言語: 一定の規則 (文法) によって生成される系列の集合 ε : 何も文字がない系列.空系列.
  14. 有限オートマトンの形式的定義 決定性有限オートマトンは, 以下に示す5項組(Q, Σ, δ, q 0 , F)である 1.

    Qは状態の有限集合 2. Σは有限のアルファベット (ただし空系列εを含まない) 3. δ: Q×Σ → Q は状態遷移関数 4. q 0 ∈ Qは開始状態 5. F ⊆ Qは受理状態の集合
  15. 有限オートマトンの形式的定義 決定性有限オートマトンは, 以下に示す5項組(Q, Σ, δ, q 0 , F)である 1.

    Q = {q 0 , q 1 , q 2 } 2. Σ = {a, b} 3. δは右の表 4. q 0 ∈ Qは開始状態 5. q 2 は受理状態 a b q 0 q 1 q 0 q 1 q 2 q 1 q 2 q 1 q 2 q 0 b q 1 a a b a 開始状態 受理状態 b q 2
  16. 正規表現 a + b: 系列aまたはbからなる集合{a, b} a・b: 系列abからなる集合{ab} a*: aを0個以上並べた系列からなる集合.

    {ε, a, aa, aaa,...} ある1つ正規表現は, 系列の集合を一意に表現する 例: b*(ab*a)*b* aを偶数個含む系列の正規表現
  17. 反復補題の証明 (概略) w i w j q i q 1

    q i 開始状態 受理状態 q n n以上の長さの系列に対して, q i = q j となるi, j (i < j ≦ n) が 少なくとも1組存在する 鳩の巣原理 q j → 系列wの中で, w 1 ~w i をx w i+1 ~w j をy w j+1 以降をzとする q j
  18. 反復補題の証明 (概略) w = xyzが受理される → xの後にyを任意の回数繰り返した系列 w’ = xyyy...yzも受理される

    (状態遷移がq i ~q j でループするため) この系列w’は反復補題のwそのものである. w i w j q i q 1 q i 開始状態 受理状態 q n q j q j
  19. 有限オートマトンで 正しいカッコの系列が受理できないことの証明 • 正しいカッコの系列の1つをw = ((((....()...)))とする(左カッコと右カッコをn回ずつ繰り返した 系列). • wを受理する有限オートマトンの1つをMとすると, wはxyy….yzと書ける

    (反復補題). • xyの長さはn以下なので, x = “(“をn - t回, y = “(“をt回と表せるはずである. • 反復補題により, Mはwからyを取り除いた系列xzも受理するはずである. ところが, xz = “(“をn - t回, “)”をn回なので, これは正しいカッコの系列ではない. • したがって, Mは正しいカッコの系列も正しくないカッコの系列も受理することになり,矛盾が 生じる.
  20. PDAの形式的定義 PDAは以下に示す6項組(Q, Σ, Γ, δ, q 0 , F)である. 1.

    Qは状態の有限集合 2. Σは入力アルファベット(入力テープに書き込める記号) 3. Γはスタックアルファベット (記憶領域に書き込める記号) 4. δ: Q×Σ×Γ → Q×Γ*は状態遷移関数 (δ (q, a, b) = (q’, u)のように書く) 5. q 0 ∈ Qは開始状態 6. F⊆Qは受理状態の集合
  21. TMの構成要素 1 1 q 無限に長い記述領域 1 0 入力系列 1. 記述領域を書き換えられる(入力系

    列が記されているところを書き換え てもOK) 2. 制御ヘッドがいまみている記号を 書き換えたあと(書き換えなくても OK), 左右どちらかに移動し, 内部 状態が遷移する. 3. ヘッドの移動と書き換えを繰り返し, 受理状態か非受理状態になれば計 算終了. いままでの計算モデルと大きく 異なるところ 空白
  22. TMの形式的定義 TMは, 以下に示す7項組(Q , Σ, Γ, δ, q 0 ,

    q r , q a )である. 1. Qは状態の有限集合 2. Σは入力アルファベットかつ, スペース” ”を含まない. 3. Γは記述アルファベットで, Σ ⊆ Γかつ, スペース” ” を含まない      (記述領域 に空白を書き込むことはない) 4. δ: (Q - {q a , q r })×Γ→Q× Γ×{L, R}は状態遷移関数(Lは左移動,Rは右移動に対応) →ヘッドがa∈Γをみているとき, これをa’に書き換えて右か左に移動する.内 部状態 はqからq’に遷移する. これをδ (q, a) = (q’, a’, R),または(q, a, q’, a’, R)などと書く. 5. q 0 ∈ Qは開始状態 6. q a ∈ Qは受理状態 7. q r ∈Qは非受理状態かつ, q r ≠ q a
  23. TMの符号化 TMは, 7項組(Q , Σ, Γ, δ, q 0 ,

    q r , q a )で表現される. → 状態やアルファベットを0と1に符号化すれば, 任意のTMを系列として表現できる (Q , Σ, Γ, δ, q 0 , q r , q a ) → 1111011001100011… • 符号化の例: ◦ 状態Q = {l 1 , l 2 ,...} → 10l1110l21… ◦ アルファベットΣ = {m 1 , m 2 ,...} → 10m1110m21… • 符号化されたTM ∈ {0, 1}* はそれ自体が数であり 別のTMへの入力として扱うことができる
  24. 万能チューリングマシン いま, 任意のTMをMとする.Mを符号化した系列を[M]とするとき, [M, w] (系列wが入力されたMを符号化した系列) を入力として, Mの動きを模倣することができるTMを,万能チューリングマシンという. ・ある計算モデルが万能TMを模倣できるとき, その計算モデルは

    チューリング完全であるという うっかりチューリング完全になっちゃったもの 1 X 1 0 1 1 1 0 X 1 0 0 現況部 (状態を記録する) 記述部 ([M]を書く) テープ部 (入力系列を書く) $ 万能TMの記述領域の構成
  25. 1 1 停止性チューリングマシン 1 1 q 1 0 入力系列w q

    a 0 1 出力系列 f (w) 任意の系列w ∈ Σ*に対し, 必ずf (w) ∈ Σ*を残して, 受理状態 または非受理状態で停止するTM (計算がループしない) →言語Lについて, w ∈ Lならば停止性TMが受理状態で停止す るとき, 停止性TMは言語Lを決定するという
  26. 停止性TMによる計算の定義 任意の関数 f : Σ* → Σ*についてTMが存在して, そのTMが 入 力w

    ∈ Σ*を受け取ったとき, 有限回計算を繰り返したのち, f (w) ∈ Σ*を出力して停止するならば, そ の関数は計算可能である. ・系列wに対してf (w)を計算する停止性TMをみつけることを, 問題という ・とくに, f (w) = 0 or 1, つまり出力が真か偽のみである問題を, 決 定問題という
  27. 停止問題が決定不能であることの証明 たとえば, あるM i に[M j ]を入力したとき, 結果は ループする (

    = loop) か停止する (= halt) かのどちらである. その結果は下の表のように表せる [M 0 ] [M 1 ] [M 2 ] [M 3 ] M 0 halt loop loop halt M 1 halt loop halt halt M 2 halt loop halt loop M 3 loop loop loop halt
  28. 停止問題が決定不能であることの証明 Hを利用することによって, [M i ]が入力されたときに, M i ([M i ])

    がloopならばhalt, haltならばloopであるTM Eを構成できる Hの状態遷移図 受理状態 非受理状態
  29. 停止問題が決定不能であることの証明 Hを利用することによって, [M i ]が入力されたときに, M i ([M i ])

    がloopならばhalt, haltならばloopであるTM Eを構成できる Hの状態遷移図 受理状態 非受理状態 Γ Γ Eの状態遷移図の一部 何を入力されても ループする
  30. 停止問題が決定不能であることの証明 Hを利用することによって, [M i ]が入力されたときに, M i ([M i ])

    がloopならばhalt, haltならばloopであるTM Eを構成できる Γ Γ [M i ]を入力 [M i ]を[M i , [M i ]]に変換 E ([M i ]) の状態遷移図 Hを改変 M i ([M i ]) = loopならば 受理して停止する M i ([M i ]) = haltならば ループし続ける
  31. [M 0 ] [M 1 ] [M 2 ] [M

    3 ] [M k ] M 0 halt loop loop halt M 1 halt loop halt halt M 2 halt loop halt loop M 3 loop loop loop halt M k (= E) loop halt loop loop ???
 停止問題が決定不能であることの証明 loopでもhaltでも矛盾する!! = Hは存在しない
  32. 問題の帰着 決定問題A, Bに対して次が成り立つとき, 問題Aは問題Bに帰着されるといい, A ≦ Bと表す. ・A(w) = 1 ⇔ B(f

    (w)) = 1となる関数 f が存在する. →問題Aを決定するTMをみつければ, 問題Bも決定できる ある問題XがTMの停止問題に帰着されるとき, 問題Xを機械的に決定することは原理的に不可能といえる
  33. Postの対応問題 a ab b ca ca a a ab abc

    c のようなタイルを組み合わせて 上段をつないだ系列と下段をつないだ系列を一致させることができるか? 任意のタイルの系列に対してこの問題を解くアルゴリズムは存在しない → 決定不能問題 (TMの停止問題に帰着できる)
  34. 決定不能問題の例 ・4辺が異なる色で塗られたタイルの隣接する辺の色が等しくなるように, タイルを全平面に敷き詰められるか? ・プログラムAはプログラムBと完全に同じ動作をするか? (仕様通りに動くか?) ・プログラムAは無限ループするか? ・整数係数の多変数方程式 f (x 1

    , x 2 ,..., x n ) = 0は整数解をもつか? ・(u 1 , v 1 ), (u 2 , v 2 ),..., (u n , v n ) のペアをいくつか並べて, uを連ねた系列とvを連ねた系列を一致させることができるか? 決定不能問題が存在することは 機械的計算の原理的限界を示している (ゲーデルの不完全性定理と関係)
  35. AIとの関連 (ニューラルチューリングマシン)
 • Neural Turing Machines (Alex et. al, 2014)


    ◦ チューリングマシンをニューラルネットワーク(NN)で再現
 = 自動プログラミング
 ◦ NNがチューリング完全なら
 プログラムの挙動を原理的に学習できる