Microsoft PowerPoint - tm ppt [互換モード]

計算理論

I

（チューリング機械と決定不能性）

計算理論

I

（チュ リング機械と決定不能性）

平成21年度 第I期

ソフトウェア基礎学講座

安本 慶一

安本 慶

2

スケジュール

„

講義日程（６回）

5月11，14，18，21，25，28日（月曜1限，木曜2限）

5月11，14，18，21，25，28日（月曜1限，木曜2限）

テスト：

6月1日（月）1限 （資料，参考書持込可）

„

講義資料

¾以下のURLで配布 ¾http://ito-lab.naist.jp/~yasumoto/lecture/tm/ ¾毎回の授業前に各自でダウンロード・印刷すること

„

参考書

„

参考書

1. Michael Sipser: “Introduction to the Theory of Computation, Second Edition,” Course Technology, 2006 (Chapter 3 - 5)

2. 野崎，高橋，町田，山崎訳：“オートマトン言語理論 計算論II [第2版]” ，サイエンス社，2003 （第8章～9章）

3. 丸岡章：“計算理論とオートマトン言語理論”，サイエンス社，2005（第6章～7章） 4. 岩間一雄：“アルゴリズム理論入門”，昭晃堂，2001

その他

„

成績判定

¾

オートマトン（伊藤先生担当分

50点）+チューリング機械(安本担当分50点)の

合計

点

上

を合格

合計

60点以上

を合格

„

質問など

¾

在室時オフィスまで直接，または，

e-mailにて随時

¾

担当教員 （オフィス：A613 ）

•安本（yasumoto@is）

¾

TA （オフィス A616）

¾

TA （オフィス：A616）

•D2勝間(ryo-k@is)，M2清川(kota-k@is)，M2神山(naoya-k@is) 4

本講義の目的

„

計算機とは何か？何ができて何ができないのか？

¾究極に簡素化した数学的計算モデル（チューリング機械）を使って「計算可能性」を学ぶ 計算 能 解を答 「解がな 答 計算 ゴ ズ が存在 ¾計算可能：問題に対し解を答える/「解がない」と答える計算手順（アルゴリズム）が存在 ¾チューリング機械（TM）：現代の計算機にいくらでもメモリ，時間を使えるとしたもの ¾計算可能性の定義：TMで計算できる⇔一般的に計算できる（他の定義とも一致） ¾計算できない問題がある（プログラムの停止性問題，ヒルベルト第10問題など）

„

計算量理論を学ぶための準備

¾計算量理論（アルゴリズムの実行時間や必要な記憶容量を数学的に扱う理論）は本講 ¾計算量理論（アルゴリズムの実行時間や必要な記憶容量を数学的に扱う理論）は本講 義では扱わないが，学ぶためにはチューリング機械の知識が必須 •多項式問題：問題サイズnに対し，計算量は多項式オーダ（O(n2_{)など）→実行可能} •NP完全問題：問題サイズnに対し，計算量は指数オーダ（O(2n_{)など）→実行不能} •与えられた問題がNP完全であるかどうかの証明（計算理論IIIで学ぶ）

講義概要

„

チューリング機械（第

1回～3回）

¾チューリング機械（TM）の定義

：

TM=FA＋無限長の書換可能なテープ

¾

TMとFA（有限オートマトン）との能力（解ける問題のクラス）の違い

¾

TMの能力⊇現代の計算機の能力 ※処理速度は無視

¾

TMへの機能拡張（拡張しても能力は変わらない）Æ標準TMは十分強力

•複数テープ，非決定性，ランダムアクセスなどを拡張（アルゴリズムの記述は容易に）

¾

TMによるアルゴリズムの記述法

„

計算機で解けない（決定不能）問題とその証明法（第4回～6回）

解けな 問題（

計算機 解けな 問題）

¾

TMで解けない問題（＝計算機で解けない問題）

¾万能チューリング機械

: 任意のTMのプログラムを読み込んで実行するTM

¾

ある問題（プログラムの停止性判定問題など）が

決定不能

なことを証明Æ 対

角線論法によりその問題を解くアルゴリズム（TM）が存在しないことを示す

