チューリングマシンに計算不可能関数が存在する証明のメモ
どんなに時間があっても、計算できない関数がUCが存在する
命題
どのチューリングマシンでも計算することが出来ないUC:{0,1}*→{0,1}が存在する
証明
UCを以下のように定義する
- 全てのa∈{0,1}*はチューリングマシン Mを表す
- Mが有限ステップで終了し1を出力するならUC(a)=0
- それ以外の場合UC(a)=1
次の式は矛盾する
M(a) = UC(a)
- M(a)=1の時、UC(a)=0
- UC(a)=1の時、M(a)=0または計算が終わらない
この証明テクニックは対角論法(diagonalization)と呼ばれる。
図が意味不明。製品版だと改善されているのか。
他
- ドラフト記載の単語綴が間違っている
diagnoalization→diagonalization
これは製品版を買うしか無いか。
