巨大数探索スレッド12 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
まったくの素人意見だが・・・
無限の広さがある碁盤と無限にある碁石を使って、画像認識みたいな
テクニックである程度自分で巨大数ではないかと思われるシステムを
作ることはできるだろう。
でもそれは統計的に「らしい」ものを作っただけでコンピュータが自分で
論理を組み立てたわけではないし、そういうわけで本当にまともなプログラム
になっている保証もない。
結構な確率で出来上がるところまでは行けるだろうが。 評価方法も考えなければならないことをうっかりしていた。
まぁあらかじめ教えておいたとしてもなお課題が残るということで。
>>121
関数自体は評価を表現する一つの手段であって、比べる手段そのものではない
ので・・・
たとえば任意の自然数nについて、n+1<n+2が成り立つというくらいのの証明は、
答えにたどり着くまでただひたすら妥当な証明を書きまくるという数の暴力作戦
でもわりと現実的な時間内に得られるでしょうし。 割と現実的な時間内に得られるww
絶対無理だから。一生計算終わんないから。 証明ができるAIはいつできるだろうか
量子コンピュータのあとかな >>149
証明と量子コンピュータは恐らく全く無関係ですよ
自明でない公理系での定理の証明は定理の言明(を表す論理式)のサイズに関してNP完全かNP困難
ところが量子コンピュータ(より正確な呼び名は量子デジタルコンピュータ)は
NP完全問題を高速に解けないというのが計算量理論の専門家の間でほぼ全員一致で予想され認識されていること
(量子コンピュータが通常のデジタルコンピュータとは違って迅速に解けることが判明した問題の一つである
素因数分解問題はNP問題ではあるがNP完全ではないと計算量理論やアルゴリズム論のコミュニティで予想されている) BBは、ビジービーバー関数
zは、0個以上の0以上の整数
xは、0個以上の0または1
a:bは、b個のa
a,b,n,mは、0以上の整数
f_0()=BB(10↑^(10)10)
f_0(0)=BB(f_0())
f_0(a+1)=BB(f_0(a))
f_0(0:(n+1),0)=f_0(f_0():(n+1))
f_0(0:(n+1),a+1)=f_0(f_0(0:(n+1),a+1):(n+1))
f_0(z,b+1,0:n,0)=f_0(z,b,f_0():(n+1))
f_0(z,b+1,0:n,a+1)=f_0(z,b,f_0(z,b+1,0:n,a):(n+1))
f_1()=f_0(f_0():f_0())
f_1(0:n+1)=f_0(f_1(0:n):f_1(0:n))
f_1(1:(m+1))=f_1(0:f_1(),(1,0:f_1()):m)
f_1(x,0,1:(m+1))=f_1(x,(1,0:f_1()):(m+1))
f_1(x,0,1:(m+1),0:(n+1))=f_1(x,(1,0:f_1(x,0,1:(m+1),0:n)):(m+1))
f_1(2)=f_1(0:f_1(),(1,0:f_1()):f_1()) >>148
妥当な証明を書きまくるというか、公理やすでに証明された論理式に推論規則を
適用しまくって目的のものにたどり着くまで待つって感じか。
∀x∃y(sx=y∧x<y)|-sa=b∧a<b
∀x∃y(sx=y∧x<y)|-sb=c∧b<c
sa=b∧a<b∧sb=c∧b<c|-∀x∃y∃z(sx=y∧x<y∧sy=z∧y<z)
例化や量化の手順は端折ってるがこんな具合。
後者関数の公理だけから出発して例化と量化を適用してるだけだし、
なんとかなるんじゃ、後者の後者のほうが大きいことを証明するだけなら。 >>152
順序数関数だけどヴェブレン関数とかフェファーマンのθ関数とか、あとは超越整数とか、ローダー数とか、ビジービーバー関数とかラヨ数とか、その辺がアプローチが近いと想うよ 愚直にやるとまともな計算結果が出る前に、物理メモリの限界が来るんだよね。
宇宙の全物質を計算機に変えても足りない。 形式化された証明のデータベースを貯めて貯めて、機械学習でcutを使えるようにさせるのは大前提だろうね。人間の証明を自動的に形式化させるにしてもやはり対応した形式化された証明のデータが必要だろうから、結局形式化された証明のデータベースは必要。 BIG FOFTとビッゲドンではどっちが大きいのん? >>145
計算しなおしたところ、確かにそうなりました。
Τ_1(Τ_1(0)+1)=ψ_0(ψ_1(Ω_2^(Ω×ω))) となり、
ψ_0(Ω_ω)=Τ_ω(0)になりそうです。
バシク行列って凄いんだなぁ… 初歩的で申し訳ない
ωから有限回の加算・乗算・冪乗では到達できない
最小の超限順序数をε0と呼ぶらしいですが
矢印表記を使ってω↑↑↑・・・↑ωのように拡張してはダメなのですか? 一般に使われる関数がべき乗までだから単にそこで区切られているだけじゃない?
ヴェブレン関数とかはωが基準になってるよ >>159
何が聞きたいことのかわからん。拡張したければすればいいのでは。
4行目の質問が1〜3行目の文とどう絡むのか分からない ω→ω→ω→ω→ω→ω→ω→ω→ω→ω
おいなり祭り開催!!! 超限順序数の計算規則は自然数とは違うから自然数の関数に突っ込んでもうまく計算できないことが多い。
BEAFがまさに同じことしてるけどものすごく複雑化してる。 あんまりよく分からないなりに、矢印やお稲荷さんが飛び交ってるの見てたんだけど
巨大数って言うのは、あくまでも有限の数の大きさ比べなのか?
Wikiとかで調べたらωとかE0?みたいな奴は無限の親戚みたいだけど、有限の数の式になんで無限が出てくるの? それがよく分からない
実際に巨大数を出力する関数とその関数の評価をする関数があって、ωとかが出てくるのは評価する関数ってこと? 増加率の単位のような感じ
その関数で到達できない数を表すときにωを使う 到達できないではおかしいか
実際に計算してωにとどく数は無いな ある関数fがgより大きいっていう場合、ある数cが存在して
∀x>=c f(x)>g(x)
みたいな議論することあるけど、巨大数論的にもこの方針を採用してるの?
それとももっと別の基準がある? >>166
巨大数は有限の数の大きさ比べ。
>>168
急増化関数はよく「評価するための関数」だと言われるから混乱するけど
「評価するために使われやすい」って言うだけで、
グラハム関数と同じ普通の単なる「実際に巨大数を出力する関数」だよ。
順序数を変えると違う関数になるのでひとつの関数じゃなくて関数群、って言う方がいいけど。
ωやε0は使われ方によって違うけど、
1,2,3…<ωだとか、ω,ω^ω,ω^ω^ω,…<ε0 だとかの順序数同士の大きさに関する性質が
そのまま関数の強さに対応するので使われてるだけだよ。
f[ω](n)はf[1](n)よりもf[2](n)よりもf[3](n)よりも…有限のmで与えられる全てのf[m](n)よりも大きい
とか、自分より小さい関数が無限個あるので無限を表す順序数を使わないと名前が付けられなかったんだよ >>171
関数を比べるときにはだいたいみんなその基準を使っているよ。「fはgを支配する」呼んでる
http://ja.googology.wikia.com/wiki/ユーザーブログ:Limitofempty/対角化と支配する >>172
解説ありがとう
その急増化関数っていうのは使う順序数で出力が変わるけど、やっぱり限界があるってことなの?
Aの巨大関数は急増化関数で大きさ比べできるけど、Bの関数はでかすぎて無理みたいな >>174
急増加関数に限界は多分ないけど
順序数をひとつ決めちゃうと関数が確定するから
こんどは「大きな順序数」を探す必要が出て来て、
大きな順序数を作るための「順序数を出力する関数」としてヴェブレン関数が使われる。
さらに順序数をでかくすることに限界がきて
今度は大きな基数を使ってでかい順序数を作る順序数崩壊関数
(フェファーマンのθとかブーフホルツのφとかワイヤーマンのθとかの順序数が出てくる関数)
が使われたりさらに拡張されたりしてる 丁寧な解説本当にありがたい
急増加関数でたぶんいろんな関数の真似事はできるけど、その部品は別途用意しないといけないということか
その部品の製造工程でもっと大きな数が出てくるから、結果的に急増加関数は関数の評価に使われてるって感じ? 収束列を厳密に設定しないといけないから、急増加関数だけじゃwell-definedにはならないんだろう。
ωの収束列が0,1,2,・・・でなく2,4,6,・・・でもいいわけだし。 自然数→自然数:関数
順序数→関数:順序数階層、ハーディー階層、急増加関数
基数→順序数:ヴェブレン関数、順序数崩壊関数、フェファーマンのθ、ブーフホルツのΨ、マドールのΨ、ワイヤーマンのθ 少し前からGwikiのブログが面白いことになってる。 円周率が乱数ならそれ使うのはだめなの?例えば「0が9→→9個続く桁数」とか いいんじゃない。
ランダムだと考えて、だいたい10^(9→→9)くらいの数だよね。
適度に大きい数だと想うよ ヴェブレン関数は順序数→順序数では
>>182
10^(9→→9)ぐらいにしかならなさそう 0が9←←9←←9個続き1〜6を一つも含まず双子素数に挟まれ前後六つ以内にカーマイケル数とブリエ数が存在する完全数 vs A(10, 10) ちょっと考えてみた
PI(x)を「円周率でxがx回繰り返された時の1番下の桁数」とする。PI(7777777)をaとして、
PI^a(a) >>186
テトレーションレベルかな。
円周率を使ったことより関数の合成を数え上げしたことの方が効果が大きかったね 円周率がまったく一様かどうかについてはまだ分かってないことが多いのかな。
実は1が7000個以上並ぶことはないとか、知らんけど。 >>186 TA(x)をπとeとφとルート2とルート3で同時にxがx←←x回同時に出たときの一番下のケタ数とする。
TA^(TA(9))(9←←9) 186です。自分で定義した関数だけを使う自分ルールを作ると、才能が無いからあんまり大きくできないんだよな、、、 円周率を使うこととか、なぜ自分がその方法に魅力を感じたのかを哲学して、さらにそっち方向に尖るように磨きをかけよう。
例えば、無理数っていうのは無限に存在する部分数列が無理やり一列に並んでいるから、
こっちが勝手に指定した数はものすごく巨大な桁数のところにすっ飛んでいくだろう、っていうアイデアだよね
(永遠に出てこない可能性がある弱点はあるけどアイデアは上記のはず)
√2の系列1,4,1,4,2,1,3,5,6,…(以降無限に続く)が初めて現れる桁数とかは?
そうか、googol桁の数列が全部出切る桁数、などと最大値演算を使ってしまうとか。 (7P7)P(7P7)... = ((7!)!)... みたいな感じに出来たら夢が少しありそうなんだけどな・・・ 対角化が一番やりやすいから
可融差関数とか例外はあるけど f(x)=min{n | SUM(n) > x}
SUM(n)=n番目までの素数の逆数の総和
f(1)=3 (1/2+1/3+1/5)
f(2)=59
e^e^xと同じぐらいの強さらしい ビジービーバー関数とラヨ関数が強さがだいたい同じというのはどうだろう。
ラヨ関数について整理
フォン・ノイマン宇宙という具体的なモデルではないが、漠然としたモデル
のようなものの中で数やら関数やらを作っていく。
0の存在を保証する公理がなければ0を定義できないとの意見があったが、
フォン・ノイマン宇宙の中の0というものとユニークに一致すれば0が命名
された、とするのがラヨ関数の定義。 ラヨ関数が神託機械で計算できるかどうかという話か。それはさておき、
前スレ終わりのほうの議論と関係しているようだな。
存在を証明できなければ定義したとは言えないと考える。
よってn文字で記述可能な公理系から証明可能かどうかを考える。
でもそれならその公理系も定義の中に含めてしまって
n×2文字で記述可能な・・・って関数を定義してしまえばいいんじゃな
かろうか。
そう考えるとその定義(とされたことになっている)数がその公理系の下で
存在することを証明するための公理系を考える・・・となっていき切りが
ないな、証明が証明になっていることの証明をどんどん追っていくようなものだ。
無条件で正しいと信じるための信仰が必要だ。 この前 >>199 を Wowoju に聞いたらビジービーバー関数はチューリングマシンで記述できないし
ラヨの言語でビジービーバー関数が定義できるのでラヨ関数の方が強いって言ってた
この前 >>200 を Wowoju に聞いたらそれはふぃっしゅ数バージョン7ですでにやってるって言ってた 前スレの双子素数の例えになぞらえて、
存在が否定されれば「最大の双子素数」という文は定義になっていない。
よって「最大の双子素数」というものを定義するためには「最大の双子素数」
の存在を証明しなければならない。(これは最初から定義されていないという
方向で考えても存在が証明されればに誤りになってしまう)
「最大の双子素数」を0に置き換えたものが前スレ200あたりからされている議論か。
ある存在をある公理系、もっとざっくり言ってある前提から証明されたところで
それは相対的な存在性が示されただけで、同じく否定されれば相対的な非存在性
が示されただけだ。なので極端な話最大の素数や最大の自然数がある条件の
もとで相対的に存在するといってもいい、ある言語によって否定されたとしても
より高度な言語で場合によっては存在することもあることが示されたとか言って
おけばいい。ただし具体的にどう存在するのかを示すことができなければただの
バカの戯言になってしまう。
直観的な理解を具体的に記述された言語で共有した気分になっているが、
実際にはひどく危ういものだし、永遠に危ういものだ。 P(0)=1
P(1)=ω
P(2)=ω→ω
P(3)=ω→ω→ω
P(4)=ω→ω→ω→ω
P(ω)=ω→ω→…ω個…→ω→ω 有限個の自然数a,b,c,…と以下の演算を用いて有限の長さの式で表せない最小の自然数をPz(a,b,c,…)とする。
・四則演算 +−×÷
・累乗 ^
・根号 √
・階乗 !
・総和 Σ(Σn=n×(n+1)÷2)
例:Pz(1,1)≧8(1を2つ使って1〜7の自然数を作れる。)
Pz(4,9)≧14(4と9を使って1〜13の自然数を作れる。)
n変数のPz関数の最大値をPmax(n)とする。
例:Pmax(1)=2(Pz(1)=2)
Pmax(2)≧14(Pz(4,9)≧14)
Pmax(n)が常に有限の値になるかはわからないが、
有限になる場合Pmax(a+b+1)>Pmax(a)×Pmax(b)が成り立つので
指数関数以上にはなる。テトレーションレベルに届くだろうか。 T[0] : On
T[a+1] : (On, T[a]) -> T[a]
T[a] : (On, T[a[n]]) -> T[a[n+1]] 多変数アッカーマン関数の
Ak(a.b.c、、、、)
を、
A[0]k(a.b.c、、、、)
とかくことにする。そして、
A[n+1]k(a.b.c、、、、)は、普通の多変数アッカーマン関数のAk(□.a)を
A[n+1]k(□.a)=A[n]k(a.a.〜(a個)〜.a.a)とする。
これはどんな感じでしょうか
>>206をそれらしく言うと、
X : 0個以上の0以上の整数
Y : 0個以上の0
a, b : 0以上の整数
A[n+1]k(a.b.c、、、、) すみません途中でおわってしまいました。
A[a]k(X,b+1,0)=A[a]k(X,b,1)
A[a]k(X,b+1,c+1)=A[a]k(X,b,A[a]k(X,b+1,c))
A[a]k(X,b+1,0,Y,c)=A[a]k(X,b,c,Y,c)
A[0]k(Y,a)=a+1
A[a+1]k(Y,b)=A[a]k(b,b,〜b個〜,b,b) >>166
引数xがある数cを超えるとそれ以降はf(x)がg(x)より大きくなる、
∃c∀x(c<x→f(x)>g(x))
つまり「fがgを支配する」をf>gと書くとすると
順序数α,βに対して、
α>β → f_α>f_β
が言えるような順序数から関数への関数を作れば、
無限(=順序数)の大きさの序列がそのまま
有限の数の大きさの序列に直結するような関数ができるわけで
それが []=1
[][]=2
[][][]=3
[[]]=[][][]...[]=ω
[[]][]=ω+1
[[]][][]=ω+2
[][[]]=[[]][][][]...[]=ω×2
[][][[]]=[][[]][][][]...[]=ω×3
[[]][[]]=[][][]...[][[]]=ω^2
[[]][[]][[]]=ω^3
[[][]]=[[]][[]]...[[]]=ω^ω=ω^^2
[[][]][[][]]=ω^(ω×2)
[[][][]]=[[][]][[][]]...[[][]]=ω^ω^2
[[][][][]]=[[][][]][[][][]]...[[][][]]=ω^ω^3
[[[]]]=[[][][]...[]]=ω^ω^ω=ω^^3
[[[][]]]=ω^ω^ω^ω=ω^^4
[[[[]]]]=ω^ω^ω^ω^ω=ω^^5
[[[[][]]]]=ω^ω^ω^ω^ω^ω=ω^^6
{}=[[[...[[[]]]...]]]=ε_0=ω^^ω {}[]=(ω^^ω)+1
[]{}={}[[[...[[]]...]]]=(ω^^ω)×2
{}{}=(ω^^ω)^2
{[]}=(ω^^ω)^ω
{[]}{[]}=(ω^^ω)^(ω×2)
{[][]}=(ω^^ω)^(ω^2)
{[][]}{[][]}=(ω^^ω)^(ω^2×2)
{[][][]}=(ω^^ω)^(ω^3)
{[[]]}={[][][]...[]}=(ω^^ω)^(ω^ω)
{[[]]}{[[]]}=(ω^^ω)^(ω^ω×2)
{[[]][]}=(ω^^ω)^(ω^(ω+1))
{[][[]]}=(ω^^ω)^(ω^(ω×2))
{[[]][[]]}=(ω^^ω)^(ω^ω^2)
{[[]][[]][[]]}=(ω^^ω)^(ω^ω^3)
{[[][]]}=(ω^^ω)^(ω^ω^ω)
{[[[]]]}=(ω^^ω)^(ω^ω^ω^ω)
{[[[][]]]}=(ω^^ω)^(ω^ω^ω^ω^ω)
{{}}={[[[...[[]]...]]]}=(ω^^ω)^(ω^^ω)=(ω^^ω)^^2
{{}{}}=(ω^^ω)^(ω^^ω)^(ω^^ω)=(ω^^ω)^^3
{{{}}}=(ω^^ω)^^4
{{{}{}}}=(ω^^ω)^^5
「」={{{...{{}}...}}}=(ω^^ω)^^ω >>211,>>212って法則性がいまいちわからん。
>>213にはわかってるようだから元ネタがあるんだろうか。 >>215
所々小細工はしてあるけど本質的にはヒドラゲームとほぼ変わらない。
あとプログラム読めないからわからないけど>>5もほぼ同じかと。 なんかでかい数作るのとでかい順序数作るのが同じに感じる 順序数の大きさで大きな関数が作れる方法があるから仕方がない
もっというと順序数のどういう部分が巨大数を生んでいるのかを考えると順序数以外に大きな関数が作れる方法がみつかるかも 順序数の呪縛からはどこまでいっても逃れられないと思う。 なぜなら大きいということはどういうことかその本質を順序数が表しているから。
グラハム数みたいに何かの条件を満たす数が偶然大きくなるというこはあるかもしれないが。 さすがに「大きいということはどういうことか」までは言ってなくて、
「かくかくしかじかの既存の演算の有限回の繰り返しで追いつけない最小の数という定義」
という「大きさを求めるための一手法」を使っているだけであって、
その隙間にこそ答えがあるんじゃないかと思う。 関数同士の「支配する」という法則を使って後で引数に数を入れる手法の範囲で考えている限りは順序数と対応が付きそう >「かくかくしかじかの既存の演算の有限回の繰り返しで追いつけない最小の数という定義」
>という「大きさを求めるための一手法」を使っているだけであって、
再帰順序数はそういう解釈でいいけどただ単に可算順序数と言う場合は
大きさの本質を表しているという解釈でいいと思う。
「順序数の束縛からは逃れられない」で納得がいかないのであれば、逆に
「大きいということはどういうことか」を分かりやすく見えるように
して説明するものが順序数ということでいいかも。 有限約束ゲームとかレイバーのテーブルとかもサブキュービックグラフ数みたいに
関連する何かを順序数に対応させられるのだろうか。 順序数=自然数の超次元リスト説
0=(0)
1=(1)
ω=(0,1)
ω+1=(1,1)
ω^2=(0,0,1)
ω^ω=((0)1) 結局ヒドラもベクレミシェフの虫もFGHもグッドスタイン数も、
・順序数と同じ木構造を作れること
・超限順序数の部分を引数 n に比例して展開することで
「引数 n さえ増やせば自分より小さい順序数による関数を必ず超えられる」
という性質を付加すること
という部分をいろんな実装を使って実現してるだけだね 再帰的到達不能順序数(可算)なんたらとか出てきてもうめちゃくちゃだよって感じだけど、
これはω_αをどうこうした奴のω_α^CK版なの?
あと
到達不能→マーロ→弱コンパクトって行ってるけどこれらの関係って綺麗に決まってるの?
1→2→3みたいな感じで どうやらバシク行列システムがローダー数よりでかいことを証明しようとしている模様
http://ja.googology.wikia.com/wiki/ユーザーブログ:KurohaKafka/型付きラムダ計算の強さ CoCの対角化でψ(ε_{M+1})
強配列表記はC(C(C(Ω_3+1,0),0),0)よりは弱い?
フリードマンのあれはCを超えてZFC+膨大基数くらいの強さ
バシクはすくなくともCを超えた強さ
loader.cは思ったより弱い? しばらく前からバシク行列の解析結果が更新され続けてる。
古い結果よりだいぶ弱くなって見たことない順序数表記が出てきた。
今度はどこでCを超えるんだろう。 順序数版急増加関数的なやつは条件P_αを満たすβ番目の順序数みたいな感じで定義すればいいと思った loader.c<フリードマンの有限ゲーム<強配列表記<Taranovsky's C 順序数崩壊関数版φ関数
多変数φ関数よりちょっと強い
Ωは0,Ω,+,φ関数の有限の組み合わせで表せない最初の順序数、ただしこの組み合わせの一番外側のφ関数の第二引数はΩより小さい
C_0(α,β)={0,β}
C_n+1(α,β)={γ+δ,φ(η,γ),φ(α,ξ) | γ,δ,ξ∈C_n(α,β); η∈α; ξ∈β}
φ(α,β)=∪[n<ω] C_n(α,β)
φ(0,0)=1
φ(0,1)=ω
φ(1,0)=ε_0
φ(0,ε_0)=ε_0*ω
φ(0,ε_0*ω)=ε_0^ω
φ(Ω,0)=Γ_0
φ(Ω^ω,0)=θ(Ω^ω)
φ(φ(1,Ω),0)=θ(ε_(Ω+1))
φ(0,Ω)=Ωω
φ(0,Ωω)=Ω^ω wikiaの欲張りクリーク列
出典の定義を見るに「(y,2m)はGの辺ではない」という部分は(y,x[2m])の間違い
じゃなかろうか。
そうだとするとm=k+1のときにy=x[2]となり、(y,x[2m])がGの辺ではないことが
xがクリークであるという条件に反するため矛盾。よって以上の関数は2k+1に
しかならないということになってしまう・・・ アッカーマン関数が頭から離れられないから小さいかもしれないけどアッカーマンでやってみる
Xは0個以上の0以上の整数
Yは0個以上の0
a,b,c,dは0以上の整数
AA(a,b:X,c+1,0)=AA(a,b:X,c,1)
AA(a,b:X,c+1,d+1)=AA(a,b:X,c,(AA(a,b:X,c+1,d)))
AA(a,b:X,c+1,0,Y,d)=AA(a,b:X,c,d,Y,d)
AA(a+1,0:Y,b)=AA(a,1:Y,b)
AA(0,a+1:Y,b)=AA(0,a:b,b,b【b回】b,b)
AA(a+1,b+1:Y,c)=AA(a,(AA(a+1,b:c,c,c【c回】c,c)):Y,c)
AA(0,0:Y,a)=a+1 バシクが使ってるψ関数ってどういう定義なの・・
ε_0がψ_0(0)じゃなくてψ_Ω(0)になってるけど 関数を入れ子にしたらψについてる順序数が入る意味かと >>241 の計算例
AA(2,2:2,2)=AA(2,2:1,(AA(2,2:2,1)))=AA(2,2:1,(AA(2,2:1,(AA(2,2:2,0)))))=AA(2,2:1,(AA(2,2:1,(AA(2,2:1,1))))) ■ このスレッドは過去ログ倉庫に格納されています