Document

停止性問題
2011/6/13
チューリング機械
• 「計算可能」の概念化
• チャーチ・チューリングのテーゼ
• 機械的に計算できることは（無限の時間が与
えられれば）すべてチューリング機械で計算
できる
万能チューリングマシン
• 任意のチューリングマシンをエミュレートでき
るチューリングマシン
• 2本のテープを入力とする
1本はTMの表現
1本はそのTMに対する入力
• プログラミングの概念に相当
計算可能性
• 任意のチューリングマシンとその入力が停止す
るかどうかを判定できるチューリングマシンを構
成できるか？
• 任意のチューリングマシンをX、その入力をYとす
る
• XとYを入力として、X(Y)が停止するならyes、X(Y)
が停止しないならnoを出力する機械Hが構成可
能か？
背理法による証明
• H(X,Y)が判定可能なら、H(X,X)も判定可能• 上記のようなHが構成できたとすると、次のよ
うなWを構成できる。
H(X,X)→YESならW（X)は止まらない
H（X,X)->NOならW（X)は停止する
• W(W)が停止したとすると、Wの定義より
H(W,W)=NO。Hの定義より H(W,W)=NOとなる
のはW(W)が停止しないときのみなので、矛
盾。
• W(W)が停止しないとすると、Wの定義より
H(W,W)=YES。Hの定義より、H(W,W)=YESとな
るのはW(W)が停止するときのみなので、矛
盾。
（wikipedia)
対角線論法
• Cantorが実数の個数に対する考察を行うた
めに使う
実数と整数は両方とも無限個あるが、どちらが
多いのか？（無限のランク付け）
濃度 ℵ
• 連続体仮説
（例）実数の連続性
1
2
3
4
5
6
7
8
9
1
4
4
2
6
4
8
9
0
3
2
5
6
7
8
9
0
3
5
6
3
7
3
5
5
4
3
7
9
0
4
4
6
3
2
7
5
3
4
2
5
1
2
6
4
3
7
6
5
3
5
3
4
4
6
3
3
6
4
1
7
5
0
4
3
2
7
8
9
0
• 任意のプログラムはそのまま自然数とみなす
ことができる
（ゲーデル化）
Printf(“hello world\n”)
1380813917884613958130139
• プログラムへの入力も自然数とみなすことが
できる
7971985719134
• あらゆるプログラムとその入力は
自然数Nx自然数Nの行列で表現可能
• 対角線(A(A))に注目する
（プログラム的には、自分自身を入力とするプロ
グラム）
• 対角線論法により￢A(A)なるプログラムMは
存在しえない
• しかしHが構成できるならMが構成できてしま
う
• Hは構成できない
直観的解釈
• プログラムはたかだか自然数と同じ個数しか
つくることはできない
• 自然数以上の問題を扱うことはできない
解決不能な問題が存在する
不完全性原理
• どんな定理導出もたかだか自然数個しか構
成できない
• その体系内では導出不能な定理が存在する
• 証明不可能な真理
計算の困難性
• 計算不可能
• クラスNP 非決定性TMで多項式時間で計算
可能
• クラスP 決定性TMで多項式時間で計算可能
参考文献
• プログラミングによる計算可能性理論
サイエンス社
• ゲーデル・エッシャー・バッハ
白泉社
• 数学は楽しい
日経サイエンス別冊

Download Report