¾帰着を用いた証明法

：既知の決定不能問題の対象問題への変換により証明

6

1. チューリング機械

チューリング機械登場の背景

„

19世紀末～20世紀初頭

ヒルベルト・プログラム

（

D. Hilbert）始動

¾数学の全てを形式化し，数学全体の完全性と無矛盾性を示そうとする試み ¾ヒルベルトの23の問題（1900年） 第10問題：n 個の未知数を含む整数係数の多項式P(x₁,…,xn)が与えられたとき，「方程 式P(x1,…,xn)=0が整数解を持つかどうか」を判定するアルゴリズムを考案せよ 例）6x3_yz2_+3xy2_−x3_{−10=0のとき，解(x,y,z)=(5,3,0)が存在する} 答え：そのようなアルゴリズムは，存在しない！

„

当時，

“アルゴリズム”

が何を意味するかは数学的に厳密に定義されておらず，直感

的なイメージ（意図した計算結果を得るための計算手順，等）が用いられていた．

Æ

アルゴリズムを数学的に扱う枠組み

„

1936年

チューリング（A. Turing）が

チューリング機械

発表

¾あらゆる計算（すなわち，アルゴリズム）の形式化，数学的議論が可能に．．． „1940年頃 最初のプログラム可能な計算機登場 „1945年 プログラム内蔵方式（J. von Neumann） (万能チューリング機械はその概念を先取り) „1946年 米ペンシルバニア大がENIAC開発 8

チューリング賞

„

コンピュータサイエンス分野のノーベル賞にあたる権威ある賞

¾優れた功績を残した人に年に1度，米国学会ACM (Association for Computing

Machinery)が贈る Machinery)が贈る

¾賞金は10万ドル以上（Intel, Googleが後援）

„

近年の受賞者

2003年 Alan Kay Æ オブジェクト指向技術 2004年 Robert E. Kahn，Vinton G. Cerf Æ TCP/IP 2005年 Peter Naur Æ プログラミング言語ALGOL60の定義

2006年 F E All Æ コンパイラ最適化技術

2006年 Frances E. Allen Æ コンパイラ最適化技術

2007年 Edmund M. Clarke，E. Allen Emerson，Joseph Sifakis Æ モデル検査技術 2008年 Barbara Liskov Æ プログラミング言語設計技術

チューリング機械（以下

TM

と略記）でできること

„

有限オートマトン

(FA)で受理できない言語の取り扱い

¾

L={0

n

1

n

}

_{これらの言語を受理するプログラムを}

¾

L={w | w=w

R

_}

„

チューリング機械では，計算機で実行可能な任意のプログラムを，シン

プルなモデルで表現できる

¾TM=有限オートマトン＋無限容量メモリ（無限長テープへの読み書き）

計算機 扱うあらゆる問題に対する計算可能性を数学的に議論

C言語などで作成するのは簡単，TMでももちろん可能

„

計算機で扱うあらゆる問題に対する計算可能性を数学的に議論

¾与えられた問題が決定不能（計算機で解けない/アルゴリズムが存在しない）であることを 数学的に証明 ¾与えられた問題がどれくらい難しい（解くのに時間を要する）のかを解析 10

TMの入出力

„

有限オートマトンと同じく，TMは与えられた入力記号列wを受理するかどうかを判定

動作

受理状態 拒否状態で停止

TM M

入力

：w

動作

：受理状態，拒否状態で停止

または停止しない(無限ループ)

出力

：受理で停止時のテープの内容

Æ

M(w)

と表記

„

TM Mが

受理

する入力の集合

Æ

受理言語

と言い，

L(M)

と表記

¾L(M)は，∅（どの入力も受理しない）, 有限集合，無限集合 のいずれか ¾どんなΤΜ Μ に対しても，その受理言語L(M)が存在し，一意に定まる

TMが扱う問題

„

TM Mは入力文字列wが，Mの受理言語L(M)に属しているかどうかを判定

言語とは何か

„

言語とは何か？

