計算理論I（チューリング機械と決定不能性）

1
計算理論I（チュ
（チューリング機械と決定不能性）
リング機械と決定不能性）
平成21年度 第I期
ソフトウェア基礎学講座
安本 慶
慶一
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
1
3
その他
„成績判定
¾オートマトン（伊藤先生担当分50点）+チューリング機械(安本担当分50点)の
合計 点 上を合格
合計60点以上を合格
„質問など
¾在室時オフィスまで直接，または，e-mailにて随時
¾担当教員 （オフィス：A613 ）
• 安本（yasumoto@is）
¾TA （オフィス：A616）
（オフィス 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で学ぶ）
2
5
講義概要
„チューリング機械（第1回～3回）
¾チューリング機械（TM）の定義：TM=FA＋無限長の書換可能なテープ
¾TMとFA（有限オートマトン）との能力（解ける問題のクラス）の違い
¾TMの能力⊇現代の計算機の能力 ※処理速度は無視
¾TMへの機能拡張（拡張しても能力は変わらない）Æ標準TMは十分強力
• 複数テープ，非決定性，ランダムアクセスなどを拡張（アルゴリズムの記述は容易に）
¾TMによるアルゴリズムの記述法
„計算機で解けない（決定不能）問題とその証明法（第4回～6回）
¾TMで解けない問題（＝計算機で解けない問題）
解けな 問題（ 計算機 解けな 問題）
¾万能チューリング機械: 任意のTMのプログラムを読み込んで実行するTM
¾ある問題（プログラムの停止性判定問題など）が決定不能なことを証明Æ 対
角線論法によりその問題を解くアルゴリズム（TM）が存在しないことを示す
¾帰着を用いた証明法：既知の決定不能問題の対象問題への変換により証明
6
1. チューリング機械
3
7
チューリング機械登場の背景
„19世紀末～20世紀初頭 ヒルベルト・プログラム（D. Hilbert）始動
¾数学の全てを形式化し，数学全体の完全性と無矛盾性を示そうとする試み
¾ヒルベルトの23の問題（1900年）
第10問題：n 個の未知数を含む整数係数の多項式P(x1,…,xn)が与えられたとき，「方程
式P(x1,…,xn)=0が整数解を持つかどうか」を判定するアルゴリズムを考案せよ
例）6x3yz2+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)が贈る
¾賞金は10万ドル以上（Intel, Googleが後援）
„近年の受賞者
2003年 Alan Kay Æ オブジェクト指向技術
2004年 Robert E. Kahn，Vinton G. Cerf Æ TCP/IP
2005年 Peter Naur Æ プログラミング言語ALGOL60の定義
2006年 Frances
F
E
E. All
Allen Æ コンパイラ最適化技術
2007年 Edmund M. Clarke，E. Allen Emerson，Joseph Sifakis Æ モデル検査技術
2008年 Barbara Liskov Æ プログラミング言語設計技術
4
9
チューリング機械（以下TMと略記）でできること
„有限オートマトン(FA)で受理できない言語の取り扱い
¾L={0n1n}
¾L={w | w=wR}
これらの言語を受理するプログラムを
C言語などで作成するのは簡単，TMでももちろん可能
„チューリング機械では，計算機で実行可能な任意のプログラムを，シン
プルなモデルで表現できる
¾TM=有限オートマトン＋無限容量メモリ（無限長テープへの読み書き）
„計算機で扱うあらゆる問題に対する計算可能性を数学的に議論
計算機 扱うあらゆる問題に対する計算可能性を数学的に議論
¾与えられた問題が決定不能（計算機で解けない/アルゴリズムが存在しない）であることを
数学的に証明
¾与えられた問題がどれくらい難しい（解くのに時間を要する）のかを解析
10
TMの入出力
„有限オートマトンと同じく，TMは与えられた入力記号列wを受理するかどうかを判定
入力：w
動作：受理状態，拒否状態で停止
動作
受理状態 拒否状態で停止
または停止しない(無限ループ)
TM M
出力：受理で停止時のテープの内容
ÆM(w)と表記
„TM Mが受理する入力の集合Æ受理言語と言い，L(M)と表記
¾L(M)は，∅（どの入力も受理しない）, 有限集合，無限集合 のいずれか
¾どんなΤΜ Μ に対しても，その受理言語L(M)が存在し，一意に定まる
5
11
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
有限制御部
□ □
...
テープの右側は
空白のセルが無
限にある
6
13
定義1.1: TMの形式的定義
„7項組 M = (Q, ∑, Γ, δ, q0 , qaccept , qreject) で定義 （※定義は参考書ごとに異なる）
TMへの入力wにはΣ
の元のみ現れる
※Γ-Σ の元（空白記号
など）は現れない
記号
説明
Q
状態の有限集合
∑
入力記号の集合 ※ □ を含まない
Γ
テープ記号の集合 （Σ ∪{$, □, ...}）
δ
遷移関数 ( Q ×∑ → Q ×Γ×{L, R}) )
q0
初期状態 (q0 ‫ ג‬Q)
qaccept 受理状態 (qaccept ‫ ג‬Q)
L, Rはヘッドの
移動方向
※到達すると直ちに停止
拒否状態 (qreject ‫ ג‬Q) ※到達すると直ちに停止
qreject
q
a/b, R
„δ の各遷移は δ(q,a) = (r,b,R) と表記
r
¾状態q で記号a を読んだら，現セルをb に書き換え，ヘッドを右に1つ移動し，状態r に移る
•遷移はx/y, Dの形式
•DはL（左）またはR
（右）のどちらか
TMの状態遷移図
X/X, R
例1.1:
0, Yを読み
飛ばす
Σ={0,1},
Σ
{0 1}
Γ=Σ ∪
{$,□,X,Y}
q0
Y/Y, R
□/□, R
qaccept
q3
Y/Y, R
q0
qaccept
qreject
初期状態 受理状態 拒否状態
q1
0/X, R
□/□, R
1/1, R
Y/Y, R
q4
14
遷移元と先が同
じなら複数の遷
移をまとめて書い
ても良い
Y/Y, R
0/0 R
0/0,
1/Y, L
Y/Y, L
0/0 L
0/0,
q2
0, Yの間
巻き戻す
□/□, R
qreject
•受理状態，または，拒
否状態に到達すると，
直ちに停止
1/1, L
0/0, L
•遷移の形式には色々バリエーションがあり，参考書ご
とに異なるが，モデルとしては等価（証明は略）
•Dとして，S（ヘッドを移動させない）を持つモデルもある
7
15
TMと有限オートマトンとの違い
„TM Mは読み書き可能な無限テープを持つ
¾テープへの読み書き，および，読み書き位置の
変更が可能
qaccept
a/□, R
q1
q0
„TM Mは入力の末尾に達しても停止しない
¾空白記号を読みながら動作を継続
¾いつまでも停まらないかも知れない
¾永遠に止まらないTMを記述するのは簡単
□/□, R
□/□, L
無限ループを含むTMの例
„TM M は受理状態または拒否状態に到達すると即座に停止
¾テープの内容やヘッドの位置に関係なく，q
容
関
，qaccept またはqqreject に到達すると停止
停
¾入力の読み込み途中で，それより後ろの文字列を読み込んでいなくても，見てないところ
も含めて受理する
„TM M が入力wに対して動作開始した時の結果は次の3通り
¾受理状態で停止： Mはwを受理する
¾拒否状態で停止： Mはwを受理しない
¾停止しない（無限ループ）： Mはwを受理しない
16
様相（configuration）:TMのある時点での様子
„様相の書き方
$ 1 1 0
1q310
現在の状態
現在の状態 3
現在の状態：q
x1x2...xi-1 q xixi+1...xn
ヘッドの左側の
記号列($からヘッ
ド手前まで．$は
書かない)
ヘッドの右側の記号列
（ヘッドから最も右の非空白記号まで）
ヘッド上の記号
空白を一つ書く！
特例：
ヘッドの左側に何もないとき，q x1x2...xn
ヘッド上から右側が全て空白のとき，x1...xi-1 q □
„様相によるTMの動作の表現
¾様相C1にδ の遷移を適用し様相 C2が得られるとき，“C1はC2を導出する”という
¾C1 ├ C2 と表記
¾C0 ├ C1├ ... ├ Cn のとき（0回以上の導出）， C0 ├* Cn と書く
¾TMの動作は，初期様相C0=q0wからqacceptまたはqrejectを含む様相への列として表現可能
¾様相の列がqacceptまたはqrejectに到達せず無限ループすることもある
8
17
TMの動作例
„例1.1のTM Mに文字列“01”を入力したときの動作
X/X, R
Y/Y, R
0/0, R
q0
□/□, R
1/1, R
Y/Y, R
□/□, R
qaccept
Y/Y, R
q3
Y/Y, R
q001
0
q0
1
Xq11
├
X
q1
0/X, R
1/1, L
0/0, L
1
X
q1
q2
Y
q2
1/Y, L
□/□, R
qreject
q4
q2XY
├
Y/Y, L
0/0, L
TM M
Xq0Y
├
X
Y
├
XYq3□ ├ XY□qaccept□
X
q0
X
Y
q3
Y
qaccept
18
練習問題
問1.1: 例1.1のTM Mについて以下の問いに答えよ．
a) 0011を入力するとどうなるか．
b) 011を入力するとどうなるか．
9
19
TMの停止性
„TM Mは入力wに対して，以下のいずれかの動作を行う
(1) qacceptに到達して停止
(2) qrejectに到達して停止
(3) 永遠に停まらない（無限ループ）
Mがwを受理するのは(1)の場合のみ
(2)と(3)の場合はwを受理しないが，(3)かどうかを見極めるのは困難
20
Decider と Recognizer
„「計算できる」の定義
¾問題に対し，解を答える，または，解がないと答えるアルゴリズムが存在する
¾語wの言語Lへの所属判定問題の場合
• wがLに属する時はwを受理し，そうでない時はwを拒否して停止するTMが存在
„TMの能力に応じて以下の呼称を用いる
¾Decider
• ある言語Lが存在し，任意の入力wに対し，w∈Lの時はqacceptに到達し停
止し， w∉ L の時はqrejectに到達し停止するTM
¾Recognizer
• ある言語Lが存在し，任意の入力wに対し，w∈Lの時はqacceptに到達し停
止するTM
• w∉Lの時は停止しないかも知れない
• 問題が計算できる⇔deciderが存在
• deciderが存在しないがrecognizerなら存在する問題もある（両方存在しない問題もある）
10
21
半決定可能/決定可能な言語の定義
„定義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を受理するため．．．
参考書によっては，以下のように呼ぶことも．．．
1帰納的可算(RE: recursively enumerable)
2帰納的(recursive)
22
言語Lが半決定可能/決定可能であることの証明法
„与えられた言語Lが半決定可能であることを証明したい
¾Lのrecognizerまたはdeciderを一つ構成する
„Lが決定可能であることを証明したい
¾Lのdeciderを一つ構成する
„他の証明方法
¾既知の（半）決定可能な言語に帰着する（帰着は 後に学ぶ）
¾既知の（半）決定可能な言語に帰着する（帰着は，後に学ぶ）
11
23
決定可能な言語の例
問1.2:
a) 有限長文字列の有限集合はどれも決定可能か？
b) 正則言語はどれも決定可能か？
24
TMの簡略記述
„TMの形式的記述（形式レベル記述と呼ぶ）は煩雑
¾全状態，状態遷移関数を含む7項組M = (Q, ∑, Γ, δ, q0 , qaccept , qreject)全て
を記述する もしくは 相当する状態遷移図を与える必要がある
を記述する，もしくは，相当する状態遷移図を与える必要がある
„労力軽減のためTMを簡略記述する（抽象レベル記述と呼ぶ）
¾ヘッドの移動，テープに書き込む記号の種類，手順を自然語で記述（状態，状
態遷移などは与えなくて良い）
„言語Lが半決定可能（または決定可能）であることを証明するには，L
„言語Lが半決定可能（または決定可能）であることを証明するには
L
のrecognizer（またはdecider）を抽象レベルで構成する
¾注意
• 抽象レベルで記述したTMから，等価な形式レベルのTMが構成できることが必要
• Deciderの場合は，どんな入力に対しても停止することが必要
12
25
TMの抽象レベル記述例
„例1.2:
L = {0 2 | n ≥ 0} を受理するTM Mを構成せよ．
n
（抽象レベル記述）
Mは入力wを入力すると以下のように動作する．
基本アイデア
1回のループで0の個数
を半分にする．最後に一
つだけ0が残れば受理．
※アルゴリズムはこれ以
ゴ ズ
外に色々考えられる！
(ステップ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) {0n10n | n ≥ 0 } （2006年テスト問題）
13
27
一般の判定問題をTMで扱う方法
扱いたい問題を表す言語を定義Æ言語への所属判定としてTMで扱うことができる．
(1) 入力が文字列であるような問題
素数判定問題：L={全ての素数の集合}
文法チェック問題：L={正しい文法で書かれたJavaプログラムの集合}
(2) 入力が任意のオブジェクトであるような問題Æ オブジェクトを2進列に符号化
9プログラムの停止性判定問題
¾任意のプログラムコードは2進数の列で符号化できる．
¾L={任意の入力で停止するようなプログラムの2進列の集合}とすれば，言語になる．
9グラフがオイラー閉路（全ての辺が一筆書きできる）を持つか
¾行列やグラフを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
(
)で与えられ 頂点の集合は { 1,v2,...,vn},
} 辺の集合はE={e
辺の集合は { 1,...,em}
¾ 無向グラフGの符号を〈G〉と表記する．
¾ 図のグラフは例えば〈G〉 =(1#2#3#4)((1#2)(1#3)(2#3)(3#4))
のように符号化できる．
2
V
E
1
4
3
¾ 次のTMを構成する．ただし，Σ={(, ), # , 1, 2, 3, 4}, Γ=Σ ∪{1’, 2’, 3’, 4’, $, □}
1. Gの最初の頂点をマークする（頂点“1”を“1’”に書き換える）．
最初
点を
クす （ 点“ を“ ”に書き換え ）
2. マークされた頂点がこれ以上増えなくなるまで3. を繰り返す
3.
Gの各頂点に対し，マークされた頂点からの辺があるとき，その頂点をマークする
4. 全ての頂点をスキャンし，全てマークされていたらaccept，そうでなければreject
¾ 上記のTMはこの問題のdeciderになっていることは明らか．∴決定可能 □
14
29
練習問題
問1.5: 例1.3の判定問題を表す言語を定義せよ．
30
記号の用法
„文字（記号）
¾0, 1, a, b, X, Yなどで表記
¾文字変数は，x, yなどで表記
„アルファベット（文字の有限集合）
¾Σ と表記．例） Σ={0,1}, Σ={a, b, c}など
„文字列（語）
¾例）0010, aabc, 0k1k, vvR
¾入力文字列は慣用的にw と表記
„空列
¾ε と表記．例）任意の文字列wに対して，w0=ε
„空集合
¾∅と表記（εとは異なるので間違えないように！）
„言語（文字列の集合）
慣例的な用法
a,b,... 文字
q,r,... 状態
x,y,... 文字変数
w ... (入力)文字列
i,j,k,l,m,n ... 整数
A,B,... 集合
M ... 機械
L ... 言語
〈M〉 ... 機械Mの符号
（＝プログラムコード）
¾L と表記．例） L={0n1n | n≥0}={ε, 01, 0011, 000111, ...}
„オブジェクト（グラフなど）Oを符号化した文字列（符号化法は固定）
¾〈O〉と表記．
15
31
まとめ
„チューリング機械（TM）とは
¾形式的な定義
¾状態遷移図
¾様相（configuration）
¾TMの記述法（形式レベル記述と抽象レベル記述）
¾半決定可能な言語と，決定可能な言語
¾TMが扱う問題は判定問題
• 言語への所属判定⇔一般の判定問題
„Homework（次回講義時に提出）
¾問1.1～1.5
16