巨大数探索スレッド13
レス数が900を超えています。1000を超えると表示できなくなるよ。
定義文で関数を強くするよりも、定義文を上位の定義文で拡張すれば良いのでは
中の定義文を強化する言わばS定義文 >>820
だいたいそんな感じ。
そしてそれは標準的な入力に対しても起こり得る。 >>795はビジービーバーがwell definedであることの説明になってないと思うし
関数であることや全域性を証明できてもモデルによって関数が変わるってつまりwell definedじゃないってことだしだからこそラヨ関数がwell definedでないと主張してたんじゃないかと
ビジービーバー関数もラヨ関数も任意のモデルで停止するとか命名文になるとかいうふうにすれば解決する、
というのであって
ラヨ関数は「任意の」という量化の範囲を公理のモデルにするか命名文のモデルにするかで2パターンに別れる とりあえず集合の濃度すらwell definedでないと思うなら、数学においてwell definedとはどんな意味の用語なのか調べたほうがいいんじゃないかな。
多分思ってる定義と世間一般での定義が違うから。 >>826はwell definedとはcomputableのことだと誤解してる
数学を知らぬ馬鹿の典型 >函数がwell-definedである事を 言うためには、
>(函数の)記述が表わす対象が 一意に決まる事を
>言わないといけないんじゃないの？
それは函数を定義する体系の強度に依存する
そういうことに無神経なのが、数学を知らぬ馬鹿 逆に>>830が考えるwell definedといえるものって例えば何？ 集合の濃度がwell definedでないというんじゃなくて、べき集合の濃度というだけじゃどれほどの濃度かはwell definedじゃないという意見 モデルの取り方によって値が超準元になり得るというのは
ごく普通にあり得る現象で、普通に数学をしている場合は
それだけだwell definedでないとは言わないとは思う。
ただ、仮に標準的自然数の値のみを考えるとか
規約したとして、それで元々の問題においてきちんと
数を定義した事になるのかと言えば大変微妙なんだけど。
つまり、ある式が或る自然数を定義しているかどうかが
ZFC + 巨大基数公理みたいな死ぬほど強い公理系から
独立になってしまうので。 だから冪集合の濃度がwell definedでないという
言い方は普通しないよね。
2^aleph 0 = aleph αとした時に、αの値は
ZFCでは決定できない、とは言えるけど。
すごく単純な例で例えていうなら、
世の中にはアーベル群と非アーベル群があるから
群Gが可換かどうかはwell definedでない、
とか言ってるようなもの。 2*3*5*√(x^2+1/2^2+1/3^2+1/5^2+2*(x*(1/2+1/3+1/5)+1/2*(1/3+1/5)+1/3*1/5))
2*3*5*√(4^2/5^2+1/2^2+1/3^2+1/5^2+2*(-4/5*(1/2+1/3+1/5)+1/2*(1/3+1/5)+1/3*1/5))=7
2*3*5*√(2^2/3^2+1/2^2+1/3^2+1/5^2+2*(-2/3*(1/2+1/3+1/5)+1/2*(1/3+1/5)+1/3*1/5))=11
2*3*5*√(3^2/5^2+1/2^2+1/3^2+1/5^2+2*(-3/5*(1/2+1/3+1/5)+1/2*(1/3+1/5)+1/3*1/5))=13
2*3*5*7*√(5^2/5^2+1/2^2+1/3^2+1/5^2+1/7^2+2*(-5/5*(1/2+1/3+1/5+1/7)+1/2*(1/3+1/5+1/7)+1/3*(1/5+1/7)+1/5*1/7))=37
2*3*5*7*√(6^2/5^2+1/2^2+1/3^2+1/5^2+1/7^2+2*(-6/5*(1/2+1/3+1/5+1/7)+1/2*(1/3+1/5+1/7)+1/3*(1/5+1/7)+1/5*1/7))=5
2*3*5*7*√(7^2/5^2+1/2^2+1/3^2+1/5^2+1/7^2+2*(-7/5*(1/2+1/3+1/5+1/7)+1/2*(1/3+1/5+1/7)+1/3*(1/5+1/7)+1/5*1/7))=47
2*3*5*7*√(5^2/7^2+1/2^2+1/3^2+1/5^2+1/7^2+2*(-5/7*(1/2+1/3+1/5+1/7)+1/2*(1/3+1/5+1/7)+1/3*(1/5+1/7)+1/5*1/7))=97
2*3*5*7*√(6^2/7^2+1/2^2+1/3^2+1/5^2+1/7^2+2*(-6/7*(1/2+1/3+1/5+1/7)+1/2*(1/3+1/5+1/7)+1/3*(1/5+1/7)+1/5*1/7))67
2*3*5*7*√(8^2/7^2+1/2^2+1/3^2+1/5^2+1/7^2+2*(-8/7*(1/2+1/3+1/5+1/7)+1/2*(1/3+1/5+1/7)+1/3*(1/5+1/7)+1/5*1/7))=7 どのモデルでもその中でBB(n)は一意であることも、どの計算可能関数よりも大きいことも証明できるんだから単に大小比較をするのに何の問題もないじゃないか。
0=BB(n),1=BB(n),...のどれかが証明できる必要なんてない。 BBの大きさを語る能力の無い公理系では
BB(ある大きい数) の値を実際とは違う値だと決めても矛盾を証明出来ない
だから上の公理系に対して
BB(ある大きい数)=実際と違う値
という公理を加えても無矛盾となる
だからBB(ある大きい数)の値は公理依存で一意に決まらない
と主張してる人がこのスレに約１名いる それぞれのモデルの中で一意に定まるんじゃなくて、定義文から一意に定まることを求められるんだと思う、でないと数の大小関係が自明でなくなってしまうことが考えられるし、ある定義文がどこまでも大きな自然数を定義しているという主張ができてしまう。
同じ体系内であればどう解釈しようが大小関係は変わらないということも考えられるが異なる解釈で大小が変わってしまうことがあるのは評価の一意性に欠けてしまう。
あと函数を定義する体系の強度に依存するというのは、たとえば1階述語論理で定義された場合であれば体系の強化が間違っていることになってこの例には当てはまらない
ビジービーバー関数は任意のモデルで同じ関数を意味するように定義することができないという意味では1階述語論理で定義できないが、
任意の標準モデルを充足するという形でなら、同じ関数を意味するように、つまりwell definedに定義できる 任意のモデルで同じ関数を意味するって
自然数を定義できないモデルとかどうすんの？ 何かstackexchangeとか見てたら、やっぱRayo関数は
いろいろ問題ありそうな感じだね。
海外サイトでも有名な論理学者とかが、やっぱり
理論の不完全性定理とかTuring機械の停止性とかと
絡めて説明してるからこのスレが脱線して非本質的な
議論してるわけじゃなさそう。
https://math.stackexchange.com/questions/2199190/the-first-few-values-of-rayos-function
Rayo関数は一階の集合論内では定義できない。
二階の集合論とかMorse-Kelleyの集合論とかは
一階部分の真理述語を持ってるから一応定義は出来る。
更にRayo関数がZFCなどの一階の集合論で定義出来る
全ての関数を十分先でdominateする事が示せる。
真理述語が使えるのかどうかとかの基礎論的な文脈を
特定しないと無意味なんじゃないのか、と。
二階の集合論が必ず一階部分の真理述語を
持ってるわけじゃないし、持ってなくても部分関数で
代用できる場合もあるし、さらに関数が集合として
存在する事が示せなかったりするし云々。
ぶっちゃけ、連続体濃度がアレフkとなる
自然数nが存在する時k、存在しない時0、みたいな定義も
明らかに1 googol文字以下で出来てるんだか
こういうのどうすんのよ、と。R(n)の値はちょっと先に
行くと明らかにZFCから独立になって
本質的にメタ数学的な問題だらけになる、と。
https://mathoverflow.net/questions/34710/succinctly-naming-big-numbers-zfc-versus-busy-beaver
何か計算量理論で出てくるアルゴリズムで
有名な研究者がコメントしてたりする。
https://mathoverflow.net/questions/32891/finding-the-largest-integer-describable-with-a-string-of-symbols-of-predefined-le
基本的に、こういうコンテストでは誰が勝者かは
再帰理論的な意味で計算不可能になる。
何気にFields賞受賞者とか、証明論の有名な研究者とかがコメントしてる。 あとどっかに、超準モデルでは超準ステップで停止する
Turingマシン、みたいな問題を避けるためには
ベースの理論が無矛盾なだけじゃなくて
少なくともω無矛盾じゃとないといけない、
とか書いてあって、確かにそうだよね、と。
停止までのステップ数が変なモデルを取ると
変わり得るというのは、こういう或る程度の強さの
算術的な健全性を仮定すれば一応解決出来るっぽい。
標準的な自然数というのは一通りに確定する事になってるから。 二階論理なら自然数のモデルが全部同型になるような自然数論を作れるのは確かにデデキントが証明した通り。
しかし英語版wikipediaのPeano axiomsの記事
https://en.m.wikipedia.org/wiki/Peano_axioms
によると、これは集合論の立場から見れば、集合論のモデルが決まればその中での二階PAのモデルは一意と言っているだけで、選んだ集合論のモデルが超準的ならその中で作れる二階PAのモデルもまた超準的でありえる。 >>837
BB(ある大きい数)がある値「である」と仮定しても無矛盾、と
BB(ある大きい数)がある値「ではない」と仮定しても無矛盾、じゃ意味が違うぞ。
後者は見たことあるが、前者の主張は見たことないな。明らかにBB(ある大きい数)=0からは矛盾が導けるし。 言いたいことが>>798ですでに言われていた
任意の標準的な自然数につき、ビジービーバー関数の値でないことは、それぞれの引数につき、標準モデルでビジービーバー関数の値になるものひとつを除いて証明可能。
>>838は充足という言葉のつかいかた間違えてた。
自然数のコーディングを決めて論理公理やらを前提として、ビジービーバー関数の定義文とされるものを充足する任意の標準モデルにおいて同じ関数を意味するように定義可能 >>795の最初の命題ってさ、計算不能関数なら機械的証明ができるとは限らないってそれ当然では？ 2^n-1=1+2+2^2+2^3+2^4+2^5+・・・+2^(n-1)
n=2kのとき3で割り切れる
n=4kのとき5で割り切れる
n=3kのとき7で割り切れる
n=10kのとき11で割り切れる
n=12kのとき13で割り切れる
n=16kのとき17で割り切れる
n=a*kのとき
2^(a*k)-1は必ず(a+1)を因数にもつ
a=a1*a2のとき
2^(a1*a2*k)-1は必ず(a1+1)と(a2+1)を因数にもつ
2^(31)-1のとき
2^(31)-1は31+1=32=2^5を因数に持つはずだが
2^(n)-1は2で割り切れないので素数になる
2^(15)-1のとき
2^(15)-1は15+1=2^4を因数に持つはずだが
上記と同じ理由で割り切れないが
15=3*5なので7を因数にもつ 2^(n)-1
n=15kのとき
2^(n)-1は7と31と151を必ず因数にもつ
n=30kのとき
2^(30k)は必ず7と31と151と331を因数にもつ 1+2+2^2+2^3+2^4+2^5+2^6+2^7=(1+2+2^2+2^3)+2^4*(1+2+2^2+2^3)=(1+2)+2^2*(1+2)+2^4*(1+2)+2^6*(1+2)=(1+2^2+2^4+2^6)*(1+2)=((1+2^2)+2^4*(1+2^2))*(1+2)=(1+2^4)*(1+2)*(1+2^2)=17*3*5
2^(n*k)-1
2^(2*n*k)-1=1+2+・・・+2^(2*n*k-1)=1+2+・・・+2^(n*k-1)+2^(n*k)*(1+2+・・・+2^(n*k-1))
2^(2^(2^(n)-1)-1)-1=2^(127)-1は素数
2^(2^(2^(2^(n)-1)-1)-1)-1は素数 2^(2^(n)-1)-1
n=2^(2^(n)-1)-1
2^(2^(2^(2^(2^(2^(2^(2^(n)-1)-1)-1)-1)-1)-1)-1)-1
2^(2^(2^(2^(2^(2^(2^(2^(3)-1)-1)-1)-1)-1)-1)-1)-1は素数
2^(2^(2^(2^(2^(2^(2^(2^(5)-1)-1)-1)-1)-1)-1)-1)-1は素数
2^(2^(2^(2^(2^(2^(2^(2^(7)-1)-1)-1)-1)-1)-1)-1)-1は素数 定義 H(x)
x!*x!^x!
He(x)=
H(x)^H(x)
途中省略
Ts(x)=
Lv(x)!^Lv!
Og(x)=
Ts!^Ts(x)!
本編
Og(ラヨ数)
これ何桁くらい？ 左から新しい数列、新しい配列表記のセパレータ、DANのセパレータ
(0,2)=(1:3)=(1,,2)
(0,2,2)=(1:4)=(1,,,2)
(0,2,2,2)=(1:5)=(1,,,,2)
こんな感じで数列や配列表記でもトリオ数列同等の強さを発揮しそう。
具体的な定義は考えて、どうぞ 結局、巨大数を生成する関数って、場合分けが多いほどビジービバーの状態数が多いのに対応するみたいな感じで、
基本的には場合分けが多いほど強くなりやすいでOK? ただ多いだけじゃ強くはならない。
強くするためのツボを押さえていかないと複雑なだけのサラダになる まじ卍関数
卍(x)=
例えば卍(4)=
卍(2)*卍(3)
卍(2)=2,卍(3)=2なので
2*2
4 下の関数はどれくらいの増加量ですか 教えて下さい
Ｘ ： 0個以上の1以上の整数
Ｙ ： 0個以上の1以上の整数
ａ ： 2以上の整数
ｂ ： 1以上の整数
ｃ ： 1以上の整数
ｄ ： 1以上の整数 のとき
① ｂ[1，Ｘ]ｃ，ｄ=ｂ[Ｘ]ｃ，ｄ
② ｂ[1]ｃ，ｄ=ｂ→ｄ→ｃ
③ ｂ[Ｘ，ａ]1，ｃ=ｂ[Ｘ，(ａ－１)]ｃ，ｂ
④ ｂ[Ｘ，ａ，1，Ｙ]ｃ，ｄ=ｂ[Ｘ，(ａ－１)，(ｂ[Ｘ，(ａ－１)，ａ，Ｙ]ｃ，ｄ)，Ｙ]ｃ，ｄ
⑤ ｂ[Ｘ]ｃ，ａ=ｂ[Ｘ](ｃ-1)，(ｂ[Ｘ](ｃ-1)，(ｂ[Ｘ](ｃ－１)，・・・・(ｂ[Ｘ](ｃ－１)，ｂ)))
ただし⑤の式で右辺のｂはａ個
>>857
卍(x)=2^(フィボナッチ数列のx項目) 卍関数計算中... 1,2,2,4,8,32,256,8192,2097152,17179869184
36028797018963968 理屈が解ってればパッと詳細な答えが出る→答え合わせができる数式なら鍵と錠前になるけど……
巨大数って詳細な数値を最後の一桁まで出すようなもんじゃないからどうなんだろ 巨大基数を仮定すればNP問題が多項式で解けるとか無いの？ >>861
ならば！！
「TMB」
TMB(x)=
TMB(x-1)^TMB(x-2) >>865
一応、ZFC+ω-huge cardinalの存在を仮定すれば、
Kunen's inconsistancy theoremと
principle of explosionより
NP問題が多項式時間で解けることを導ける。
まあ無意味だが。 >>210
SaidiやLepageに見放されてないんだな TMBの場合は...
1 2 2 4 16 65536 115792089237316195423570985008（続く）
（続き）687907853269984665640564039457584007913129639936
ぎゃあああああああああ ZFC + ω-huge cardinalを仮定したら
NP問題が多項式時間では解けない事を示せるよ というか >>874 が矛盾したらP=NPの証明完了 第1卍数です。
A(x)=(804^x!)→x→x→(804^x^x)
B(x,y)=(x^y)*(A(x)↑↑A(y))→x→(804^x)
C(x,y)=(10↑↑↑(A(x)*A(y))^B(804^xy)
D(x,y,z)=(3↑↑・・(y↑↑・・（z↑↑↑回）・・↑↑y回)・・↑↑3)^(x→y→z→y→x)
このとき、
D(A(1000),B(361,73),C(16552,77384))が第一卍数 （訂正）
>>880の「z↑↑↑回」は正しくは「z↑↑↑z回」でした。すいません 結局ω-huge cardinalってなんなのよ？ 逆にP=NPが言えればω-huge cardinalが存在することも言える？ 勉強が進んでやっとω進数が存在するかどうかって話だと理解した rank into rank cardinal の一番弱いやつ もう集合論の知識ないと何言ってるかわからん世界だな
取り敢えず階層内階層基数(公理?)ってZFCに付け足しても破綻しない中では一番強い巨大基数公理だっけ? 破綻してるかしてないかなんてわからないし
一番強いなんて物も無い wikipediaでググればあまり数学的に意味のある事を言ってないと分かるんだけどね wikipediaのhuge cardinalの記事見たら、ω-hugeには複数の同値でない定義があって(つまりω-hugeという言葉は意味が不明確で)、定義によっては>>869が真とは限らなくなるっぽい。
だから>>869の言明は取り下げる。
ω-huge cardinalをReinhardt cardinalに置き換えれば確実に>>869が言えるけど。 >>889
英語版のWikipediaのリストになんかあったんでそうだと思ってた
おんなじリストによると、選択公理と併用できないのがラインハルト基数とあとなんかもう一つあってこれが階層内階層基数よりも強いらしい(Wiki調べ)
>>890
英語noobだから件の表見たところで力尽きた 数学板なんだから
「同値」くらい正しい意味で使おうよ うーんついていけない。
wikiとかちんぷんかんぷんな説明だし。 本買って読んだ方がいい気がするけれど、どんな本がいいんだろうかねぇ 去年はSpringer yellow saleで安くて
半額くらいだったよね。
今年はJechのSet theoryが安い。 f_[a](n)は急増加関数
aはℵ_1より小さい順序数
lim{a→ℵ_1}f_[a](n) まずはaが??_1より小さい順序数の時のf_[a](n)を定義してください 計算可能関数で最大の増加速度のやつって、階層内階層基数のI0をもとにした関数系でいいの？ このスレに上がったwell-definedの物ってこと？
このスレにwell-definedの物はほとんど無いけど 計算可能って言っても、
具体的に計算するアルゴリズムがわからなくて良いならいくらでも定義出来るから
具体的な計算アルゴリズムで定義して初めて計算可能な価値があると思うんだ
関数自体は計算可能だけど
その関数をアルゴリズムの形にするのに
計算可能でない手続きが必要なもの
なんてのは計算可能関数としての価値は無い ラヨ数の巨大数wiki、変数設定とかマイクロ言語とか耳慣れない単語があるんだが、これってどんな分野の言葉なの？ 会話のドッジボール
そういえば「マイクロ言語」って言葉ラヨ関数の記事以外で見たことない 巨大数wiki見たんだが、サスクワッチって何でadjunction(随伴関手)やclosure(閉包)が出てくるんだ？ ラヨ自体、二階の集合論の論文とかを書いたり
してる人ではあるので、「変数設定」はそっち系の
分野では通じるものの言い方なのかもしれないけど
まああまり聞かんよね
マイクロ云々はしらない キューネンには閉集合があった気がするが、adjunctionあったっけ よし、では表記法の作成をしよう
a 競 b =a^b
a 競 1=a
a 競^c b=a競^c-1(a競^c-1(・・(a^b^c nested)・・(a競^c-1b))(a^b^c nested)) リトルビッゲドンがビッグフット以上の理由がよく分からないんだが
分かる人いる？ ε_0以上の順序数がよく分からないので誰か教えて下さい ε_0 = ω^ω^...^ω
ε_(a+1) = ω^ω^...^ω^(ε_a+1)
ε_a = lim ε_a_n @ a= lim a_n サスクワッチの帰属関係が右肩に乗っかってるのって何だ？
モデルの相対化とかなら分かるが、帰属関係が右肩に乗っかるのは見たことがない これ帰属関係が複数あるから「この式はこっちの帰属関係の意味」ってことなのか
にしても関係が3つもある理由がよく分からんな…… 次の関数の大きさの評価をお願いします。
{}とその中のいくつかの非負整数の組のことを合わせてリストと言うこととする。
例) {5，3，2，7} など
リストの中で{}の中に数が１つもないものを空リストと言うこととする。
{Ａ}や{Ｂ} … 0個以上のリスト
{Ｃ}…０個以上の空リスト
ａやｂやｎやｍ …１つの非負整数
Ｗ …０個以上のの非負整数の組
Ｙ …0個以上の0の組
① ｎ{ }ｍ= ｎ×ｍ
② ｎ{ａ+1，Ｗ}{Ａ}ｍ
= ｎ{ａ，Ｗ}{Ａ}ｎ{ａ，Ｗ}{Ａ}ｎ …(ｎがｍ個)… ｎ{ａ，Ｗ}{Ａ}ｎ
③ ｎ{Ｃ}{Ｙ，0，ａ+1，Ｗ}{Ａ}ｍ= ｎ{Ｃ}{Ｙ，ｍ，ａ，Ｗ}{Ａ}ｍ
④ ｎ{Ｃ}{Ｗ，Ｙ}{Ａ}ｍ= ｎ{Ｃ}{Ｗ}{Ａ}ｍ
⑤ ｎ{Ａ}{0}{Ｂ}ｍ= ｎ{Ａ}{ }{Ｂ}ｍ
⑥ ｎ{Ｃ}{ }{ａ+1，Ｗ}{Ａ}ｍ
= ｎ{Ｃ}{0，0，0 …(0がｍ個)… 0，０，1}{ａ，Ｗ}{Ａ}ｍ
⑦ ｎ{Ａ}{Ｃ}ｍ= ｎ{Ａ}ｍ
⑧ ｎ{Ａ}ａ{Ｂ}ｍ= n{Ａ} (ａ{Ｂ}ｍ) レス数が900を超えています。1000を超えると表示できなくなるよ。
