巨大数探索スレッド13
■ このスレッドは過去ログ倉庫に格納されています
>>482
ビージービーバー→ビジービーバー
計算不可能レベルはより強力な言語を開発して殴り合う戦いになるけど、それでできあがった言語って計算可能レベルでも
活躍できると思うし、計算可能レベルもある程度のレベルを超えると計算不可能レベルとやること変わらなくなってくると思う 同じ本質でもけっこう自由にいろんな解釈ができることを主張したい 計算不可能なシステムを計算可能なシステムに組み込ませて(再帰させて)もサラダになるだけ CoCは高階述語論理を型を使って計算可能レベルに実装したものだし、loader.cはサラダではないと思う 484の言ってることって可能なのかなと疑問に思った
まだ自分自身よく理解してない領域が残ってるから
「計算不可能レベルで開発された言語を計算可能レベルで使用する」
でも可能なんだね 面白い 開発した言語を計算可能レベルに実装するかそのまま対角化して不可能レベルの関数を作るかは
好きにすればいいし、不可能レベルに縛る理由はないだろう 実用的になるかどうかは分からんが、派生して新しい証明支援システムやプログラミング言語ができるかもしれないし 計算可能レベルの場合言語を強くしていく考え方よりも領域に関する理論をどんどん充実させていく
考え方のほうが本質に迫れるのかもしれない。
じゃあ不可能レベルは違うのかと言うと、高階の集合論でLに可測基数を追加した宇宙の対角化以上のことが
できるとか考えるだけなら考えられるが、自由度が高い分健全性にも気を遣わなければならなくなり、
計算可能レベルほど簡単にwell definedと言うことはできない。
という理屈だろうか。とりあえずそう簡単に新しくてより強力な言語を(健全性やら整合性やらどうでもいいというなら
ともかく)そう簡単に作れるものでもない、か。反省します ある意味計算可能レベルのほうが自由で強力だったりするのね 計算可能レベルだってwell-defineかどうか容易にはわからない物もたくさんある 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が定義になってないことから
ふぃっしゅ氏が神託機械や機械自体をよく理解してない事がわかるわけだが
これを指摘した人はいなかったのかな? ■ このスレッドは過去ログ倉庫に格納されています