4. 決定不能な問題 決定不能な問題

1
4. 決定不能な問題
2
決定不能な問題
„決定不能＝決定可能でない
Type1: 半決定可能であるが，決定可能でない
T
Type2:
2 半決定可能でない
•もし，この問題が決定可能だった
なら ソフトウ アのテストに非常に
なら，ソフトウェアのテストに非常に
有用である．
•残念ながらそのようなTMは構成
„Type1の例
できないことが証明できる．
¾ヒルベルトの第１０問題，ポストの対応問題（次頁参照）
¾TMの停止性問題「入力wに対しTM Mは停止するか」
¾TMの受理判定問題「TM Mは入力wを受理するか」
入力
•TM M
•Mへの入力w
„Type2の例
Yes
wに対し
に対し
Mは停止するか？
No
こんなアルゴリズム(decider)作れますか，という問題
¾TMの等価性判定問題「2つのTM M1, M2が受理する言語は等しいか」
¾「TM Mはどの文字列も受理しないか」
1
ポストの対応問題
PCP: Post’s Correspondence Problem
3
„文字列の対のリスト（要素数は有限個）が与えられる．
⎧⎡ b ⎤ ⎡ a ⎤ ⎡ ca ⎤ ⎡ abc ⎤ ⎫
⎨⎢ ⎥, ⎢ ⎥, ⎢ ⎥, ⎢
⎥⎬
⎩⎣ ca ⎦ ⎣ ab ⎦ ⎣ a ⎦ ⎣ c ⎦ ⎭
„PCPは，「リストの中の要素を任意の順序で並べて（同じ要素を何回使っても
良い）上下とも同じ文字列にできるか」という問題．上記の例は次の解を持つ．
a b c a a a b c
a b c a a a b c
„一般に，以下のようにk個の対のリストが与えられた時に， ti1 ti2 ...til = bi1 bi2 ...bil
となる自然数の列i1, …, ilが存在するか，という問題
⎧⎡ t ⎤ ⎡ t ⎤ ⎡ t ⎤ ⎫
P = ⎨⎢ 1 ⎥ ,⎢ 2 ⎥ ,...,⎢ k ⎥ ⎬
⎩⎣ b1 ⎦ ⎣ b2 ⎦ ⎣ bk ⎦ ⎭
¾一見簡単そうだが決定不能．．．
4
決定不能な問題（Type1）の証明
„TMの受理判定問題「TM Mは入力wを受理するか」が決定不能で
あることを証明したい．対応する言語は以下の通り
LTM={〈M,w〉 | ΤΜ Μ はwを受理する}
証明の方針
¾LTMを決定するTM（decider）は存在しないことが言えればよい
¾このことを，対角線論法を使って証明する
2
5
対角線論法
„1891年Georg Cantorにより導入された背理法に基づいた証明手法
¾例えば，実数の集合などが非可算であることを証明するのに使用
„集合が可算：数え上げられる（自然数集合と1対1対応関係持つ）
„集合が非可算：数え上げることができない
6
無限集合と濃度
„目的：複数の無限集合間で，要素の多さ（濃度と呼ぶ）を比較したい
„定義4.1: 集合A, BとAの元からBの元への写像f を考える
¾a ≠ aa’のとき
のとき，常にf(a)
常にf(a) ≠ f(a
f(a’)なら
)なら，ff は単射(one-to-one)と呼ぶ
は単射(one to one)と呼ぶ
¾b∈Bのとき，常にf(a)=bとなるa∈Aが存在するなら，f は全射(onto)と呼ぶ
¾上記の2つの条件がともに満たされるとき，f を全単射(correspondence)と呼ぶ
A，B間に全単射写像f: A→Bが存在するとき，AとBの濃度(size)は等しいと言う
単射の例（全射ではない）
全射の例（単射ではない）
„例4.1: 自然数の集合Nと偶数の集合Eの濃度は等しい．
¾（証明）NからEへの全単射写像 f(n)=2n が存在する．□
„定義4.2: 任意の集合Aについて，Aが有限あるいはNと等しい濃度を持つなら，Aは
可算(countable)であると言う．そうでない場合，非可算(uncountable)と言う
3
7
定理4.1: 実数の集合Rは非可算である
（証明）
„NとRの間に全単射写像fが存在（1対1対応が存在）すると仮定する．
„f の例を以下に示す（全単射であればなんでも良い）．
例を
に す（全単射 あればなん も良 ）
„実数xを次のように構成する．
¾xの小数点以下の第n桁目の値を，f(n)のn桁目の値と異なるように選ぶ．
n∈N
1
2
3
4
…
f(n) ∈ R
3.14159…
5.55555…
0 12345
0.12345…
0.50000…
…
x=0.4641…
無限集合の対角成分（i番
目の要素のi番目の成分）
を取り出して組み合わせる
ことで，どの要素にも一致
とで，どの要素にも 致
しないものを作り出す方法
を「対角線論法」と呼ぶ．
このようにして構成したxは，どのようなnに対してもx ≠ f(n)となる．
従って，実数xに対応する自然数は存在しないことになり，仮定に矛盾する．
以上より，Rは非可算であることが証明された．□
8
定理4.2: 全てのTMの集合は可算である
（証明）
„TM Mを2進符号化する
¾「TMの符号化（第3回資料，p.13-14）」で述べた方法で〈
¾「TMの符号化（第3回資料
p 13 14）」で述べた方法で〈M〉を求める
¾〈M〉を構成する{a, q, d, 0, 1, “,”, “(”,“)”}の各記号を2進数で符号化
“a”: 001, “q”: 010, “d”: 011, “0”: 000, “1”: 111, “,”: 100, “(’’: 101, “)”: 110
¾全てのTMは2進列（すなわち，10進数で表記すると，自然数）で表せる．
„有効なTMの符号の集合を昇順に並べる
¾全ての（有効な）TMの符号を，対応する10進数が小さい順に並べると，TMのリスト
{〈M1〉, 〈M2〉, 〈M3〉, …}が得られる．
¾以上により 自然数の要素とTMの集合との1対1の対応（全単射写像）が得られた
¾以上により，自然数の要素とTMの集合との1対1の対応（全単射写像）が得られた．
¾∴全てのTMの集合は可算である．□
• 任意の2進列（任意の自然数）をTMの符号とみなす方法もある．
¾この場合，有効でないTMの符号は，何も受理しないTM M（すなわち，L(M)=∅）の符
号と考える．
4
定理4.3: 言語LTM={〈M,w〉 | ΤΜ Μはwを受理
する}は決定不能である
9
„基本方針：対角線論法で証明したい．
¾全てのTMのリストM1, M2, … を対象に，各TMの符号を入力として動作させた時の受理
状況（例）を以下の表で表す
状況（例）を以下の表で表す．
¾リストのどのTMとも異なる動作を行うTMを，対角線論法に基いて構成し矛盾を導く！
空白の部分はrejectもしくは停止しない
〈M1〉
M1
accept
M2
accept
p
〈M2〉
〈M3〉
accept
p
accept
p
〈M4〉
M1
accept
…
accept
accept
…
〈M3〉
…
〈M4〉
…
reject
j
accept
M3
reject
M4
accept
…
〈M2〉
reject
M2
accept
p
M3
M4
〈M1〉
…
…
…
この様な動作を行うTMは
M1, M2, …のどのTMとも一致
しない（対角線要素が異なる）
対角線要素に着目し，どの
要素とも異なる動作をする
TMを構成する！
10
定理4.3の証明
(1) LTMが決定可能，すなわち，LTMのdeciderであるTM Hが存在すると仮定する．
¾H(〈M,w〉) =
accept (Mがwを受理する時)
reject (Mがwを受理しない時)
•前頁右側の表の動作を
行うTMとしてDを構成する．
(2) 〈M〉 を入力として次のように動作するTM Dを構成する．
¾ 〈M〉から〈M, 〈M〉〉注をつくり，それを入力としてΗを模倣する．
¾DはHの判定結果を逆（HがacceptならDはreject）に報告する．
¾Hを使って以下のようにDを構成可能
Dは〈M〉を受け取り，
〈M, 〈M〉〉を構成
〈M〉
〈M, 〈M〉〉は〈M, M〉
と同じと思って良い
注
D
〈M, 〈M〉〉
DはHの判定を
逆に出力する
reject
accept
H
reject
accept
5
問い：Dに〈D〉 を入力し
て動作させた時に，どう
いう場合にacceptとなり，
どういう場合にrejectとな
るかを記述せよ
定理4.3の証明（つづき）
11
(3) Dを入力〈D〉 で動作させると以下のようになる．
¾D(〈D〉) =
accept (Dが〈D〉を受理しないとき)
reject (Dが〈D〉を受理するとき)
D
〈D〉
reject
〈D, 〈D〉〉
accept
H
reject
accept
この状況は矛盾しており，仮定が間違っていたことになる．
以上より，LTMは決定可能でないことが証明された．□
Hはdeciderなので，どん
な入力に対してもaccept
かrejectかを答える
証明のレビュー
以下，全てのTMのリストをM1,M2, …で表す．
〈M1〉
M1
accept
M2
accept
〈M2〉
M4
…
(1)
〈M4〉
accept
accept
accept
空白の部分は
rejectもしくは
停止しない
…
accept
〈M1〉
〈M2〉
〈M3〉
〈M4〉
accept
reject
accept
reject
M2
accept
accept
accept
accept
M3
reject
reject
reject
reject
M4
accept
accept
reject
reject
…
D
...
…
Miに〈Mj〉を入力したときの出力（例）
M1
〈M1〉
〈M2〉
〈M3〉
〈M4〉
M1
accept
reject
accept
reject
M2
accept
accept
accept
accept
M3
reject
reject
reject
reject
M4
accept
accept
reject
reject
…
accept
M3
accept
〈M3〉
…
12
…
…
…
(2) Hに〈Mi, 〈Mj〉〉を入力したときの出力
… 〈D〉 …
•定理4.1の証明のときと同じよ
うに，矛盾を導くことを目的に，
対角線論法に基づきDを構成
している．
…
…
reject
reject
accept
accept
???
(3) Dに〈Μj〉を入力したときの出力ÆΜjに〈Μj〉を入力した時の出力と異なるように決めている
ÆDの出力は，他のどのΤΜの出力（対角線成分の出力が違うので）とも一致しない
6
13
練習問題
„問4.1: 定理4.3の証明になぜ対角線論法が使えるのか答えよ．
¾ヒント：付録の定理4.5を参照せよ
„問4.2: 言語 LTM が半決定可能でないことを証明せよ（ヒント：過去に
出てきた定理を用いて良い）．
14
まとめ
„決定不能な問題
¾deciderが構成できないような問題（言語）を，決定不能と呼ぶ
が構成できないような問題（言語）を，決定不能と呼ぶ
¾タイプが2種類存在（半決定可能だが決定可能でない，半決定可能でない）
„対角線論法
¾実数の集合Rなどが非可算であることの証明に使う
¾全ての言語の集合が非可算であることを証明できる（付録参照）
„言語LTM （TMの受理判定問題）が決定不能であることの証明
¾LTMが決定可能と仮定すると矛盾する（対角線論法で証明）
„Homework
¾問4.1～4.2
7
15
付録
„定理4.4: 「半決定可能でない言語が存在する」の証明
¾全てのTMの集合より，全ての言語の集合の方が「多い」ことを証明することに
よって 対応するd id /
よって，対応するdecider/recognizerが存在しない（決定可能/半決定可能でな
i が存在しない（決定可能/半決定可能でな
い）言語が存在することを証明する
全てのTM
の集合
全ての言語
の集合
16
定理4.4: 半決定可能でない言語が存在する
（証明の手順）
(1) 全てのTMの集合が可算であることを示す．Æ 定理4.2（証明済）
(2) 全ての言語の集合が非可算であることを示す．Æ 定理4.5
(3) (1), (2)より，TMの集合と言語の集合は1対1対応を持たないため，
対応するTMを持たない（すなわち，半決定可能でない）言語が存在
することが言える．
8
17
定理4.5: 全ての言語の集合は非可算である
（証明手順）
(1) 全ての無限2進列の集合B は非可算であることを証明する．
列の長さ=無限
無限2進列の集合B
101000001000100100101010101…
110101010100101010101000001…
010101010000101000101010001…
000010100100100101001010100…
1111101010101011110101011010…
…
要素数=無限
(2) 全ての言語の集合（Lと表記する）がB と同じ濃度を持つことを証明する．
（注）各言語は文字列の集合なので，全ての言語の集合Lは，集合の集合となる．
L とΣ*（全ての文字列を含む言語）を混同しないこと！ Σ*は Lの要素である．
他のあらゆる言語はLの要素である．
18
「Bは非可算である」の証明
（証明）自然数の集合Nと無限2進列の集合Bの間に全単射写像fが存在（1対1対応
が存在）すると仮定する．f の例を以下の表に示す．
„表の要素から ある無限2進列xを次のように構成する．
„表の要素から，ある無限2進列
を次のように構成する
¾xの上位から第n桁目の値を，f(n)のn桁目の値と異なるように選ぶ．
n∈N
1
2
3
4
5
6
…
f(n) ∈ B
101100100…
010010101…
001010111…
110101100
110101100…
001101010…
100010001…
…
x=000011…
このようにして構成したxは，どのようなnに対しても
x ≠ f(n)となる．
従って，この無限2進列xに対応する自然数は存
在しないことになり，仮定に矛盾する．
以上より， B は非可算であることが証明された．□
9
19
定理4.5 「Lは非可算である」の証明
言語毎に固有に定まる無限長記号列
（証明）
„Σ={0,1}とする．
„任意の言語L ∈ Lに対し，Lの特徴系列χ
に対し Lの特徴系列 Lを次のように構成できる．
を次のように構成できる
¾ χLのi番目の文字＝ 1 言語Σ*のi番目の要素が言語Lに含まれる時
0 そうでない時
Σ*={ ε,
0,
L={
0,
χ L=
0
1
1,
0
00, 01, 10, 11,
000, 001, …}
00, 01,
000, 001, …}
1
1
0
0
1
1
…
¾上記の特徴系列の構成法は，LからBへの全単射写像（1対1対応）になってい
る．よって，p. 17の(2)が証明された．
„以上(1), (2)より，全ての言語の集合Lは非可算である．□
10