¾ある性質を持つ文字列集合（文字列に含まれる0の数と1の数が同じ，など） ¾すなわち，入力が，ある特定の性質をもつかどうかを判定する問題をTMは扱う．

„

本講義では，以降，言語への所属判定＝判定問題，として扱う

例）言語L={素数の集合}を受理するTMは，問題「入力が素数かどうか」を判定する．

例えば以下の判定問題は全て言語として定式化でき，TMで扱うことができる

9プログラムの停止性判定問題 9グラフがオイラー閉路（全ての辺が一筆書きできる）を持つか 9論理関数 f(x1, x2, ..., xn)に対し，f(x1, ..., xn)=1となる各変数への割当て方は存在するか？ 12

TMの定義

„

有限オートマトンに無限容量メモリ（読み書き可能なテープ）を拡張した計算モデル

¾有限制御部：有限個の状態を持ち，現在どの状態にいるのか記憶 ¾テ プ セルに分割されており 各セルは つの記号を保持 ¾テープ：セルに分割されており，各セルは一つの記号を保持 •最初，有限長の入力記号列wがテープ上に左詰で置かれる（wは空白を含まない!） ¾ヘッド：現在指しているセルの内容の読み取り，書き込み，左右への移動が可能 •TM始動時のヘッドの位置は，入力記号列wの左端

テープ

入力列w（空白含まない） 空白記号

ヘッド

有限制御部

a

a

b

a

a □ □ ...

$

終端マーカ

（これより左には 移動しない） テープの右側は 空白のセルが無 限にある

q

r

定義

1.1: TMの形式的定義

„

7項組 M = (Q, ∑, Γ, δ, q

₀

, q

accept

, q

reject

) で定義

（※定義は参考書ごとに異なる） TMへの入力wにはΣ の元のみ現れる 記号 説明 _{の元のみ現れる} ※Γ-Σ の元（空白記号 など）は現れない 記号 説明 Q 状態の有限集合 ∑ 入力記号の集合 ※ □ を含まない Γ テープ記号の集合 （Σ ∪{$, □, ...}） δ 遷移関数( Q ×∑ → Q ×Γ×{L, R}) ) q₀ 初期状態 (q0ג Q) qaccept 受理状態 (qacceptג Q) ※到達すると直ちに停止 L, Rはヘッドの 移動方向

„

δ の各遷移は δ(q,a) = (r,b,R) と表記

¾状態q で記号a を読んだら，現セルをb に書き換え，ヘッドを右に1つ移動し，状態r に移る

q

a/b, R

r

accept (qaccept Q) q_reject 拒否状態 (qrejectג Q) ※到達すると直ちに停止 14

TMの状態遷移図

Y/Y, R 0/0 R Y/Y, L_{0/0 L} X/X, R •遷移はx/y, Dの形式 •DはL（左）またはR （右）のどちらか

例1.1:

Σ {0 1}

遷移元と先が同 じなら複数の遷 移をまとめて書い ても良い 0, Yを読み 飛ばす

q

₀ 0/X, R Y/Y, R

q

₂ 1/Y, L

q

₁

q

₃

q

_accept 0/0, R _{0/0, L} □/□, R

q

_reject □/□, R 1/1, R _{•受理状態，または，拒} 否状態に到達すると， 直ちに停止

Σ={0,1},

Γ=Σ

∪

{$,

□,X,Y

}

□/□, R

q

₄ Y/Y, R 0, Yの間 巻き戻す Y/Y, R qaccept q0 qreject 初期状態 受理状態 拒否状態 •遷移の形式には色々バリエーションがあり，参考書ご とに異なるが，モデルとしては等価（証明は略） •Dとして，S（ヘッドを移動させない）を持つモデルもある

q

₄ 1/1, L 0/0, L

TMと有限オートマトンとの違い

„

TM Mは読み書き可能な無限テープを持つ

¾テープへの読み書き，および，読み書き位置の 変更が可能 a/□, R □/□, R qaccept

„

TM Mは入力の末尾に達しても停止しない

¾空白記号を読みながら動作を継続 ¾いつまでも停まらないかも知れない ¾永遠に止まらないTMを記述するのは簡単

„

