（勉強中）パラドックスがいっぱい
続き
前
uso-800-plus-alpha.hatenablog.com
K("x") < n
というのは、「n桁未満のプログラムで、出力が"x"になるものが存在する」ということを意味していて（なので論理式）、
n ≦ K("x")
の場合だと、「n桁未満のプログラムに、出力が"x"になるものが存在しない」ということを意味する（なので論理式）のだそうです。
※前の記事で適当な用語法を使ったせいで、原文とは記号が微妙に違います。そのせいで間違ってたらごめんなさい。
で、
理論TをPAの拡大（とかの例の条件を満たす）理論としたときに、
或るbが存在して、自然数 a について、T ⊬ b ≦ K(a) である。
を、Chaitinの不完全性定理と呼びます。
前の記事で、K(x)の値は頭打ちにはならないと言っておいてこの仕打ちです。
証明は、定理生成プログラムを準備するという方法で行われます。
ここも『不完全性定理』を見ながらやってみます。
Ruby上で、証明を簡単な順から並べるプログラムを組んだとします。
f(0) = 0x303d30 （0=0※公理のため1行で証明終了）
f(1) = 0x313d31 （1=1※上に同じ）
･･･
で、「証明の16進コード n が与えられたとき、その証明の結論がb ≦ K(a) 型の定理だったかどうか判定する述語」が定義できたとして、それを b_Ka?(n) と書くことにします。
def g(n)
b_ka?(f(n)) ? a : g(n+1)
end
$><<g(1)
※いままでの用語法だと、ここで16進数表記→文字列表記に変換すべきだが、端折る。
bを大幅に圧縮できる数として選んでやると、全体のプログラムの桁数をb未満に抑えることが可能となる。このとき、b桁未満のプログラムからaが出力されているため、
K(a) ＜ b
であり、また、b_Ka?(n)がtrueを返しているので、fのプログラムにバグが無ければ、
b ≦ K(a)
である。
～完～
これが「ベリーのパラドックスっぽいよね」という話があるそうです。
b ≦ K(a) は、「aがb文字未満で定義できない」と言っているように見えます。それに基づいて、K(a) ＜ b、つまり「aがb文字未満で定義できる」ことになってしまうというノリは、「"30文字未満で定義できない最小の自然数"って"30文字未満で定義できてる"よね」と比較して、確かにそれっぽいです。
ここから、抜き打ちテストのパラドックスに話を飛ばします。
上で書き忘れていましたが、理論Tには、無矛盾であるという前提があります。
その上で、T ⊬ b ≦ K(a) です。
この b について、b桁以下となるプログラムの数はいくつでしょうか？
前の記事の感じでは、個あることになります。
同じく前の記事の感じでは、の中に、どう頑張っても b ≦ K(x) となってしまう x が存在します。
そのため、b ≦ K(x) となる x の数 m は、の範囲に含まれることが分かります。
まず、m=1としてみましょう。
この場合、の中の1個だけが b ≦ K(x) を満たし、残りが K(x) ＜ b を満たすということです。
実は、K(x) ＜ b を満たすときには、これを証明することが可能です。b桁までのプログラムを調べて、出力が x になるものを探せばいいという理屈のようです。
ということは、
b ≦ K(x) を満たす、証明できないはずの1個を除いて、全て K(x) ＜ b であることが証明されてしまうということになります。
つまり、消去法で b ≦ K(x) を満たす x が特定されてしまいます。
これではいけません。
したがって、であることが分かりました。
正確に言うと、
理論Tが無矛盾ならば、です。
では、m=2でしょうか？
この場合も同様に、K(x) ＜ b ではなさそうな2個を残して、すべてK(x) ＜ bであることが判明してしまいます。さらに、m=1である可能性が上記の議論で潰れているので、（1つなんだけどどちらか分からないという可能性は無く）残った2つとも b ≦ K(x) を満たすことが確定してしまいます。
これではいけません。
したがって、であることが分かりました。
正確に言うと、
理論Tが無矛盾ならば、です。
では、m=3でしょうか？
･･･
では、m=4でしょうか？
･･･
･･･
･･･
･･･
では、m=でしょうか？
おそらく、ここまでに圧縮可能なものが少なくとも一つはあったでしょう。
したがって、m=もあり得ません。
mは、1～の中のどこかにあるはずです。
しかし、そのどれでもないという結果になってしまいました。
もしも、理論Tの無矛盾性が（T内で）証明できたとしましょう。そのときには、この議論が前件抜きで成立するため、そのまま矛盾が発生します。
･･･つまり、理論Tの無矛盾性が（T内で）証明できないということです。
～完～
まず、m=1か？→違う
じゃあm=2か？→違う
じゃあ･･･
･･･
？？？
というノリが、抜き打ちテストのパラドックスの
まず、金曜か？→違う
じゃあ木曜か？→違う
じゃあ･･･
･･･
？？？
という構成と似てますね。
参考書が無く、Kritchman and Raz (2010)の"The Surprise Examination Paradox and the Second Incompleteness Theorem" を見ながら書いたので、ヤベーことを言っているかもしれませんが、誰か直すでしょ（他人事）。
参考
Kritchman and Raz, "The Surprise Examination Paradox and the Second Incompleteness Theorem" 2010年
Wikipediaの記事はリンクを見てください。
