巨大数探索スレッド13
■ このスレッドは過去ログ倉庫に格納されています
https://twitter.com/wota1969?t=1&;cn=ZmxleGlibGVfcmVjcw%3D%3D&refsrc=email&iid=7ee5dd3e1aad40d9a574c9f18d8e62a1&uid=525178774&nid=244+272699405 俺的文明レベルの定義
文明のレベルはビジービーバー関数の値をどこまで求められるかで測られる。
現在の人類の文明レベルは4 囲碁、チェス、将棋のプログラムで一気にトップに出た Google に、
絶大なコンピュターパワーでビジービーバー関数の計算にチャレンジしてほしい GIMPSみたいに分散コンピューティングしたいけれどあまりにも知名度が 名前がよくない
いっそ社畜関数って名前にしてしまえばもっと共感を呼ぶ 計算量がそのまんまビジービーバー関数レベルで増えていってやばい。
指数関数レベルの増え方とは次元が違う・・・と思ったけどほんとにそうだろうだろうか？ 停止するプログラムをすべて最後まで走らせてその中で最大の値を求める。
これは本当に最後まで走らせる必要があるわけではない、
どこまで計算効率を上げられるか
停止しないプログラムは停止しないという判定をしなければならない。
限定的に停止性を判定するアルゴリズムは存在するものの、それをどこまで簡単にできるか？
またそのプログラムを開発するプログラムはもっと複雑になるのではないか？
停止性を判定するプログラムはオラクルで与えられてもいい、つまり適当に作ったプログラムが
たまたまそうなっていたとしてもいい、ではそれがほんとうに停止性を判定するプログラムであると
判定するプログラムは？
停止性を判定するプログラムであると判定するプログラムであると判定するプログラムは？
これもうわかんねえな >>13
普通にゲーデルの不完全性定理を停止問題として言い換えられるのぐらい知ってて言ってるよね？。 BB(100)とかは無理だろうけど、BB(5)とかBB(6)くらいなら、
Googleが頑張ればそのうちなんとか、とか思わないでもない 実際に求める必要なんてないと思うが
グラハム数だって計算しようなんてヤツはいない >>14あくまで限定的な停止性判定のアルゴリズムの話なので。
たとえば4状態のプログラムは有限個しか存在しないので、究極最初からプログラムの中に
それぞれの入力されたプログラムに対する答えを用意しとけば4状態の停止性を判定する
プログラムとなります。
と書いて思ったけどこんなのでもアルゴリズムと言っていいのか？ プログラムとは言えるけど 計算可能レベルの追究が結果的にビジービーバー関数の値を求めることにもなるだろう。
逆も然りだが、こちらからはけっこう難解 実際に求めると言うのは、当然10進数で求めるという意味ではなくて、
優勝マシンを決定すること
その一般的なアルゴリズムはないけど、小さいnに対しては決定できても
おかしくはない 巨大数ベイクオフ大会もある意味BB(512)の値を追求する大会ですし 前スレでビジービーバー関数の全域性うんぬん言ってたやつに致命的な間違いを見つけた。
ω矛盾の定義がおかしい。∃n∈(自然数)(Q(n))が証明可能なのに
Q(0),Q(1),Q(2),...がいずれも証明不能であることをω矛盾の定義といってたが、
これだとペアノ算術に例えば定数記号aを加えただけの拡張でも、
a = a から ∃n (a = n)が導出できる一方で、a = 0,a = 1,a = 2,... のいずれも証明不能で、
ω矛盾になる。しかし、これにa = 0という仮定を加えても無矛盾だから、
超準モデルになるとは限らない。
間違いの源はおそらく日本語版wikipediaだ。
"ω矛盾とは、自然数 n によって定まる論理式 Q(n) が存在して、次を満たすことをいう。
Q(0), Q(1), Q(2), …が全て証明可能であるが、「∃n： ¬Q(n) 」も証明可能である"
この記述は正しい。問題があるのはその下の、
"公理系が無矛盾であれば、対偶を取る事により、ω矛盾の概念が次と同値である事を示せる：
「∃n： Q(n) 」が証明可能であるが、Q(0), Q(1), Q(2), … のいずれも証明可能ではない。"
というところだ。最初の記述は「Q(0),Q(1),Q(2),...が証明可能で、かつ∃n(¬Q(n))も証明可能」
と言い換えられる。すると、実はAならばBの形になってないから、そもそも"対偶を取る"のは変だ。
英語版wikipediaには下の記述に該当する文は無い。
同値でないことも簡単に確認できる。ペアノ算術に定数記号aを加えただけの拡張は、
∃n(a = n)が証明可能で、a = 0, a = 1, ...が証明不能なことから下の記述を満たすが、
∃n(¬(a ≠ n))が証明可能な一方、a ≠ 0, a ≠ 1, ...は証明不能だから、上の記述を満たさない。
よって2つの記述は同値でない。
だから、前スレのあの証明では、「ビジービーバー関数の出力が超準的自然数になる」ことは
証明できていない、と言える。
あー、すっきりした まぁでも、「ビジービーバー関数の出力が超準的自然数になる」、すなわち
BB(x)をビジービーバー関数として、
「十分大きな自然数Mについて、0 < BB(M), 1 < BB(M), 2 < BB(M), ...が証明可能」
は証明できてないけど、もっと弱い主張である※ならば簡単に証明できる。
(∀n(n < BB(M))と、0 < BB(M), 1 < BB(M), ...は異なる。∀n (n < BB(M))からは、
例えばBB(M) + 1 < BB(M) を導出できるので明らかに矛盾)
※: 任意の無矛盾かつ帰納的公理化可能な公理について、ある自然数Mが存在して、
任意のn ∈ {0,1,2,...}について公理に n < BB(M) という式を加えてもなお無矛盾
やや分かりにくいけど、公理に0 < BB(M)とか1 < BB(M)とか 2 < BB(M)をいくら加えても
そこから矛盾が導出できない、ということ。ビジービーバー関数を扱える公理じゃないと
いけないので、多分自然数論を含むだろう。 証明: 背理法による。どんなに大きな自然数Mに対しても、n < BB(M)を仮定すると矛盾が
導出できるような n ∈ {0,1,2,...}が存在すると仮定する。
公理が帰納的公理化可能なので、以下のような計算機械を構成すれば、必ず停止する
k = 0 とする
親プロセス:
(1).子プロセスに k < BB(M)を与えて起動する
(2).子プロセスが1つでも停止したら(3)へ
そうでなければ k を 1 増やして(1)へ戻る
子プロセス:
k < BB(M)が与えられたら公理 + (k < BB(M))から
矛盾の導出を試みて、矛盾を導出したらkを出力して停止
また、親プロセスが停止したら停止
すべてのプロセスは並行して行われる
この計算機械の出力する値を N とすると、N < BB(M)から矛盾を導出したので
N ≧ BB(M)を導出でき、状態数M以下のチューリングマシンをエミュレートして
N個を超える1を出力した時点でそのチューリングマシンは停止しないと判定できる。
どんなに大きな自然数Mに対してもこのことが言えるので、
任意の停止性問題を解ける計算機械が構成できることになり矛盾する。
よって背理法より※が示された。 ※からは面白いことが分かる。
例えば、いかに大きなn∈{0,1,2,...}についてもn < BB(M)の仮定と矛盾しないということは
ある程度大きなMについてBB(M)に意味のある上限を導出できないことを意味する。
上限 m∈{0,1,2,...} が導出できるなら、m < BB(M)の仮定を加えると矛盾し、※に反するから。
(ここでいう意味のない上限とは、BB(M) < BB(M) + 1など)
ある程度大きなというのがどれくらいかは公理によるが、例えばZFCで100とすると
BB(100)の上限がふぃっしゅ数ver6ぐらい、とか、H(ψ(Ω_ω))である、といった
何かしら計算可能なもので表せると証明されることはありえない、ということになる。
あとは、"公理が無矛盾 ⇒ 公理 + (n < BB(M)) が無矛盾"は示した通りだが
逆は明らかなので公理と公理 + (n < BB(M))は無矛盾性同値でもある。
なんだか、まるでBB(M)は連続体濃度みたいな感じがする。
連続体濃度cも、ZFC + (アレフ1 < c) とか ZFC + (アレフ2 < c),...にしたって無矛盾だし、
cは存在するし一定の濃度でもあるはずだけど、可算無限との間にいくつの濃度の異なる集合が
あるのか決まらない、といったような。
何をもって一意に定まるとするのかは、もはや哲学の問題だね。 いまだにビジービーバーみたいな小さな関数で思考が止まってるのか グラハム数が指数の塔で表現出来なくても
ちゃんと大きさが見積もれる 前スレの「フワフワした感じがすっきりしないんじゃないか？」を「大きさを見積もることができない」
と言っていると勘違いされた可能性はどうだろう >>26
「どんなに大きな自然数Mに対しても、n < BB(M)を仮定すると矛盾が
導出できるような n ∈ {0,1,2,...}が存在する」
としたら、「1をn個出力するまでチューリングマシンを走らせる」とするだけで
停止性問題が解決してしまうので、そういうnが存在しないということが
停止性問題と同値であることは自明 >>31
小さな数しか作れないものは否定されてもしょうがない 無限の無限乗の無限乗の無限乗の無限乗の・・・・・（これが無限に続く）
ってどのくらい大きいの？ >>37
「無限」じゃないですかね
元の無限とは異なるんだろうけど 無限について考えていてふと思ったんだけど、仮に「ゼロで割る」という操作が「できる」と仮定したら、何かおもしろいことが起きるか、
例えば、ｕ×０＝１という関係が成り立つｕを仮定して、これをあたかも虚数単位のようにして数を拡張すること、
具体的には、実数集合Ｒに対して、このｕを使って集合Ｕ＝{ａ＋ｂｕ|ａ、ｂ∈Ｒ}を定義することができるが、このような集合Ｕに、果たして数学的な意義はあるのか
それともまったく無意味なのか
こんなことを思い付いて研究してる数学者が、じつは既に居るんじゃないかって気がしてるんですが、その辺りどうなんでしょうか？ とりあえずルベーグ測度を勉強すれば幸せになれると思う >>39
とりあえず、ある程度までは自力で考えてみよう 1/0と0/0を割と自然に追加したのが車輪
でも
(1/0)*0
は1じゃなく0/0になっちゃうが 結局、巨大数を求めるにあたってどこまで奇妙な性質をもつことを許容できるか
という哲学の問題なのかな。
いったんここでは自然数論のモデルに属しうるものはすべて自然数と呼ぶことに
して、以下の4つに分類しよう。特に断りがない場合、証明可能とは古典論理の
もとで証明可能であることを意味する。
(1)存在を直観主義論理のもとでも証明可能な自然数
例: ふぃっしゅ数ver6など、計算可能な手段で求められるもの
(2)存在を証明可能だが、直観主義論理のもとでは証明不能な自然数
例: ある程度大きな入力に対するビジービーバー関数やラヨ関数、
その他の計算不能関数の出力？
(2)の数は、さっきの※みたいな、任意のn∈{0,1,2,...}についてnより大きい
としても無矛盾、といったやや奇妙な性質をもつようになると思われる。
続く (3)存在を仮定するとω矛盾であることが導ける、したがって自然数論からは
おそらく存在が証明不能であるが、無矛盾性は強くしない自然数
おそらく、としたのは自然数論が矛盾していれば何でも証明可能であるため。
例: 「自然数論の矛盾の導出を試みて、導出したら停止する計算機械」
が停止するまでにかかるステップ数
自然数論 + (自然数論は矛盾)という公理を採用すれば停止することを証明可能で、
自然数論が無矛盾ならば(自然数論は無矛盾)は導出できないため、
自然数論が無矛盾ならば、自然数論 + (自然数論は矛盾)もまた無矛盾
よって無矛盾性は強くなっていない。
(4)存在を仮定すると、ω矛盾になるうえ、無矛盾性も強くなるが、
矛盾はしないような自然数
集合論では、大きすぎて存在を仮定すると無矛盾性が強くなるような
濃度のことを巨大基数と呼ぶのだった。いわば、(4)は自然数論版の
巨大基数である。ただしこれについての研究はほとんど無いから、
具体例を挙げるのは難しい。
(3),(4)に属する自然数は超準数で、したがって(1),(2)に属するどの自然数よりも大きい。
(1),(2)は存在を証明できる自然数で、(3),(4)は存在しないとは証明できない自然数である。
(4)に属する自然数はおそらく(3)に属する自然数よりも大きい。 ちなみに>>39にあるような u * 0 = 1となるuについては、実数0は加法の単位元で、
実数1は乗法の単位元なので、1 + 0 = 1と分配法則から
u = u * 1 = u * (1 + 0) = u * 1 + u * 0 = u + 1
よって u = u + 1 両辺からuを引いて 0 = 1 実数の0と1は等しくないので矛盾
だからこのような u は、(1)から(4)のどれにも属さない、
存在を仮定すると矛盾が導ける数、ということになる。 あっ、そうだ。
>>39
さすがに0の逆数っていうのは先述の通り矛盾するからないけど、
どんな実数よりも大きい超実数という数の存在を仮定して色々する
超準解析っていうのがあるよ。 >>47
通常の算術が成り立たなくなることは理解しました。ありがとうございます。
スレチってこともあるのであまり深くは掘り下げないことにします。
そういえばu=u+1って式はuが可算集合濃度だと成立する式ですね。この場合は辺々uを引く操作に意味がないわけですが。 >>45
ビジービーバー関数が存在することに疑問の余地がある？ >>45
ビジービーバー関数の何が証明不可能だと言ってる？
Σ(9^9^9)が明確に定義されていて存在することは明らかだよね？ 少なくとも、存在することが証明できる数でないと探索にならないのでは？
到達不可能基数のような、巨大基数を仮定すると定義できる巨大自然数
みたいなのがあるの？
関数であればそういう物もあるような気がするけど、
単なる１個の自然数にそういうのがある？
自然数に計算可能も計算不可能も無いよね？ スレを計算可能レベルと不可能レベルに別けるのは構わないっちゃあ構わないけど、
不可能レベルだけでそんなに話題があるだろうか？ と思って前スレみてみたらそこそこあるな >>24からどうも引っかかるので整理
"ω矛盾とは、自然数 n によって定まる論理式 Q(n) が存在して、次を満たすことをいう。
Q(0), Q(1), Q(2), …が全て証明可能であるが、「∃n： ¬Q(n) 」も証明可能である"
これは正しい
"公理系が無矛盾であれば、対偶を取る事により、ω矛盾の概念が次と同値である事を示せる：
「∃n： Q(n) 」が証明可能であるが、Q(0), Q(1), Q(2), … のいずれも証明可能ではない。"
これは確かにおかしいと思う、Q(0), Q(1), Q(2), … のいずれも証明可能ではないというのは統語論的に
決定できないと言うだけで、Q(0), Q(1), Q(2), … のいずれも反証可能ということではないので スレの統一ルールはないので、計算可能でも不可能でも、自分が好きな話題を出せばいい 数年に1スレ消費するような閑散としたスレッドで、前スレは久々に1年以内に消費した
程度なんだから、話題なんてごった煮でよくて、巨大数に関することは基本的になんでもあり 公理 A に対して、※を満たすくらい十分に大きな定数 M を用意して、
A に可算無限個の式を加えた以下のような公理
A + (0 < BB(M)) + (1 < BB(M)) + (2 < BB(M)) + ...
を A* として、コンパクト性定理より A が無矛盾なら A* も無矛盾
A から ∃n (n = BB(M)) を証明可能とすると、 A のモデルはすべて
BB(M)に該当する数を含む。 一方で A* のモデルではBB(M)は必ず
超準数である。A* が A を含むから、A* のモデルは A のモデルでもあり、
したがって採用する A のモデルによってはBB(M)は超準数になる。
さらに A がω無矛盾であるとすると、 A のモデルには標準モデルもあるため、
採用する A のモデルによってはBB(M)は標準数∈{0,1,2,...}になる。
したがってBB(M)の値はモデルの選び方に依存して変わる。
f が自然数上の計算可能関数とすると、n∈{0,1,2,...}について
0 = f(n), 1 = f(n), 2 = f(n), ...のうちのいずれかは証明可能である。
証明可能な式はどんなモデルを採用しても真なので、標準数を入力したときの
計算可能関数の出力する値はモデルの選び方に依存しない。
当然、0 = BB(M), 1 = BB(M), 2 = BB(M), ...のうちのいずれも証明不能である。
これは、任意の n∈{0,1,2,...} について n < BB(M) としても無矛盾である
ことによる。(n < BB(M) ならば n ≠ BB(M)である)
さっきは暗黙的に標準モデルで考えたために(2)の具体例が(3)の具体例
よりも小さいって言ったけど、超準モデルの中にあるBB(M)だったら
(3)の具体例を超えることも十分に考えられるな。 順序数や基数は整列集合だから
○○を満たす最小
みたいなのがあるわけで
整数だと
nが○○を満たせばn-1も満たすから
そういう形で大きな数を定義するのは無理では？ >>57
公理系によってBBの値は変わらんよ
公理系で証明可能だろうが不可能だろうが
BBの値に影響無い
単に選んだ公理系に証明の能力が無いだけ 選んだ公理でマシンの動きが変わるなんて事はあり得ない BB(M)の大きさを語るのに
その大きさをまともに扱えない公理系を使うのが間違い
幼稚園児がBB(4)=14の矛盾を導けないからといって
BB(4)=14と教えれば幼稚園児にとってはBB(4)=14である
と言ってるようなもの 計算可能な関数も
公理によって値を返すかどうか証明不可能なものがあったと思うけど 公理系の強さが順序数で表されるというのは興味深い。
深く勉強してみたいものだ。 二階部分を量化して任意の部分集合は最小値をもつと言えば自然数論の超準モデルと区別できるようになる >>62
少なくともZFCにおいては、BB(4) = 13 が証明されているから、
ZFCのもとで 4 は※をみたすほど大きな数ではない。
無数にある無矛盾な公理系のうちどれを採用すべきかは数学の範囲内
じゃ答えられないし、ある公理がもつ無数のモデルのうちのどのモデル
を採用すべきかも数学の範囲内じゃ答えられない。
しかも、ビジービーバー関数の出力をすべて決定できる無矛盾な公理は必ず
帰納的公理化不能になるから、そんな公理の採用を強制されても神様にしか
扱いきれない。
数学の範囲内で答えられないなら哲学の出番になるけど、俺は哲学的議論
なんてしたくない。決着がつくことはほとんどありえないからだ。
俺はそんな哲学的議論をするより、あくまで数学の範囲内で、
そして人間が扱える公理の範囲内で、考察対象がもつ性質について
述べる方がずっと面白いと思う。 BB(M)が扱える公理系ならどの公理系を選んでも値は同じ
どの公理系を選ぶかなんて考える必要は無い
その辺はBB(4)となんら変わらない 大きい数を競うのに、
実際に値を求める必要は全くなくて、
大小を比較する手段があれば十分 ■ このスレッドは過去ログ倉庫に格納されています