TM M は

受理状態

または

拒否状態

に到達すると即座に

停止

¾テープの内容やヘッドの位置に関係なく，qacceptまたはqrejectに到達すると停止 q₀ q1 □/□, L 無限ループを含むTMの例 容 関 ，qaccept qreject 停 ¾入力の読み込み途中で，それより後ろの文字列を読み込んでいなくても，見てないところ も含めて受理する

„

TM M が入力wに対して動作開始した時の結果は次の3通り

¾受理状態で停止： Mはwを受理する ¾拒否状態で停止： Mはwを受理しない ¾停止しない（無限ループ）：Mはwを受理しない 16

様相（

configuration）:TMのある時点での様子

„

様相の書き方

$ 1 1 0

1q

3

10

現在の状態 現在の状態

x

1

x

2

...x

i-1

q

x

i

x

i+1

...x

n

„

様相によるTMの動作の表現

ヘッド上の記号 特例： ヘッドの左側に何もないとき，qx1x2...xn ヘッド上から右側が全て空白のとき，x1...xi-1q□ 現在の状態：q3 空白を一つ書く！ ヘッドの左側の 記号列($からヘッ ド手前まで．$は 書かない) ヘッドの右側の記号列 （ヘッドから最も右の非空白記号まで）

„

様相によるTMの動作の表現

¾様相C1にδ の遷移を適用し様相 C2が得られるとき，“C1はC2を導出する”という ¾C1 ├ C2と表記 ¾C₀ ├ C₁├ ... ├ Cnのとき（0回以上の導出），C0 ├* Cn と書く ¾TMの動作は，初期様相C0=q0wからqacceptまたはqrejectを含む様相への列として表現可能 ¾様相の列がq またはq に到達せず無限ループすることもある

TMの動作例

„

例

1.1のTM Mに文字列“01”を入力したときの動作

q0 _{0/X, R} Y/Y, R q2 1/Y, L q1 q3 qaccept Y/Y, R 0/0, R Y/Y, L_{0/0, L} X/X, R □/□, R qreject □/□, R 1/1, R q4 □/□, R Y/Y, R q3 accept Y/Y, R 0 1 q₀ X 1 X Y X Y X Y X Y

q

0

01

q₁

Xq

1

1

├

q₂

q

2

XY

├

q₀

Xq

0

Y

├

q₃

XYq

3

□

├

qaccept

XY□q

accept

□

├

TM M

q4 1/1, L 0/0, L 18

練習問題

問

1.1: 例1.1のTM Mについて以下の問いに答えよ．

a) 0011を入力するとどうなるか．

b) 011を入力するとどうなるか．

TMの停止性

„

TM Mは入力wに対して，以下のいずれかの動作を行う

(1) q

accept

に到達して停止

(2) q

に到達して停止

(2) q

reject

に到達して停止

(3) 永遠に停まらない（無限ループ）

Mがwを受理するのは(1)の場合のみ

(2)と(3)の場合はwを受理しないが，(3)かどうかを見極めるのは困難

Decider と Recognizer

„

「計算できる」の定義

¾

問題に対し，解を答える，または，解がないと答えるアルゴリズムが存在する

¾

語wの言語Lへの所属判定問題の場合

20

¾

語wの言語Lへの所属判定問題の場合

•wがLに属する時はwを受理し，そうでない時はwを拒否して停止するTMが存在

„

TMの能力に応じて以下の呼称を用いる

¾Decider

•

ある言語Lが存在し，任意の入力wに対し，w∈Lの時はq

_accept

に到達し停

止し，

w

∉

L

の時はq

_reject

に到達し停止するTM

¾Recognizer

•

ある言語Lが存在し，任意の入力wに対し，w∈Lの時はq

_accept

に到達し停

止する

TM

•

w∉Lの時は停止しないかも知れない

•問題が計算できる⇔deciderが存在 deciderが存在しないがrecognizerなら存在する問題もある（両方存在しない問題もある）

半決定可能

/決定可能な言語の定義

„

定義

1.2: ある言語Lのrecognizerが

存在する

とき，Lは

半決定可能

