巨大数探索スレッド13
■ このスレッドは過去ログ倉庫に格納されています
大きさだけで考えたら計算不可能なシステム一択
計算可能だと強配列表記の一連の流れに興味がある(絶対BEAFに対抗心燃やしてる) 当然計算可能な関数は越えないと
ビジービーバーより小さくてビジービーバーより複雑な定義の関数なんかには興味無い やっぱり計算可能と計算不可能でスレ分けた方が良いと思うんだよな
巨大数の世界に長く住むにつれて「この強さ以下はダメ」って閾値が生まれて、その値は理解するにつれてどんどん強くなるわけで ひたすら大きな帰納的順序数を追い求める人と>>459は理解しあえない 絶対BEAFに対抗心燃やしてるは言い過ぎでは。
プログラミングで必要な文字数で計ればビジービーバー関数は無限に複雑や そうだよな
話振る人は誰かにゴミと言われてもめげないことが最終的に大事だし
ゴミだと言いたくなっても出来るだけ言ってあげないことも大事だ
巨大数論でこれまで議論されていた数の大きさのスケール全体がどれ程広いのか理解できてはじめて双方の理解につながる
(サラダなのはさすがに言語道断だが) 理解しあえないからと言って発言権まで剥奪せんでもええやろ。誹謗中傷でもないんだから。 強配列表記の事についてはすまなかった
本人のページでBEAFは不完全だぽい事が書いてあってつい 一般的な感覚では大きいといえ、
指数関数について延々語られても迷惑だろ
そういうこと loader.cなんかは指数タワーでコード化してますし。
指数関数レベルでもなにか新しいアイディアによるものであれば歓迎だし、今後の発展性とかも考えるとよい 計算不可能関数の世界に到達して巨大数を眺めることに慣れてる人にしてみれば
多重リストアッカーマン関数やテトレーション配列が指数関数と同じようなものだと思ってもしょうがない
気持ちは分かる
用はそれを表に出すかどうかだ 煽りじゃなくて純粋に気になるんだけど、>>465の1962年ってなんなんだ。
あと>>463は帰納的順序数じゃなくて可算順序数では 指数関数で発展性なんか無い
このスレ的にはx+1と同じ >>474
>>462の続きのレスだから計算可能同士の例 ビジービーバー関数やラヨ関数もある意味指数関数の延長線上にあるやん。
loader.cみたいにコード化してメタな構造を作るのもよし 延長線上にある言ってもさすがに遠いな。適切な例ではなかった。すまん 再帰で強くするシステムを作るときは弱いのから考えていく節あるし、指数関数レベルでも前者でも自分は興味ある
計算不可能関数の魅力の一つは「最初からめちゃ強い定義をこしらえて、再帰じゃ絶対に到達できないものを作る」ことだものね
いつかやってみたい 指数関数の延長線上にビジービーバー関数やラヨ関数があると思う頭の構造が理解不能 ビージービーバー関数を、n文字のプログラムで指数関数を強化して得られる関数と解釈することも可能ではある。 >>482
ビージービーバー→ビジービーバー
計算不可能レベルはより強力な言語を開発して殴り合う戦いになるけど、それでできあがった言語って計算可能レベルでも
活躍できると思うし、計算可能レベルもある程度のレベルを超えると計算不可能レベルとやること変わらなくなってくると思う 同じ本質でもけっこう自由にいろんな解釈ができることを主張したい 計算不可能なシステムを計算可能なシステムに組み込ませて(再帰させて)もサラダになるだけ CoCは高階述語論理を型を使って計算可能レベルに実装したものだし、loader.cはサラダではないと思う 484の言ってることって可能なのかなと疑問に思った
まだ自分自身よく理解してない領域が残ってるから
「計算不可能レベルで開発された言語を計算可能レベルで使用する」
でも可能なんだね 面白い 開発した言語を計算可能レベルに実装するかそのまま対角化して不可能レベルの関数を作るかは
好きにすればいいし、不可能レベルに縛る理由はないだろう 実用的になるかどうかは分からんが、派生して新しい証明支援システムやプログラミング言語ができるかもしれないし 計算可能レベルの場合言語を強くしていく考え方よりも領域に関する理論をどんどん充実させていく
考え方のほうが本質に迫れるのかもしれない。
じゃあ不可能レベルは違うのかと言うと、高階の集合論でLに可測基数を追加した宇宙の対角化以上のことが
できるとか考えるだけなら考えられるが、自由度が高い分健全性にも気を遣わなければならなくなり、
計算可能レベルほど簡単にwell definedと言うことはできない。
という理屈だろうか。とりあえずそう簡単に新しくてより強力な言語を（健全性やら整合性やらどうでもいいというなら
ともかく）そう簡単に作れるものでもない、か。反省します ある意味計算可能レベルのほうが自由で強力だったりするのね 計算可能レベルだってwell-defineかどうか容易にはわからない物もたくさんある well-defined自体はwell-definedな概念なの？ well-defined自体がwell-definedだったら何か矛盾が起きるんだろうか？
でも自己複製するプログラムだって存在するし一概にはわからんか ゲーデルの第二不完全性定理によりwell-definedそれ自体はwell-definedではない
と言ってみる。 メタwell-definedという概念を作ろうぞｗ >>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の式だけで評価できる」ってしちゃうと計算可能になるんじゃないのか ■ このスレッドは過去ログ倉庫に格納されています
