巨大数探索スレッド13
■ このスレッドは過去ログ倉庫に格納されています
well-defined自体はwell-definedな概念なの? well-defined自体がwell-definedだったら何か矛盾が起きるんだろうか?
でも自己複製するプログラムだって存在するし一概にはわからんか ゲーデルの第二不完全性定理によりwell-definedそれ自体はwell-definedではない
と言ってみる。 メタwell-definedという概念を作ろうぞw >>500
その言語による再帰的な表現の範囲内だけで健全性やら完全性やらを考えればいい
という考えだったけど、再帰の存在の証明がどんどん難しくなっていって結局>>501みたいなな感じになるのね
「より自由で強力」は取り下げてお詫びします。 誰がフォン・ノイマン宇宙の対角化と言ったのか知らないけど、ラヨ関数って構成可能宇宙の対角化
と言ったがいい気がする。
Little BigeddonでLに無数のウッディン基数を追加した世界の対角化か(適当) 新しく発見された物理現象でビジービーバーの値が計算できるようになったって。 >>507
いやフォンノイマン宇宙。
公理がなくて∈しかないから。
ウディンとか特定の基数の存在を仮定したら有り無しを問わないラヨ数より弱体化するがな 構成可能宇宙も公理はないけど。ただ1階述語論理に限定してるだけで。
というか公理があったらそのまんまモデルとして扱える。
それに可測基数以降は1階述語論理ではその性質を記述しきれないし、ウッディン基数レベルにもなってくると
高階化した程度じゃ相手にならない、ような。このへん自分もよく分かってない 特定の存在が非自明な巨大基数の存在を否定していない1階集合論のモデルとなりうる。
可測基数は含まれない。
ラヨ命名する式の中で、すくなくとも可測基数よりも強い性質を扱うことはできない。 amazonで垣間みようとしたら垣間見えませんでした 集合への入門[無限をかいま見る]
福田拓生 培風館 2012年初版
2900円+税
三部構成
第一部は集合と写像について初学者にも理解できるように解説されてある。
ラッセルのパラドクスと選択公理についても章を分けて説明されてある。
第二部は無限集合、その大きさの比べ方(つまり濃度の性質)について書かれてある。カントールの対角線論法や連続体仮説といった巨大数論で用いる概念についても記されてある。
まとめに濃度に関するありがちな疑問への簡単な回答がまとめられている。
第三部は選択公理と濃度の比較可能定理に言及している。また、ツォルンの補題、整列集合について説明がなされている。
第一部から第三部にかけて定理と例題に証明が詳しくついていて読みやすい。
特に第一部、第二部においては初学者の学習を考慮してかさらに詳しく解説してあり、問題も設けられていてその解答も記されている。
付録として、集合論の歴史、連続体仮説、選択公理とバナッハタルスキーのパラドクスについての議論、解説が再度なされている。 ただ、順序数に関する具体的な話題はほとんどないのが残念。理由はあとがきに書かれてあった。
あとがきの中で順序数に触れている集合論の良書が書かれてある。 IJK(Infinity-Jumping-Kangaroo)関数
一階述語論理でn個以内の記号で表現できるいかなるFGHの階層よりも強い最弱の一変数関数にnを代入する関数である
IJK(888)をカンガルー数と呼ぶ その+1が大きかったりすることもある
Σ(888)は計算可能な手続きでも越えられる可能性は有るかもしれないけど
Σ^888 (888)は無理だとわかる
って感じ? ちょっと意味が分からない
n文字以内の一階述語論理で順序数を定義して、その順序数を添字とするFGHにnを代入した数がIJK(n)ってことか? 恐らく頭の中で描かれたであろう事
「急増加関数がモノサシに使われるって事は急増加関数こそ最強。なんか無限がいっぱい出てくるし」
「n文字を費やして定義されたfω究極なんちゃらかんちゃら(n)より強い関数IJK(n)は絶対最強。」
「n文字のあらゆる関数ではなく急増加関数のみをターゲットにしているのでパラドックスにならない。」
「無限がいっぱい出てくる急増加関数を踏み台にしてるけど増加率で勝ってるだけなので値はちゃんと有限。やばい」
「とりあえず雛型にwikiのラヨ数の定義コピペしとこう」 最弱だからIJK(888)=0になる気がする
「強い」の定義にもよるけど 一階述語論理n文字で定義出来る最大の自然数
とほぼ同じだな
一階述語論理
強い
最弱
の定義をしないと >>533
おっしゃる通りで念のための処置
>>536
メタでない(後述)一変数関数に任意の値を入れた時、定義にω、つまり極限を使えるFGHが最も大きな値を返すのは自明でしょう
FωCK(n)をFω CK (n)にするだけで
ω εω 既存の巨大数を
遥かに凌ぐ
IJKはFGHというゲタを履いた関数で、これを1次メタと呼ぶ
f(n)の増加率を競えば必ず勝つFGHに、見掛けはf(n)でf(f(n))をぶつけるのがIJK
ではIJKというゲタを履いたLMNなる関数があるとして、これは2次メタであるか?
答えはならない
ゲタを無限に履いてやっと2次メタ足り得るが、それは有限の数ではない
よって1次メタが巨大数探索の終点に最も近い概念となります とりあえず収束列を明示しないとwell definedにならない 定義にFGHを使うのがよくわからない。順序数次第でどんなに強力な関数もとらえることができる。
というかFGH自体はただの「評価する順序数の扱い方」で強いも弱いもない これも
再帰的関数論 照井一成
http://www.kurims.kyoto-u.ac.jp/~cs/cs2011_terui.pdf ラヨ関数は公理を明らかにすべきというのが納得いかない。
すくなくとも自然数のクラスが共有できていればどこで比較する基準は明らかになるし、これはFOSTだけで可能。もっと突っ込めば、特定の値を比較するだけなら
それぞれの引数に対し十分大きな自然数までを空集合から定義すればよくてすべての自然数が共有できてなくてもいい。
それ以外の公理は、たとえばφを評価するのに公理Γが必要というのなら最初からその公理が指定されてなくてもΓ→φという式で無条件でwell definedになるはずだし、これは演繹定理と完全性から明らか。
というか「ZFCの式だけで評価できる」ってしちゃうと計算可能になるんじゃないのか 「最小の証明を書けなくても戦え数」はラヨ数と同じくらいっぽいし、書けるほうもだいたい同じじゃないかね、
証明に使う式を対角化しても>>556の理屈で結局定義文の対角化と同じだと思う >>557
書ける方は証明の長さも対角化していたか。失念していた。なら計算可能だ。 定義する部分は1階述語論理だし、1階述語論理のコンパクト性からFOL_{論理式}は、無限集合であっても実際にはせいぜい有限部分しか使われない
ということにならないか? あぁいや、定義する部分も2階述語論理か。となるとF7より大きくBIG FOOTより小さいってところか? >>561 ふぃっしゅ数バージョン7です。
こいし数というものも見てみたけどあれはω階の集合論を対角化した関数を2回適用した感じの強さでBIG FOOTよりは小さい?
2階以降の推論規則をどうするのか、PAのようなちゃんと整合的に機能するかどうかを知りようがない
システムをただで使っていいのかとか、疑問や要望がある
まとめると有限の立場に還元できるのか?
有限の立場ってなんだよ ふいっしゅ数みたいなサラダ
大きさの指標しなくていいよ 他人に望むばかりでいざなにかでてきたらサラダ言って、自分からはなにも生み出さないってのはさ サラダはサラダでもフィッシュ数は見て楽しい食べて美味しいサラダだよ フィッシュさんも最初はそれほど知識なかったんだよね?
俺も追いつきたい 計算可能な巨大数論を学びながら数学的手法になれつつ計算不可能な巨大数論に手を出していく感じ 肉も食えよ!
V4とV7は中途半端に再帰順序数使ってるところがサラダ感を否めない 順序数を使って定義しているのではなくて評価しているだけ(他の巨大数も大抵はそう)
ビジービーバーだって、順序数で「評価」されている
そして、V4の順序数は再帰順序数ではない V4なんてサラダそのものじゃん
何の目新しさもない
ただのゴミ それ以前に、
定義にすらなってない
神託機械の仕様が書いてない >>569
いや、神託機械の階層のようなものが再帰的に定義されていて計算不可能レベルじゃナンセンスという意味です。 それ言ったらLittle Bigeddonの真理述語も昔から知られているものでなんの目新しさもない
サスカッチ以外は全部サラダ(暴論) もちろん巨大数論的な観点から見た目新しさ
(昔からあったけど)この道具使えば大きな数定義できるじゃん!
てのは巨大数論的に目新しいね バシク行列とか、HUGEの証明論的強さをもつ欲張りクリーク列とか、かえって計算可能レベルのほうが
なにかと新しいな V4については、神託機械を使って巨大数を作ったというだけで、
「この道具使えば大きな数定義できるじゃん」という観点で、当時としては新しい
そもそも、このスレッドでは誰もが「計算不可能なんて意味ない」と言っていたわけで、
誰一人その巨大数が「定義される」とすら思っていなかった 「V4が定義されるのは当たり前だけど、そんなトリビアルな拡張は意味ないよ」
なんてことは、今だから言えることで、当時のログでそんなことを書いている人がいるかどうか
探してみればいい たとえば、こんな感じで「神託機械そのものを認めようとしない」というレベルの
スレッドの中で、神託機械で階層を使って巨大数が定義できる、と一貫して主張していた、
というだけですごいものだと思う
http://www.geocities.co.jp/Technopolis/9946/log/ln034.html
265 名前:132人目の素数さん :02/11/07 08:11
当然でしょう。チューリングマシンにビジービーバー関数は取り込めません。 ふぃっしゅさんは神託機械を見てV4を作ったのだと思っていたけど、
当時のログをよく読むと、最初にアイデアがあって、ロバートさんとの
メールのやりとりの後に調べて神託機械 (O-machines) を見つけた、
という感じみたい
http://www.geocities.co.jp/Technopolis/9946/log/ln033.html
245 名前:ふぃっしゅっしゅ ◆/T2GtW187g :02/11/04 04:49
「そんなはずはなかろう、同じ発想をしている人はいるん
じゃないのか?」と思い、よく調べてみると、それがまさに
O-machinesだったわけです。 V4よりずっと前から神託機械の概念があったし
実際V4の定義に「神託機械」と書いてある
V4が定義になってないことから
ふぃっしゅ氏が神託機械や機械自体をよく理解してない事がわかるわけだが
これを指摘した人はいなかったのかな? > チューリング次数はエミール・ポスト(1944)によって導入され、多くの基本的な結果はスティーヴン・コール・クリーネとポスト(1954)によって確立された。 神託機械の具体的な実装はO-machinesの原典に載っている通りにするってことじゃないの?
神託状態みたいなのを付加するやつ ログ読んでみたけどふぃっしゅ氏の文面がなんか若さを感じる。
ビジービーバーから再帰的に新しい関数を作ったところで本質的な強さに寄与
できてないという意味でロバートさんの主張は正しい 誰に聞いてるの?
答えはふぃっしゅしか知らないわけだが 1階述語論理の範囲では>>556でいいとして、2階述語論理以降ではある記述可能で非自明な定義文を評価するのに、どうしても記述不可能な(有限文字で表現できない)環境を必要とすることがあり、真理述語に頼らなければならなかったりする。
そう考えるとこいし数は高階述語論理を定義に使っていても実際には2階述語論理の域を出てないのでは?
真理述語の階層でいえばω*2の関数を2回適用したような
SOSTと同等? やたらと再帰的再帰的という人がいるけど、2次ビジービーバー関数は
ビジービーバー関数から再帰的に作られた関数ではない チューリング次数を+1出来る手段を使って
たったの ω^(ω+1) x 63 増やしただけだからなあ
ふぃっしゅの拡張は誤差だろ >2次ビジービーバー関数はビジービーバー関数から再帰的に作られた関数ではない
それはそうけどチューリング次数を再帰的に上げたところでという話で。
Ξ関数みたいにシンプルでよかったと思うわ そのチューリング次数を+1あげるという手段があることを、当時のスレッドでは
数学の専門家っぽい人もいろいろ書いている中で誰も指摘していなかったわけで、
それが指摘されていたらあんなに紛糾しなかった 当時のネットにはあった O-machines は参照されているので、そのページを読んでも、
神託機械のビジービーバー関数を考えることをビジービーバー関数の「再帰的拡張」と
同一視しているような人たちしかいなかった、というのが当時のスレッドのレベル というか、当時のスレッドは「ビジービーバー関数は神聖不可侵な関数で、
これよりも大きな関数は存在しない」という意見が支配的だった そう考えると、今って界隈全体のレベル上がってるんだね ふぃっしゅの井の中の蛙ぶりが半端無い
ってことだな
今そんなゴミ関数を取り上げる価値は無い 逆に取り上げる価値のある巨大関数って何なん?
FOSTも真理述語も昔から知られていて何の目新しさもないけど ビジービーバー、チューリングマシン、神託機械
の考え方は巨大数を語る上で必須科目と言っても良いくらいに価値がある
これらの優れた概念に対して、ゴミみたいな方法で+1したのがV4
このゴミのせいで台無しになった
アッカーマン関数をただ100乗したようなトンチンカン具合 ■ このスレッドは過去ログ倉庫に格納されています