(semi-decidable or Turing-recognizable)

1

_と言う．

„

定義1.3: ある言語Lのdecider が

存在する

とき， Lは

決定可能

(decidable)

2

_{であると言う．}

•

Lが決定可能であるとき，Lは半決定可能でもある

¾

Lのdecider Mは，任意の文字列w∈Lを受理するため．．．

¾

Lのdecider Mは，任意の文字列w∈Lを受理するため．．．

参考書によっては，以下のように呼ぶことも．．．

1_{帰納的可算(RE: recursively enumerable)}

2_{帰納的(recursive)} 22

言語Lが半決定可能/決定可能であることの証明法

„

与えられた言語Lが半決定可能であることを証明したい

¾

Lのrecognizerまたはdeciderを一つ構成する

„

Lが決定可能であることを証明したい

¾

Lのdeciderを一つ構成する

„

他の証明方法

¾

既知の（半）決定可能な言語に帰着する（帰着は 後に学ぶ）

¾

既知の（半）決定可能な言語に帰着する（帰着は，後に学ぶ）

決定可能な言語の例

問

1.2:

a) 有限長文字列の有限集合はどれも決定可能か？

b) 正則言語はどれも決定可能か？

24

TMの簡略記述

„

TMの形式的記述（

形式レベル記述

と呼ぶ）は煩雑

¾

全状態，状態遷移関数を含む

7項組M = (Q,

∑, Γ, δ, q

₀

, q

accept

, q

reject

)全て

を記述する もしくは 相当する状態遷移図を与える必要がある

を記述する，もしくは，相当する状態遷移図を与える必要がある

„

労力軽減のため

TMを簡略記述する（

抽象レベル記述

と呼ぶ）

¾

ヘッドの移動，テープに書き込む記号の種類，手順を自然語で記述（状態，状

態遷移などは与えなくて良い）

„

言語Lが半決定可能（または決定可能）であることを証明するには L

„

言語Lが半決定可能（または決定可能）であることを証明するには，L

の

recognizer（またはdecider）を抽象レベルで構成する

¾

注意

•抽象レベルで記述したTMから，等価な形式レベルのTMが構成できることが必要 •Deciderの場合は，どんな入力に対しても停止することが必要

TMの抽象レベル記述例

„

例

1.2:

を受理する

TM Mを構成せよ．

（抽象レベル記述）

}

0

|

0

{

2

_≥

=

n

L

n 基本アイデア1回のループで0の個数 を半分にする．最後に一 つだけ0が残れば受理． ゴ ズ

（抽象レベル記述）

Mは入力wを入力すると以下のように動作する． (ステップ1) テープの左端から入力wの右端に向かってヘッドを移動させながら一つおきに0を テープ記号Xに書き換える（0の個数を半分にする） (ステップ2) ステップ1で0の数が1つだったら，停止して受理（accept） (ステップ3) ステップ1 で0の数が（1以外の）奇数だったら，停止して拒否（reject） (ステップ4) ヘッドをテープの左端に戻す (ステップ5) ステップ1から繰り返す ※アルゴリズムはこれ以 外に色々考えられる！ （注）TMを構成する際には，テープ記号として，入力アルファベットΣ以外の（有限個の）記 号（X, Y, Zなど）を使用して良いことに留意せよ．

„

よくある間違い

(TMにない機能を使うのは×)

¾

変数を使う，算術演算を使う，など

26

練習問題

問

1.3: 例1.2のTMを形式レベル（状態遷移図）で記述せよ．

ヒント：1の個数が1の場合，偶数個の場合，奇数個（3つ以上）の場合を異なる状態で区別する．

問1.4: 以下の言語を決定するTMを構成せよ（“抽象レベル”でよい）．

a) 同数の0と1を含む列の集合（ただし，Σ={0,1}） b) {wwR_{| wは0,1の任意の列} （2005年テスト問題）} c) {0n₁₀n_{| n}≥ 0 } （2006年テスト問題）

一般の判定問題を

TMで扱う方法

扱いたい問題を表す言語を定義

Æ言語への所属判定としてTMで扱うことができる．

(1) 入力が文字列であるような問題

(1) 入力が文字列であるような問題

(2) 入力が任意のオブジェクトであるような問題

Æ オブジェクトを2進列に符号化

9プログラムの停止性判定問題 ¾任意のプログラムコードは2進数の列で符号化できる． ¾L={任意の入力で停止するようなプログラムの2進列の集合}とすれば，言語になる． 9グラフがオイラー閉路（全ての辺が一筆書きできる）を持つか 素数判定問題：L={全ての素数の集合} 文法チェック問題：L={正しい文法で書かれたJavaプログラムの集合} ¾行列やグラフを2進文字列として符号化する． ¾L={オイラー閉路を持つグラフの符号の集合}とすれば，言語の認識問題になる． 9論理関数 f(x1, x2, ..., xn)に対し，f(x1, ..., xn)=1となる各変数への割当て方は存在するか？ ¾例えば，x1∧¬x2∨¬x1∧x3=1を満たす割り当て方は，x1=1, x2=0, x3=1である． ¾全ての論理関数を2進符号化し，真になる割当て方が存在するものの集合を受理言語 とする． 28

TMで解ける（決定可能な）判定問題の例

例1.3: 判定問題「与えられた無向グラフGが連結であるかどうか」は決定可能か？

„

証明

¾ ( )で与えられ 頂点の集合は { } 辺の集合は { }

¾ G=(V,E)で与えられ，頂点の集合はV={v₁,v₂,...,v_n}, 辺の集合はE={e₁,...,e_m}

¾ 無向グラフGの符号を〈G〉と表記する． ¾ 図のグラフは例えば_{〈G〉 =(1#2#3#4)((1#2)(1#3)(2#3)(3#4))} のように符号化できる． ¾ 次のTMを構成する．ただし，Σ={(, ), #, 1, 2, 3, 4}, Γ=Σ ∪{1’, 2’, 3’, 4’, $, □} 最初 点を クす （ 点“ を“ ”に書き換え ）

2

1

3

4

V

E

1. Gの最初の頂点をマークする（頂点“1”を“1’”に書き換える）． 2. マークされた頂点がこれ以上増えなくなるまで3. を繰り返す 3. Gの各頂点に対し，マークされた頂点からの辺があるとき，その頂点をマークする 4. 全ての頂点をスキャンし，全てマークされていたらaccept，そうでなければreject ¾ 上記のTMはこの問題のdeciderになっていることは明らか．∴決定可能 □

練習問題

問

1.5: 例1.3の判定問題を表す言語を定義せよ．

30

記号の用法

„

文字（記号）

¾0, 1, a, b, X, Yなどで表記 ¾文字変数は，x, yなどで表記

慣例的な用法

a,b,... 文字

„

アルファベット（文字の有限集合）

¾Σ と表記．例） Σ={0,1}, Σ={a, b, c}など

„

文字列（語）

¾例）0010, aabc, 0k₁k_{, vv}R ¾入力文字列は慣用的にw と表記

„

空列

¾ε と表記．例）任意の文字列wに対して，w0_=ε

„

空集合

q,r,... 状態

x,y,... 文字変数

w ... (入力)文字列

i,j,k,l,m,n ... 整数

A,B,... 集合

M ... 機械

L ... 言語

〈M〉

機械Mの符号

¾∅と表記（εとは異なるので間違えないように！）

„

言語（文字列の集合）

¾L と表記．例） L={0n₁n| n≥0}={ε, 01, 0011, 000111, ...}

„

オブジェクト（グラフなど）Oを符号化した文字列（符号化法は固定）

¾〈O〉と表記．

〈M〉 ... 機械Mの符号

（＝プログラムコード）

まとめ

„

チューリング機械（

TM）とは

¾

形式的な定義

¾

状態遷移図

¾

様相（

configuration）

¾

TMの記述法（形式レベル記述と抽象レベル記述）

¾

半決定可能な言語と，決定可能な言語

¾

TMが扱う問題は判定問題

•言語への所属判定⇔一般の判定問題

„

Homework（次回講義時に提出）

¾

問1.1～1.5