巨大数探索スレッド12 [無断転載禁止]©2ch.net
レス数が1000を超えています。これ以上書き込みはできません。
ヒドラゲームを拡張してみました。
rubyスクリプトです。
http://ideone.com/lg6Udg
通常のヒドラゲームのノードは1種類しかないけどそれを複数種類にしました。
ノードはランクという名前の整数を一つ持っています。
そして通常のヒドラゲームのノードをコピーする操作の後で、
「第n段階で、ランクがrのノードが切り離されたら、ランクがr-1のノードで構成された高さがnのツリーが追加される。」
という操作を追加します。
これにより高さが増えなかった従来のヒドラゲームにくらべて高さも増えることになります。
なかなか自然で強力な拡張が出来たのでは?と思っています。
ちなみにスクリプトは第n段階から第n+1段階に上がるときのインクリメントをコメントアウトしています。
興味がある方はコメントアウトを外してみてください。 >>5を超ヒドラと名付けよう。
そしてランクを整数ではなく超ヒドラノードに拡張することによって真・超ヒドラへと進化します。 ┌──────────┐
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ ↓↓↓↓↓↓↓↓ │
│--------------------│
│ 広 告 │
│--------------------│
│ │
└──────────┘
その他広告を消したかったらなんjorVIPへ
泥 ADGUARD(追加設定あり)他
林檎 adblock(1/24まで無料)(追加設定あり)他
これ他の板に拡散してくれ そのヒドラの大きさはΓ0に届くかどうかぐらいになると思う 返信、早!
もしかして既出でしたか?T△T
既出でも全然おかしくないですが… しかしこれだけデカい関数を定義してもビジービーバーには遥か届かないというね。
ビジービーバー怖すぎw 「停止する特定のアルゴリズム」より、「適当なアルゴリズムの内停止するもの」の上界の方が強いのは当然。 ふぃっしゅ氏著巨大数入門なんてあんのかよ。
時代は進んでるな。 前スレの議論は「定義」という言葉の意味より定義「した」とか定義「できた」とか
定義「できたことを確認した」とか、助詞的な部分で食い違ってるだけっぽい。 超次元空間以降が巨大数論以外で使われる日は来るのだろうか?
超弦理論で11次元がどうこういうみたいに。 ω_α^{CK}→αの次は、順序数崩壊関数ψ^{CK}でいいのかな?φ^{CK}(ω,0)=ψ_I^{CK}(I^ω)なら、ψ_I^{CK}(ω_{I+1}^{CK})は凄くなりそう。 (#,α)[n]=(#,α[n])
(#,0)=(#)+1
他はベクレミシェフの虫と同じ
(1)=ω
(ω)=((1))=ε_0
(ω,ω)=ε_1
(ω+1)=((1,0))=ε_ω
(ω×2)=((1,0,1))=ε_ε_0
(ω^2)=((1,1))=ζ_0
限界は多分ψ_0(Ω_ω) >>17を「Τ_0関数」と名付け、Τ_0関数の中でネスト構造を作る働きをする
Τ_1関数を考える。
Τ_1(0)=1
Τ_0(Τ_1(0))=ω
Τ_0(Τ_1(0,0))=Τ_0(Τ_0(Τ_1(0)))
Τ_0(Τ_1(0,0,0))=Τ_0(Τ_0(Τ_0(Τ_1(0))))
Τ_0(Τ_1(1))=Τ_0(α)→αの最初の不動点
Τ_0(Τ_1(1),Τ_1(0,0,0))=Τ_0(Τ_1(1),Τ_0(Τ_1(1),Τ_0(Τ_1(1),1)))
Τ_0(Τ_1(1),Τ_1(1))=Τ_0(Τ_1(1),α)→αの最初の不動点
Τ_0(Τ_1(1,0,0,0))=Τ_0(Τ_1(1)+Τ_0(Τ_1(1)+Τ_0(Τ_1(1)+1)))
Τ_0(Τ_1(1,0,1))=Τ_0(Τ_1(1)+α)→αの最初の不動点
Τ_0(Τ_1(Τ_1(1)))=Τ_0(Τ_1(α))→αの最初の不動点
厳密な定義は未完成。
同様にΤ_2関数とかΤ_Τ_0(1)関数、Τ_Τ_1(1)関数などを考えることができる。 巨大数を生成するシステムの評価点
表現の分かりやすさ
・使用する字母集合の長さとか構造とか
プログラムの長さ
・これはプログラミング言語にもよる
応用の効きやすさ
・BEAFのもろもろの配列とか 歴史からみるとそうなるのか。
逆にハイパー演算子の拡張でないシステムってなに? 巨大数を作る関数の基本が既存の計算の拡大反復だし、必然とhyper関数と戦術が結果的ににてくるんじゃない
収斂進化的な ふぃっしゅってもろアッカーマン(≒ハイパー演算子)の拡張じゃなかったか? 以下の性質を満たすグラフを「サブツリー」と命名する。
・すべての変に向きがある有効グラフである。
・辺とその向きに従って頂点間を移動するとき、
1回以上の移動で元の頂点に戻ってこられる頂点は1つもない。
・辺とその向きに従って頂点間を移動するとき、
まったく移動できない頂点がただ一つ存在する。
ST(n)を以下の性質を満たすサブツリーの列T_kの最大長とする。
・T_kの頂点の個数と次数はn+k以下である。
・列の中には位相同型的埋め込み可能 である組は1つもない。
関数として成立するかはわかりませんが、成立する場合
弱いツリー数列よりは確実に強くなるはずです。
使えるグラフはシンプルサブキュービックグラフ数より多い(濃度はたぶん同じ)
はずですが、越えられるかは不明です。 >>17の計算方法がよくわからんのやけど。
(1)=(0)(1)=ωでおk? Τ_0(ω)=ε_0
Τ_0(ω,ω)=ε_1
Τ_0(ω,ω,ω)=ε_2
Τ_0(ω+1)=ε_ω
Τ_0(ω+1,ω)=ε_(ω+1)
Τ_0(ω+1,ω,ω+1)=ε_(ω×2)
Τ_0(ω+1,ω+1)=ε_(ω^2)
Τ_0(ω+2)=ε_(ω^ω)
Τ_0(ω+3)=ε_(ω^ω^ω)
Τ_0(ω×2)=ε_ε_0
Τ_0(ω×3)=ε_ε_ε_0
Τ_0(ω^2)=ζ_0=ψ_0(Ω)
Τ_0(ω^2,ω)=ψ_0(Ω+1)
Τ_0(ω^2,ω,ω^2)=ψ_0(Ω+ψ_0(Ω))
Τ_0(ω^2,ω+1)=ψ_0(Ω+ψ_0(Ω)×ω)
Τ_0(ω^2,ω+1,ω^2)=ψ_0(Ω+ψ_0(Ω)^2)
Τ_0(ω^2,ω+2,ω^2)=ψ_0(Ω+ψ_0(Ω)^ψ_0(Ω))
Τ_0(ω^2,ω×2)=ψ_0(Ω+ψ_0(Ω+1))
Τ_0(ω^2,ω^2)=ψ_0(Ω×2)
Τ_0(ω^2+1)=ψ_0(Ω×ω)
Τ_0(ω^2+ω)=ψ_0(Ω×ε_0)
Τ_0(ω^2×2)=ψ_0(Ω×ψ_0(Ω))
Τ_0(ω^3)=ψ_0(Ω^2)
Τ_0(ω^3,ω^2)=ψ_0(Ω^2+Ω)
Τ_0(ω^3,ω^2,ω^3)=ψ_0(Ω^2×2)
Τ_0(ω^3,ω^2+1)=ψ_0(Ω^2×ω)
Τ_0(ω^3,ω^3)=ψ_0(Ω^3)
Τ_0(ω^3+1)=ψ_0(Ω^ω)
Τ_0(ω^ω)はまだ遠い。 ベクレミシェフの虫と同じなら(1)は1にしかならんけど。 Τ_1(1)=Ωとすると、Τ_1(ω)=Ω×ε_0 にしかならない。
Τ_1関数は意外としょぼいかも。
>>31
FGHによる評価のことですか?
Τ関数は順序数から順序数への関数なのでFGHとは無関係です。 ベクレミシェフの虫の話題が出たからプログラム組んでみましたが面白いですねこれ。
最初のリストが[2]ならすぐ終わるのに[2,0]ってしただけで計算終わんないです。
リストの末端が[0,2]のときはstep数をハイパー(step+1)演算子に作用させて大きくさせるって感じなんですかね。
Googologywikiにもあまり詳しく書いてないのはなんででしょう。 ベクレミシェフの虫と同じなら
T_0(n)はnの値に関係無く1にしかならないと思う。 34>>
何を勘違いされているかわかりませんが、とりあえずΤ_0(ω)まで書いておきます。
Τ_0(0)=1
Τ_0(0,0)=2
Τ_0(0,0,0)=3
Τ_0(1)=Τ_0(0,0,0,…)=ω
Τ_0(1,0)=ω+1
Τ_0(1,0,1)=Τ_0(1,0,0,0,…)=ω×2
Τ_0(1,0,1,0,1)=ω×3
Τ_0(1,1)=Τ_0(1,0,1,0,1,0,…)=ω^2
Τ_0(1,1,0)=ω^2+1
Τ_0(1,1,0,1)=ω^2+ω
Τ_0(1,1,0,1,1)=ω^2×2
Τ_0(1,1,1)=Τ_0(1,1,0,1,1,0,1,1,…)=ω^3
Τ_0(2)=Τ_0(1,1,1,1,…)=ω^ω
Τ_0(2,0)=ω^ω+1
Τ_0(2,0,2)=ω^ω×2
Τ_0(2,1)=ω^(ω+1)
Τ_0(2,1,2)=ω^(ω×2)
Τ_0(2,2)=ω^ω^2
Τ_0(3)=ω^ω^ω
Τ_0(4)=ω^ω^ω^ω
Τ_0(ω)=Τ_0(n)=ε_0 >>33
詳しく書いてないってどういうこと?
定義と増加率と例が書いてあるんだから、十分じゃないの?
不十分だと思うなら、自分でどんどん書き足せばいい。 多次元配列は分かるけどテトレーション配列が分かりません。どういうの >>37
プログラムの動作確認のための例が2つじゃ心許なかったって意味です。
そうですね、暇な時にいくつかの気付きを精査してから纏めて書き足してみます。 テトレーション配列って俺もよくわからん。
だれか分かりやすい解説たのむ。 多次元配列の次元を多次元配列であらわすのがテトレーション? >>41
こんなに綺麗に書けるんですね。もうちょっと勉強しなきゃって感じです。 ある言語を対角化した関数を記述できる言語を対角化したらより強い関数ができる、
というのは計算可能レベルでもそうな訳で、当たり前と言えば当たり前か。 線形配列…{a,a,a,a,a…}
高次元配列…{a,b(n)2}
超次元配列…{a,b(n,n,n,n…)2}
テトレーション配列…{a,b(((…((1)1)…1)1)1)2}
BEAFで厳密に定義できてるのってどこまでだっけ? あぁ、FOOTがFOSTに一つの真理述語を追加した強さだと言うのは
SKIコンビネータに神託コンビネータを追加するようなもんなのか。
神託式の追加は神託機械の延長線上にあるようなイメージ。つまりF4とΞ関数の違いみたいな。
とここまで書いて思ったけどそうなるとΞ関数の強さはI^CKくらい? テトレーション次元配列ちょっと分かった。
スカラーで位置が表せるのが線形配列。
例えば(a,b,c)でbの位置は2番目。
線形配列で位置が表せるのが多次元配列。
例えば
[a,b,c
d,e,f
g,h,i]でfの位置は(2,3)。
そして多次元配列で位置が表せるのがテトレーション配列。
たとえばサイズが
[2,2
2,2]のテトレーション配列(位置と同じくサイズも多次元配列で表せる)は16個の要素を持つ。 1辺が10の100次元だと10^100個の要素があるけど、
1辺が10で100テトレーションすると10^^100個の要素になる、ということがわかればよくて、
実際にその要素がどのように並ぶのかを頭の中で想像するのは大変 多次元配列で位置を表せるのはX^X^Xまででテトレーション空間には
届かないんじゃなかろうか? あ、テトレーション次元じゃなくて超次元の話をしちゃってたのかな Googology Wikiのベクレミシェフの虫の[2]のステップ4ゼロ足りなくない? g=[1,0,1,0],b=[0]
Step 4 だから、next(W,m)=g+b+b+b+b+b
で、いいんでないの Τ_0(ω^3+1)=ψ_0(Ω^ω)
Τ_0(ω^3+1,ω^3)=ψ_0(Ω^(ω+1))
Τ_0(ω^3+1,ω^3,ω^3+1)=ψ_0(Ω^(ω×2))
Τ_0(ω^3+1,ω^3+1)=ψ_0(Ω^ω^2)
Τ_0(ω^3+2)=ψ_0(Ω^ω^ω)
Τ_0(ω^3+ω)=ψ_0(Ω^ε_0 )
Τ_0(ω^3+ω,ω^3)=ψ_0(Ω^(ε_0+1))
Τ_0(ω^3+ω,ω^3+ω)=ψ_0(Ω^ε_1)
Τ_0(ω^3+ω^2)=ψ_0(Ω^ψ_0(Ω))
Τ_0(ω^3+ω^2,ω^3+ω)=ψ_0(Ω^ψ_0(Ω+1))
Τ_0(ω^3+ω^2,ω^3+ω,ω^3+ω^2)=ψ_0(Ω^ψ_0(Ω+ψ_0(Ω)))
Τ_0(ω^3+ω^2,ω^3+ω^2)=ψ_0(Ω^ψ_0(Ω×2))
Τ_0(ω^3+ω^2+1)=ψ_0(Ω^ψ_0(Ω×ω))
Τ_0(ω^3+ω^2+ω)=ψ_0(Ω^ψ_0(Ω×ε_0))
Τ_0(ω^3+ω^2×2)=ψ_0(Ω^ψ_0(Ω×ψ_0(Ω)))
Τ_0(ω^3×2)=ψ_0(Ω^ψ_0(Ω^2))
Τ_0(ω^3×2,ω^3×2)=ψ_0(Ω^ψ_0(Ω^3))
Τ_0(ω^3×2+1)=ψ_0(Ω^ψ_0(Ω^ω))
Τ_0(ω^3×3)=ψ_0(Ω^ψ_0(Ω^ψ_0(Ω^2)))
Τ_0(ω^4)=ψ_0(Ω^Ω)
Τ_0(ω^ω)かΤ_0(ε_0 )あたりで「FGH with transfinite ordinals」
と一致するようになるかも。 詳しく調べてはないがΤ_0(ω^3,ω^2,ω^3)=ψ_0(Ω^2×Ω×ψ_0(Ω^2))じゃないの 間違え
Τ_0(ω^3,ω^2,ω^3)=ψ_0(Ω^2+Ω×ψ_0(Ω^2)) 久しぶりに見たらまだあったのか
しかも2月3日に巨大数論更新されてるし >>55
計算しなおしたところ、確かにそうなりました。
Τ_0(ω^4)=ψ_0(Ω^3) となり、
Τ_0(ω^ω)=ψ_0(Ω^ω) になりそうです。
「FGH with transfinite ordinals」と同程度
(じっさいはFGHよりハーディー階層に近い)なら
Τ_0(ω^(ω+1))=ψ_0(Ω^Ω) になるはず。 新しい順序数崩壊関数
Ρ_0(Ρ_0(Ω))=ψ_0(Ω)
Ρ_0(Ρ_0(Ω)×2)=ψ_0(Ω×2)
Ρ_0(Ρ_0(Ω)^2)=ψ_0(Ω^2)
Ρ_0(Ρ_0(Ω)^Ρ_0(Ω))=ψ_0(Ω^Ω)
Ρ_0(ε_(Ρ_0(Ω)+1))=Ρ_0(Ρ_0(Ω+1))=ψ_0(ε(Ω+1))=ψ_0(ψ_1(0))
Ρ_0(Ρ_0(Ω+Ρ_0(Ω)))=ψ_0(ψ_1(Ω))
Ρ_0(Ρ_0(Ω+Ρ_0(Ω×2)))=ψ_0(ψ_1(Ω_2))
Ρ_0(Ρ_0(Ω+Ρ_0(Ω×2+Ρ_0(Ω×3))))=ψ_0(ψ_1(ψ_2(Ω_3)))
Ρ_0(Ρ_0(Ω×ω))=ψ_0(Ω_ω)
Ρ_0(Ρ_0(Ω×Ρ_0(Ω)))=ψ_0(Ω_Ω)
Ρ_0(Ρ_0(Ω^2))=ψ_0(ψ_Ι(0))
定義は未完成。
Ρ_0(Ρ_0(Ρ_0(Ω)))=ψ_0(Ω)とすればもっと強くなり、
同じ方法でさらに強くできる。 >>59
Taranovsky's Cを参考にしたので(定義を知らないので見た目をまねただけですが)
もしかしたら似たような性質があるかもしれません。 どうやらΤ_0(ω^(ω+1))=ψ_0(Ω^(ω+1))になるようです。
そうなるとΤ_0(Τ_1(1))=ψ_0(Ω^Ω)になり、
Τ_1関数の限界もあまり大きくならなさそうです。 Τ関数の定義を微調整。
Τ_1(#,0)=Τ_1(#)+Ω
Τ_0(#,0)=Τ_0(#)+ω
Τ_0(Ω)=ψ_0(Ω^Ω)
Τ_0(Ω,0,Τ_0(Ω))=ψ_0(Ω^Ω)×2
Τ_0(Ω,0,Τ_0(Ω),1)=ψ_0(Ω^Ω)×ω
Τ_0(Ω,0,Τ_0(Ω),ω)=ψ_0(Ω^Ω+1)
Τ_0(Ω,0,Τ_0(Ω),Τ_0(Ω))=ψ_0(Ω^Ω×2)
Τ_0(Ω,0,Τ_0(Ω)+1)=ψ_0(Ω^Ω×ω)
Τ_0(Ω,0,Τ_0(Ω,0,Τ_0(Ω)))=ψ_0(Ω^Ω×ψ_0(Ω^Ω))
Τ_0(Ω,0,Τ_0(Ω,0,Τ_0(Ω),1))=ψ_0(Ω^(Ω+1))
Τ_0(Ω,0,Ω)=ψ_0(Ω^(Ω×2))
Τ_0(Ω,0,Ω,0,Ω)=ψ_0(Ω^(Ω×3))
Τ_0(Ω,1)=ψ_0(Ω^(Ω×ω))
Τ_0(Ω,1,0,Ω,1)=ψ_0(Ω^(Ω×ω×2))
Τ_0(Ω,1,1)=ψ_0(Ω^(Ω×ω^2))
Τ_0(Ω,1,Τ_0(Ω))=ψ_0(Ω^(Ω×ψ_0(Ω^Ω)))
Τ_0(Ω,1,Ω)=ψ_0(Ω^Ω^2)
Τ_0(Ω,2)=ψ_0(Ω^Ω^ω)
Τ_0(Ω,ω)=ψ_0(ε_(Ω+1))=ψ_0(ψ_1(0))
Τ_0(Ω,ω,Ω)=ψ_0(ψ_1(Ω))
Τ_0(Ω,ω+1)=ψ_0(ψ_1(Ω×ω))
Τ_0(Ω,ω+2)=ψ_0(ψ_1(Ω^ω))
Τ_0(Ω,ω×2)=ψ_0(ψ_1(ψ_1(0)))
Τ_0(Ω,ω^2)=ψ_0(ψ_1(Ω_2)) 巨大数を生成するシステムを作る人工(でなくてもいいけど)知能的なやつ
基本
とにかく不特定多数のプログラムを書きまくる。
実行して停止したものから最終的に出力された数を一旦全て採用
大きさを比較して小さい方は捨てる。
ここから自力でいかに効率をあげられるかが勝負どころ。
健全で停止するプログラムを作った場合は、結果だけ求めるのであれば必要ないが、
健全で停止することの証明まで用意してもらうのが望ましい、
というか知識の共有のためには必要不可欠 最終的に出力された数を保存しようと思ったらグーゴルプレックスでも無理でしょ 指数を導入すればいいだけ
表記法も自動で学習、獲得する感じで グーゴルプレックスそのものは指数で書けるけど、グーゴルプレックス程度の
大きさの指数ではぴったりとかけないような数字を書こうとすると、
どうしても10進数で計算する必要があるよ いずれにせよ「実際に計算する」時点でメモリと計算時間の「現実的制限」があるよ 原子の数は限りがあるけど、電場・磁場・重力場とかのパターンとかなら無限の表現ができるよね。
それで計算できたりしないのかな。
一桁上がる毎に半分のフォントにすれば全角に無限桁入るはず
テオヤンセン機構みたいな感じで電磁力の相互作用で計算できるとすごくいい 1万ビット程度の素因数分解もできないのに、巨大数を素直に計算しようなんて無謀すぎる 「将棋の完全解析をするプログラム」ですらできないわけなので
実行して停止したものから最終的に出力された数
というアプローチだとクラス3の数が限界だよ 宇宙が有限で最小の長さがあるという理論が有力である以上、無限のパターンは無理だろ なんだか語弊のある書き方をしてしまったが、実際には巨大数を生成する
プログラムを記憶すればいいのであって
巨大数そのものは記憶しなくてよい、現実的に不可能だし。
人工知能に限らず普通にグーゴロジストの知能にとっても課題となるが、
つぎの二つを学習しなければならない。
効率的な評価方法
・最低限、プログラムを最初から最後まで起動させなくても大きさを
見積もれるようになってほしい。
より強力なシステムの発見
・(現実的な時間内に)発見したシステムが強力であればあるほど、その発見者は
より自由な意志をもっている(ように見える)
計算不可能レベルは言語そのものを開発して殴り会うからまた事情が違ってくる。 なにをもって「大きさを見積もった」とするかだな
実際には「停止するとわかったものの中で最大」がわかればいいので、
ビジービーバー候補である「優勝マシン」の探索を、いかに効率的にしていくか、
という問題に帰着するのかな 簡単な例をあげれば、実際に計算しなくても、
3+3と3^^3を比較してテトレーションのほうが強力だから
3^^3の方が大きい、と評価する感じ、評価方法が健全であることの証明を添えて。
ここまで書いて気付いたけど、この場合の証明って要するに説明するってことだな。 停止するか確認じゃなくてするか証明させればいいじゃん
本当にやったら人間には理解できないのが出てきそうで期待 そもそもみんな証明することしか考えてなかっただろ
ベクレミシェフの虫も、ヒドラも、グッドスタイン数列も、サブキュービックグラフ数も、
停止することを証明するし、でかいことも証明する 3+3と3^^3 程度の複雑さだったらいいけど、
>>66 の「不特定多数のプログラムを書きまくる」というアプローチで期待していることは、
なんかとても複雑なことをやっていてよくわからないけどでかい数ができることを
期待してるわけでしょ。そんなものの大きさをどう評価するかという問題なわけで。
評価するためには、なんらかの物差しとなる「評価する関数」が必要となる。
そして、結局はその「評価する関数」が整然とした関数なのであれば、はじめから
その「整然とした関数」で巨大数を作ればいいので、
「不特定多数のプログラムを書きまくる」というアプローチの出番はない。 とりあえずは、バシク行列数を出力するプログラムと、
ローダー数を出力するプログラムの大小関係を
どうやって比較するのでしょうか >>82
最初から効率よく評価する方法を知っていればいいですけど、
自然数の公理以外は何も知らない状態から始めることを前提としているので。
それに新しい発見のために従来よいとされているやり方から離れるランダムな
要素は多少必要かと。 ランダムな要素で語弊がありそうなので補足
効率のいいやり方を学習したら不特定多数のプログラムを書きまくる必要はありません。 Τ_ω未満ではΤ_0(Τ_1(Τ_2(Τ_3(…))))という構造が出てきて、原始数列の計算法を使うことになる。
Τ_ω以上を定義するにはΤ_0関数の原始数列バージョンを作るか虫のルールだけで計算できるように
Τ_1の計算法を変える必要がある。
後者の場合Τ_1(0)=ψ_0(Ω^Ω) なのにΤ_1(Τ_1(0))≠Τ_1(ψ_0(Ω^Ω))みたいに変なことになるが
前者より定義は簡単で強さも多分変わらない。 サバンナで一番強い動物は何か、ライオンかゾウかそれとも蚊かって話し合ってるときに「答えはサバンナで一番強い動物だ」って言ってるようなものだな。
その命題は偽じゃないけど情報量がないというかそういう答えは求めてない。その動物名が知りたくてみんなやっているわけで。
ラヨ数とかビジービーバーとかもそういうけがある。いいよ、別に手段としてラヨ数というアプローチを使っても。でもそれで一番だと分かったその関数が何だったのかを知りたい >>47
ちょっとC++でソース書いてみたがこんな感じ?
ここからどう巨大数を生み出せばいいかな?
#include<map>
using namespace std;
template<int N>
class T;
template<int N>
bool operator<(const T<N> &a,const T<N> &b);
template<int N>
class T{
public:
map<T<N-1>,int> val;
};
template<int N>
bool operator<(const T<N> &a,const T<N> &b)
{
return a.val<b.val;
}
template<>
class T<0>{
public:
map<int,int> val;
};
int main()
{
T<0> t0;
T<1> t1;
T<2> t2;
t0.val[0]=1;
t1.val[t0]=1;
t2.val[t1]=1;
} 「サバンナで一番早い動物」の答を求めてるんじゃなくて、
答に至るまでの考え方や知能のはたらき方といった過程を
求めてるんだけど、過程に興味ないと言われてしまえばそれまでなのだわ。 計算不可能レベルでは一番の存在を示すことはできても
それが何であるかを知ることができなくなってきますし・・・
主に英語版の住民がやってることだが、計算不可能レベルにもそれなりに需要があるわけで、
みんな具体的な動物名が知りたくてやってるというのは極論かと。 函数を比べるためにはそれよりも強い函数が必要になるんじゃないの?
でそんな函数があればそれを利用したもっと強い函数が出てきて・・・ BIG FOOT、BIG FOFT、Little Biggedonにはさらに次の議論を示唆する余地があって良いよね。有意義だと思う。
でも計算可能関数もいいよね。それは何だ。っていうのが見えてきて。 Τ_1(0)=ψ_0(Ω^Ω)
Τ_1(0,0)=ψ_0(Ω^Ω)×2
Τ_1(Τ_0(Τ_1(0)))=ψ_0(Ω^Ω)^2
Τ_1(Τ_0(Τ_1(0)),1,Τ_0(Τ_1(0)))=ψ_0(Ω^Ω)^3
Τ_1(Τ_0(Τ_1(0)),ω)=ψ_0(Ω^Ω+1)
Τ_1(Τ_0(Τ_1(0)),Τ_0(Τ_1(0)))=ψ_0(Ω^Ω×2)
Τ_1(Τ_0(Τ_1(0))+1)=ψ_0(Ω^Ω×ω)
Τ_1(Τ_0(Τ_1(0),1))=ψ_0(Ω^(Ω+1))
Τ_1(Τ_0(Τ_1(0),1,Τ_1(0)))=ψ_0(Ω^(Ω+ψ_0(Ω^Ω)))
Τ_1(Τ_1(0))=ψ_0(Ω^(Ω×2))
Τ_1(Τ_1(0),0,Τ_1(0))=ψ_0(Ω^(Ω×3))
Τ_1(Τ_1(0),1)=ψ_0(Ω^(Ω×ω))
Τ_1(Τ_1(0),1,Τ_1(0))=ψ_0(Ω^Ω^2)
Τ_1(Τ_1(0),2)=ψ_0(Ω^Ω^ω)
Τ_1(Τ_1(0),ω)=ψ_0(ψ_1(0))
Τ_1(Τ_1(0),ω,ω)=ψ_0(ψ_1(1))
Τ_1(Τ_1(0),ω,Τ_1(0))=ψ_0(ψ_1(Ω))
Τ_1(Τ_1(0),ω+1)=ψ_0(ψ_1(Ω×ω))
Τ_1(Τ_1(0),ω+2)=ψ_0(ψ_1(Ω^ω))
Τ_1(Τ_1(0),ω×2)=ψ_0(ψ_1(ψ_1(0)))
Τ_1(Τ_1(0),ω^2)=ψ_0(ψ_1(Ω_2))
Τ_1(Τ_1(0),ω^2,Τ_1(0))=ψ_0(ψ_1(Ω_2×Ω))
Τ_1(Τ_1(0),ω^3)=ψ_0(ψ_1(Ω_2^2))
Τ_1(Τ_1(0),Τ_1(0))=ψ_0(ψ_1(Ω_2^Ω_2))
Τ_1(Τ_1(0),Τ_1(0),ω)=ψ_0(ψ_1(Ω_2^Ω_2+1))
Τ_1(Τ_1(0),Τ_1(0),ω+1)=ψ_0(ψ_1(Ω_2^Ω_2×ω))
Τ_1(Τ_1(0),Τ_1(0),ω×2)=ψ_0(ψ_1(ψ_2(0)))
Τ_1(Τ_1(0),Τ_1(0),Τ_1(0))=ψ_0(ψ_1(ψ_2(Ω_3^Ω_3)))
ここまでが正しければΤ_1(Τ_1(0)+1)=ψ_0(Ω_ω)になるはず。
早く定義を完成させなければ。 Ρ関数はこうしたほうが強い。
Ρ_0(Ρ_0(Ρ_0(Ρ_0(…))))=Ρ_0(Ω)
Ρ_1(Ρ_1(Ρ_1(Ρ_1(…))))=Ρ_1(Ρ_1(Ω_2))
Ρ_2(Ρ_2(Ρ_2(Ρ_2(…))))=Ρ_2(Ρ_2(Ρ_2(Ω_3)))
Ρ_3(Ρ_3(Ρ_3(Ρ_3(…))))=Ρ_3(Ρ_3(Ρ_3(Ρ_3(Ω_4))))
さらにこれをΤ関数に応用すれば… >>133
Τ_1(Τ_1(0),Τ_1(0))
=ψ_0(ψ_1(Ω_2^Ω))
Τ_1(Τ_1(0),Τ_1(0),ω+1)
=ψ_0(ψ_1(Ω_2^Ω+ψ_1(Ω_2^Ω)×ω)) まったくの素人意見だが・・・
無限の広さがある碁盤と無限にある碁石を使って、画像認識みたいな
テクニックである程度自分で巨大数ではないかと思われるシステムを
作ることはできるだろう。
でもそれは統計的に「らしい」ものを作っただけでコンピュータが自分で
論理を組み立てたわけではないし、そういうわけで本当にまともなプログラム
になっている保証もない。
結構な確率で出来上がるところまでは行けるだろうが。 評価方法も考えなければならないことをうっかりしていた。
まぁあらかじめ教えておいたとしてもなお課題が残るということで。
>>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))))) 「計算不可能関数」と「いかなる計算可能関数よりも強い関数」を区別する呼び方はないのか >>241に触発されて
AM(fx;0,m)=fm
AM(fx;n+1,0)=AM(gx;n,1)
AM(fx;n+1,m+1)=AM(gx;n,AM(gx;n+1,m)
ここでgx=AM(fx;n,x) 「いかなる計算可能関数よりも強い関数」と「計算不可能関数」って同じやないの >>248
「空のテープから計算を始めて有限の時間で停止する2記号n状態チューリングマシンの個数」
をf(n)とする。
2記号n状態チューリングマシンの停止性問題は計算不可能なので
f(n)は「計算不可能関数」である。
しかし2記号n状態チューリングマシンは16^n個しかないため
f(n)<16^nが成り立ち、「いかなる計算可能関数よりも強い関数」ではない。 BB(n)が計算不可能で、いかなる計算可能よりも大きいから、BB(n)より強い物は計算可能よりも大きい 大きさそのものは大したことないかもしれないが雑魚な計算不能関数はない。
なぜならその計算不能関数をオラクルにすれば計算可能関数より大きい関数が定義できる可能性が開けるから。
どのような計算不能関数をオラクルにしても必ずビジービーバー相当の関数が定義できるかどうかは知らない。 >>253
計算不可能ならもっと上もある。最つよは、「ふぃっしゅ関数バージョン7」だと思う BB<n次BB<F4<ラヨ<F7<FOOT<Little Bigeddon<FOFT<Big Bigeddon(未登場) ぶっちゃけBBのデカさは想像がつかない。
もしかしたら人間にBBのデカさを想像することは原理的に不可能なのかもしれないw ところで>>249のf(n)って本当に計算不可能か? いや 16^n - f(n) 個のチューリングマシンが残るまで走らせれば停止性問題が解けることになるから、
計算不可能か。
失礼。 あと1/BB(x)とかBB(x) mod 2とか、いくらでもあるな。 ビジービーバー繋がりで一つ数を作ってみた。
「BB(x+1)-BB(x) が BB(x+2)-BB(x+1) よりも大きい」が成立するような、n番目のBB(x)を k(n) としたときの、 k^10(100)
ちなみに、k(1)は、BB(1)で、1になるけど、k(2)は、分からない BB mod 2が計算不能かどうかはそんなに自明じゃない wikiaのレイバーのテーブルの記事がおかしい気がするが、あれはZFC+階層内階層基数
の強さで今のところ大きさが見積もられている巨大数の中で最強ということに
なるんだろうか 元々ビッグビッゲドンあってこそのリトルビッゲドンじゃなかったの、知らんけど
計算不可能レベルでは存在を示すことはできても具体的にそれがどういう数かを知ることができない。
おそらく2階集合論を対角化して得られる関数や数にもなると、
存在はしてもその証明は不可能となってくる。
ビッゲドンやらは証明不可能レベルではない? 1階述語論理の性質から、1階の言語で記述されたそれぞれの数について存在するという証明
ができる無矛盾な体系が必ず存在する。もちろん数とされるもの自身が矛盾している場合は論外。
1階のシステムが強力であればあるほど証明が難しくなるが、それだけ巨大な数を生み出せるようになる。
これは計算可能レベルで計算が難しいほど巨大な数を生み出せることに対応する。
計算の難しさ自体を対角化することでビジービーバー関数が得られ、これはいかなる
計算可能関数より強力であり計算不可能である。
計算を証明に置き換えたものがラヨ関数となり、いかなる証明可能関数より強力であり、
ラヨ関数の全域性は1階では証明できない。
こんなところか A(0,a)=ω+a
A(b+1,0)=A(b,ω)
A(b+1,a+1)=A(b,A(b+1,a)) >>269じゃないけど少し計算してみよう
A(3.3)=A(2.A(2.A(2.A(2.ω))))=A(2.A(2.A(2.A(1.(2.ω-1)))))
ω-1って何 ωは第ニの0として、A(b+1.aω)=A(b.(a+1)ω)としてみようかな
=A(2.A(2.A(2.A(0.3ω))))=13ω
無知だから間違ってると思う A(0,0)=ω
A(0,1)=ω+1
A(0,2)=ω+2
A(0,3)=ω+3
A(0,ω)=ω+ω=ω×2
A(1,0)=A(0,ω)=ω×2
A(1,1)=A(0,A(1,0))=A(0,ω×2)=ω+ω×2=ω×(2+1)
A(1,2)=A(0,A(1,1))=A(0,ω×3)=ω+ω×3=ω×(2+2)
A(1,3)=A(0,A(1,2))=A(0,ω×4)=ω+ω×4=ω×(2+3)
A(1,ω)=ω×(2+ω)=ω^2
A(2,0)=A(1,ω)=ω^2
A(2,1)=A(1,ω^2)=ω×ω^2=ω^(2+1)
A(2,2)=A(1,ω^3)=ω×ω^3=ω^(2+2)
A(2,3)=A(1,ω^4)=ω×ω^4=ω^(2+3)
A(2,ω)=ω^(2+ω)=ω^ω
A(3,0)=A(2,ω)=ω^ω
A(3,1)=A(2,A(3,0))=A(2,ω^ω)=ω^(2+ω^ω)=ω^ω^ω
A(3,2)=A(2,A(3,1))=A(2,ω^ω^ω)=ω^(2+ω^ω^ω)=ω^ω^ω^ω
A(3,3)=A(2,A(3,2))=A(2,ω^ω^ω)=ω^(2+ω^ω^ω^ω)=ω^ω^ω^ω^ω
A(3,ω)=ε_0 >>272という事は
A(n,ω)=ω→ω→(n-1) という事になるのか。
A(n,n)=ω→(n+2)→(n-1) という事になりそう >>273
そうなりますね
多変数化
ω:最初の極限順序数
X:0個以上の(0以上の整数または順序数)
a,b,n:0以上の整数または順序数
x#y:y個のx
A(0#n,a)=ω+a
A(X,b+1,0#(n+1))=A(X,b,ω#(n+1))
A(X,b+1,0#n,a+1)=A(X,b,A(X,b+1,0#n,a)#(n+1)) >>274
三行目がなんかわけわからんが計算してみる
A(1,1,1)=A(1,0,A(1,1,0))=A(1,0,A(1,0,ω))=A(1,0,A(0,A(1,0,(ω-1)))) あれ、また間違えたかな。無理に計算して
A(1,0,A(0,A(0,・・・・・・【ω回】・・・・・・0,A(1,0,0)=A(1,0,A(0,A(0,・・・・・・【ω回】・・・・・・0,A(0,ω,ω) うーん >>275
3行目の例
A(1,2,3,4)=A(1,2,3,0#0,4)=A(1,2,2,0#0,A(1,2,3,0#0,3)#1)=A(1,2,2,A(1,2,3,3))
A(1,2,0,4)=A(1,2,0#1,4)=A(1,1,A(1,2,0#1,3)#2)=A(1,1,A(1,2,0,3),A(1,2,0,3))
A(1,0,0,4)=A(1,0#2,4)=A(0,A(1,0#2,3)#3)=A(0,A(1,0,0,2),A(1,0,0,2),A(1,0,0,2))=A(A(1,0,0,2),A(1,0,0,2),A(1,0,0,2))
A(1,0,0)=A(0,ω,ω)=A(ω,ω)=ω→ω→ω=ω→(ω)→(ω)を0回再帰的に入れ子
A(1,0,1)=A(0,A(1,0,0),A(1,0,0))=A(A(1,0,0),A(1,0,0))=A(ω→ω→ω,ω→ω→ω)=ω→(ω→ω→ω)→(ω→ω→ω)=ω→(ω)→(ω)を1回再帰的に入れ子
A(1,0,2)=A(A(1,0,1),A(1,0,1))=ω→(ω→(ω→ω→ω)→(ω→ω→ω))→(ω→(ω→ω→ω)→(ω→ω→ω))=ω→(ω)→(ω)を2回再帰的に入れ子
A(1,0,3)=A(A(1,0,2),A(1,0,2))=ω→(ω)→(ω)を3回再帰的に入れ子
A(1,0,ω)=ω→(ω)→(ω)をω回再帰的に入れ子
A(1,1,0)=A(1,0,ω)=ω→(ω)→(ω)をω回再帰的に入れ子
A(1,1,1)=A(1,0,A(1,1,0))=A(1,0,A(1,0,ω))=(ω→(ω)→(ω)をω回再帰的に入れ子)を(ω→(ω)→(ω)をω回再帰的に入れ子)回再帰的に入れ子 A(1,0,0)=ω→ω→ω
A(1,0,n+1)=ω→A(1,0,n)→A(1,0,n)
A(1,0,ω)=ω→A(1,0,ω)→A(1,0,ω) を満たす極限順序数をWとする
A(1,1,0)=A(1,0,ω)=W
A(1,1,1)=A(1,0,A(1,1,0))=A(1,0,A(1,0,ω))=A(1,0,W)=ω→W→W 274を自分流に拡張
定義
ω:最初の極限順序数
X:0個以上の(0以上の整数または順序数)
a,b,n,m:0以上の整数または順序数
@:順序数
x#y:y個のx
A(n#A(n#A・・・・【Aがω個】・・・A(n#n))))・・・))=B(n)
B(0#(n+1),a)=B(a#(n+1))
B(X,b+1,0#(n+1))=B(X,b,ω#(n+1))
B(X,b+1,0#n,a+1)=B(X,b,B(X,b+1,0#n,a)#(n+1))
B(X,@#m)=B(X,(@→→m)
計算例 ただしk=B(ω),J=B(1,ω#2)
B(1,ω#2)=B(1,(ω→ω→ω))=B(1,B(1,(ω→ω→ω-1)))=【「B(1,」がω→ω→ω回】k=、、、=J ハイパー演算子っぽいからBEAFみたいな拡張で良いんじゃない? テトレーション空間というのはある空間に配置された値によって任意の座標が定まる新たな空間を定義する、
という操作について閉じている空間
レギオン空間とはその空間とそこに配置された情報に定義されたもろもろの計算ルールで
新たな空間を定義する、という操作について閉じている空間。そう考えるとあんまり自明ではない。 A(ω#ω)
これはどれくらいの大きさになるんかな? >>281
A(1#1)=A(1)=ω+1
A(2#2)=A(2,2)=ω^4
A(3#3)=A(3,3,3)=分からない(法則推理だとω↑↑↑9になったけどもっとでかそう)
A(ω#ω)= 法則推理だと ω→(ω^2)→(ω×2-1) だけどもっとでかそう >>278で思いついた
定義
ω:最初の極限順序数
X:0個以上の(0以上の整数または順序数)
a,b,n,m:0以上の整数または順序数
@:順序数
x#y:y個のx
A[m+1](n)=A[m](n#A(n#A・・・・【Aがω個】・・・A(n#n))))・・・))
A[0](n)=ω+n
A[m](0#(n+1),a)=[m](a#(n+1))
A[m](X,b+1,0#(n+1))=[m](X,b,ω#(n+1))
A[m](X,b+1,0#n,a+1)=A[m](X,b,A[m](X,b+1,0#n,a)#(n+1))
A[m](X,@#n)=A[m](X,(@→→n) FGHで考えると
f[ω↑↑(ω+1)](x)=f[ω↑↑ω](x+1)
順序数部分の右辺をすべて展開しなければ左辺を展開できない。順序数部分を
すべて展開しなければxに関数を適用できない。
そういうわけで順序数のテトレーション以降の右結合って効率が悪い。
SGHではそこそこ効果が出る。 多重括弧がゲシュタルト崩壊してきたので演算子風に
ω(0)n = ω+1
ω(1)n = ω(0)…【n個のn】…(0)n = ω+n
ω(2)n = ω(1)…【n個のω】…(1)ω = ω*n
ω(1,0)n = ω(ω)…【n個のω】…(ω)ω
ω(1,1)n = ω(1,0)…【n個のω】…(1,0)ω
ω(2,0)n = ω(1,ω)n
ω(1,0,0)n = ω(ω,ω)…【n個のω】…(ω,ω)ω
ε_0ぽいものをつくって拡張
α_0 = ω(ω,…【ω個のω】…,ω)ω
α_0(0)n = ω(ω,…【ω(0)n個のω】…,ω)ω
α_0(X)Y = ω(ω,…【ω(X)Y個のω】…,ω)ω
α_1 = ω(ω,…【α_0個のω】…,ω)ω 間違えた
ω(2,0)n = ω(1,ω)…【n個のω】…(1,ω)ω つまりそれって
ω(a+1)n=ω(a)n(a)n(a)・・・
ってことだと思うけど、それってどういう定義なんですか? あ、修正
ω(1)n=ω(0)n(0)n(0)・・・
ってことだと思うけど、それってどういう定義なんですか? ハイパー演算子の拡張として定義したから
a(0)nはhyper(a,0,n)つまりsuc(a)
ω(1)5
= ω(0)5(0)5(0)5(0)5(0)5
= ω+1(0)5(0)5(0)5(0)5
= ω+2(0)5(0)5(0)5
= ω+3(0)5(0)5
= ω+4(0)5
= ω+5 こんなのとか
X:0個以上の、0以上の整数または順序数
a,b,c,d:0以上の整数または順序数
a#b:b個のa
BM(a,0,X)=ωa
BM(a,b,0#c)=ωa→→ωb
BM(a,b+1,0#c,d+1,X)=BM(a#(c+1),BM(a,b,0#c,d,X),d,X)
BM(3,3,3)=BM(3,BM(3,2,2),2)=BM(3,BM(3,BM(3,1,1),1))=BM(3,BM(3,(3ω→→3ω^2)) >>291って
BM(a,b+1,0#c,d+1,X)=BM(a#(c+1),BM(a,b,0#c,d,X),d,X) じゃなくて
BM(a,b+1,0#c,d+1,X)=BM(a#(c+1),BM(a,b,0#c,d+1,X),d,X) だとオモう 自分も参加してみる
→:コンウェイのチェーン表記
ω:最初の極限順序数
X:0個以上の、0以上の整数または順序数
a,b:0以上の整数または順序数
a#b:b個のa
C(0#n,0)=ω
C(0#n,a+1)=C(a)→C(a)→...C(a)回繰り返し...→C(a)→C(a)
C(X,b+1,0#[n+1])=C(X,b,C(ω)#[n+1])
C(X,b+1,0#n,a+1)=C(X,b,C(X,b+1,0#n,a)#[n+1]) >>293 のC(ω)は
f(x)=ω↓ω↓2とした時の
C(ω)≒f^ω(ω) かな >>294
想像したよりは大きなかったです
がっくり バシク氏のψ関数はバシク行列を応用して強化されてるんだろうが、
バシク行列を使ってバシク行列を評価するという事態に陥ってるんじゃなかろうか 自分で作ってみた
X : 0個以上の0以上の整数
Y : 0個以上の0
a,b,n,m : 0以上の整数
a#b=b個のa
ゑn〔〕=ゑn〔0〕
ゑn〔X,a+1,0=〕ゑn〔X,a#2〕
ゑn〔X,a+1,b+1〕=ゑn〔X,a,ゑn〔X,a+1,b〕〕
ゑn〔X,a+1,0,Y,b〕=ゑn〔X,a,b,Y,b〕
ゑn+1〔Y,a〕=ゑn〔a#a〕
ゑ0〔Y,a〕=2*a
ゑY:n〔X〕=ゑn〔n#(X)〕
ゑX:n+1:0〔X〕=ゑX:n:n ここからXの代わりにZも使う
ゑZ:n+1:0〔X〕=ゑZ:n:n〔X〕
ゑZ:n+1:m+1〔X〕=ゑZ:n:(ゑZ:n+1:m〔X〕)〔X〕
ゑZ:n+1:0:Y:m〔X〕=ゑZ:n:m:Y:m〔X〕
f0〔a〕=(ゑ^a)a#a(〔a#a〕#a)
f(b+1)〔a〕=(fb)^a〔a〕
ここでf関数の〔〕の中も多変数にして
f^9〔9#9〕 をゑゑ数とする θ(α,β)
αをパラメータとしてβを強化する (β≥Ωのときも)
θ(0,b) = ω^b
θ(0,b+c) = b*c
θ(0,b*c) = b^c
残りは後で 多変数のアッカーマン関数を再考
2変数アッカーマン関数
f(0,a)=a+1
f(b+1,0)=f(b,1)
f(b+1,a+1)=f(b,f(b+1,a))
3変数アッカーマン関数
f(0,0,a)=a+1
f(0,b+1,0)=f(0,b,1)
f(b+1,0,0)=f(b,1,1)
f(0,b+1,a+1)=f(0,b,f(0,b+1,a))
f(b+1,0,a+1)=f(b,f(b+1,0,a),f(b+1,0,a))
f(c+1,b+1,0)=f(c,f(c+1,b,1),f(c+1,b,1))
f(c+1,b+1,a+1)=f(c,f(c+1,b,f(c+1,b+1,a)),f(c+1,b,f(c+1,b+1,a))) 4変数アッカーマン関数
f(0,0,0,a)=a+1
f(0,0,b+1,0)=f(0,0,b,1)
f(0,b+1,0,0)=f(0,b,1,1)
f(b+1,0,0,0)=f(b,1,1,1)
f(0,0,b+1,a+1)=f(0,0,b,f(0,0,b+1,a))
f(0,b+1,0,a+1)=f(0,b,f(0,b+1,0,a),f(0,b+1,0,a))
f(b+1,0,0,a+1)=f(b,f(b+1,0,0,a),f(b+1,0,0,a),f(b+1,0,0,a))
f(0,c+1,b+1,0)=f(0,c,f(0,c+1,b,1),f(0,c+1,b,1))
f(c+1,0,b+1,0)=f(c,f(c+1,0,b,1),f(c+1,0,b,1),f(c+1,0,b,1))
f(c+1,b+1,0,0)=f(c,f(c+1,b,1,1),f(c+1,b,1,1),f(c+1,b,1,1))
f(0,c+1,b+1,a+1)=f(0,c,f(0,c+1,b,f(0,c+1,b+1,a)),f(0,c+1,b,f(0,c+1,b+1,a)))
f(c+1,0,b+1,a+1)=f(c,f(c+1,0,b,f(c+1,0,b+1,a)),f(c+1,0,b,f(c+1,0,b+1,a)),f(c+1,0,b,f(c+1,0,b+1,a)))
f(c+1,b+1,0,a+1)=f(c,f(c+1,b,f(c+1,b+1,0,a),f(c+1,b+1,0,a)),f(c+1,b,f(c+1,b+1,0,a),f(c+1,b+1,0,a)),f(c+1,b,f(c+1,b+1,0,a),f(c+1,b+1,0,a)))
f(d+1,c+1,b+1,0)=f(d,f(d+1,c,f(d+1,c+1,b,1)),f(d+1,c,f(d+1,c+1,b,1)),f(d+1,c,f(d+1,c+1,b,1)))
f(d+1,c+1,b+1,a+1)=f(d,f(d+1,c,f(d+1,c+1,b,f(d+1,c+1,b+1,a))),f(d+1,c,f(d+1,c+1,b,f(d+1,c+1,b+1,a))),f(d+1,c,f(d+1,c+1,b,f(d+1,c+1,b+1,a)))) 再考した多変数アッカーマン関数の定義の省略方法を思いつかなかったので挫折
>>274を参考に多変数アッカーマン関数を定義
X : 0個以上の0以上の整数
a,b,n : 0以上の整数
a#b : b個のa
f(0#n,a)=a+1
f(X,b+1,0#(n+1))=f(X,b,1#(n+1))
f(X,b+1,0#n,a+1)=f(X,b,f(X,b+1,0#n,a)#(n+1)) f(0#n,a)=a+1 はもっと強くできると思います
f(0#n,a)=f(a#n)
f(a)=a+1 みたいな >>304
こんな感じにしてみた
X : 0個以上の0以上の整数
a,b,n : 0以上の整数
a#b : b個のa
f(a)=a+1
f(0#(n+1),a)=f(a#(n+1))
f(X,b+1,0#(n+1))=f(X,b,1#(n+1))
f(X,b+1,0#n,a+1)=f(X,b,f(X,b+1,0#n,a)#(n+1)) 今思いついたけど
#の記号をa#b#cと並べたら
c×b個のaとできるね
そしてa#a#a#…n個…#aをa##nと表現して
a##nは、a↑n個のaと表現できて
a##a##a##…n個…##aをa###nと表現すれば
a###nは、a↑↑n個のaと表現できるね 多変数アッカーマンの拡張やろうとしたら駄目だったので定義だけ書いておく
X : 0個以上の0以上の'(後述)で区切られた整数
a,b,n,m : 0以上の整数
a(#0)b : 「,」で区切られたaがb個
a(#(n+1))b : 「#n」で区切られたaがb個
' : 「,」もしくは「#n」 オンプ関数を次のように定義する
a(♪0)=Ack(a,a,a(a回)a)
a(♪b+1)=a((♪b)^a)
そして
a(♪♪0)=a(♪a)
a(♪♪b+1)=a((♪♪b)^a)
同様に、♪がいくつあっても
a(♪(c個)♪0)=a(♪(c-1個)♪a)
a(♪(c個)♪b)=a((♪(c個)♪(b-1))^a)
そして、ここで縦に無限に広がるテープを考える。その表の一番前の所に1と書く。テープの二番目からは、前にある数をxとして、
x(♪(x個)♪x)
で、できた数を書く。実際に計算すると一番前は1で、1(♪1)=2なので、二番目の数は2となる。三番目の数は、
2(♪♪2)=2(♪♪1)(♪♪1)=(省略、、)=Ack(7,7,7,7,7,7,7)(♪1)(♪♪0)(♪♪1) という事になるので、もう巨大な数となる。
さらに巨大にするために、テープを表に拡張させる。ここで、:(横,縦) という表記を用いる事にする。
一番左の行は、前述テープと同じで、二行目からは、まず:(a,1)に1を書き、
:(a,b)=:(a-1,:(a,a-1)♪) とする。
そうした時の、:(9(♪9),9(♪9)) >>309
a(♪0)はアッカーマンを繰り返しているからω+1
a(♪b+1)=a((♪b)^a)は^がべき乗ならあまり意味がない
おそらく十分大きなaに対して (a+1)(♪0) >> a(♪…(a個)…♪a)
後半のテープに書くやつは前の演算を繰り返す操作だから
数字が1増えてω+2
二次元テープのやつはどうなんだろ
内部のアッカーマンとの絡みがないので急激には増えない
アッカーマン的操作なのでωは追加されそう
なのでω2+2+αぐらいな気がする
ω3はいかない気がする べき乗というか、繰り返し
a(♪b+1)=a((♪b)^a)=a(♪b)(♪b)(♪b)(♪b)・・・a回・・・(♪b) X : 0個以上の非負整数
a,b,c,d : 非負整数
m#n : m個のn
A(X,0,0)=1
A(0,b)=b+1
A(X,a+1,0)=A(X,a,1)
A(X,a+1,b+1)=A(X,a,A(X,a+1,b))
A(X,d+1,c#0,0,b)=A(X,d,(c+2)#b)
多次元空間の表を使った手順の計算がやり易そうな多変数アッカーマン関数 そういえば多重リストアッカーマンってまだ厳密に定義されてないんだっけ?
もしかしてε0はペアノ算術超えてるから数式では書き表せないとかいう落ちがあるんだろうか? 2重リストアッカーマンの解説読んでみたけど
基本的なアイディアはヒドラと同じなのかな?
じゃあヒドラをパクれば多重リストアッカーマンも厳密に定義できるかな? Alist1(X) 関数は二重リストと同じ
Alist2(0,a)=Alist1([a#a]#a) つまりaがa個入った[]がa個、さらにそれをリストにして、、、っていうのを考えてみた 1段階でどのくらい強化されるのがちょうどいいんだろうね ωとかを使う、「ものさし」の急増加関数の自分版を定義してみた。
n,m:0以上の非負整数
$:ω以上の順序数
$[n]:$の収束列のn番目
Z:0個以上の0以上の非負整数または順序数
f(n)=n+1
f(Z,0)=f(Z)
f(Z,n,m+1)=f^f(Z,n)(Z,n,m)
f(n,Z,$)=f(n,Z,$[f(n,Z)])
f($,Z)=f($[10],Z)
f(n,Z,m+1)=f^(n,Z)(n,Z,m) 訂正
f(n)=n+10
f(Z,0)=f(Z)
f($,Z,n)=f($[n],Z,n)
f(n,Z,$)=f(n,Z,$[f(n,Z)])
f($,Z,$)=f($[10],Z,$)
f(n,Z,m+1)=f^f(n,Z,m)(n,Z,m)
f(ω,ω,ω)=f(10,ω,ω)=f(10,ω,f(10,ω))=f(10,ω,f(10,f(10)))=f(10,ω,f(10,20)).... このスレも将来は巨大数探索スレッド{3,3,3,3}とか表記されるようになるのか >>320
巨大数探索スレッド({3,3,3,3}/2+10^72+4↑↑↑↑5)とかなったら暗記できなさそう {3,3,3,3}/2+10^72+4↑↑↑↑5とか切の良い番号ならいいが
切が悪いと表記するのにどうやってもものすごい文字数が必要になる。 そりゃあ4↑↑↑5個のユニークな数を表現しようとしたら4↑↑↑5パターンのユニークな表現を使わざるを得ないから仕方がない。むしろ一番圧縮率が良い表現方法がベタの2進数だし 単純にm種n文字でm^nパターンの数を表現できるということになふぁないか ω:最初の極限順序数
a,b,n:0以上の整数または順序数
X:0個以上の0以上の整数または順序数
a#b:b個のa
a#b+1=a#(b+1)
A()=ω
A(0#n+1)=ω^A(0#n)
A(a+1)=A(0#A(a))
A(0#n+1,a+1)=A(A(0#n+1,a)#n+1)
A(X,b+1,0#n+1)=A(X,b,ω#n+1)
A(X,b+1,0#n,a+1)=A(X,b,A(X,b+1,0#n,a)#n+1)
A(0#ω)=ε_0になるように定義した 以下計算例
A()=ω
A(0)=ω^ω
A(1)=A(0#A(0))=A(0#ω^ω)
A(2)=A(0#A(1))=A(0#A(0#ω^ω))
A(0,0)=ω^ω^ω
A(0,1)=A(A(0,0))=A(ω^ω^ω)
A(0,2)=A(A(0,1))=A(A(ω^ω^ω))
A(1,0)=A(0,ω)
A(1,1)=A(0,A(1,0))=A(0,A(0,ω))
A(1,2)=A(0,A(1,1))=A(0,A(0,A(0,ω)))
A(2,0)=A(1,ω)
A(2,1)=A(1,A(2,0))=A(1,A(1,ω))
A(2,2)=A(1,A(2,1))=A(1,A(1,A(1,ω)))
A(0,0,0)=ω^ω^ω^ω
A(0,0,1)=A(A(0,0,0),A(0,0,0))=A(ω^ω^ω^ω,ω^ω^ω^ω)
A(0,0,2)=A(A(0,0,1),A(0,0,1))=A(A(ω^ω^ω^ω,ω^ω^ω^ω),A(ω^ω^ω^ω,ω^ω^ω^ω))
A(0,1,0)=A(0,0,ω)
A(0,1,1)=A(0,0,A(0,1,0))=A(0,0,A(0,0,ω))
A(0,1,2)=A(0,0,A(0,1,1))=A(0,0,A(0,0,A(0,0,ω)))
A(0,2,0)=A(0,1,ω)
A(0,2,1)=A(0,1,A(0,2,0))=A(0,1,A(0,1,ω))
A(0,2,2)=A(0,1,A(0,2,1))=A(0,1,A(0,1,A(0,1,ω)))
A(1,0,0)=A(0,ω,ω)
A(1,0,1)=A(0,A(1,0,0),A(1,0,0))=A(0,A(0,ω,ω),A(0,ω,ω))
A(1,0,2)=A(0,A(1,0,1),A(1,0,1))=A(0,A(0,A(0,ω,ω),A(0,ω,ω)),A(0,A(0,ω,ω),A(0,ω,ω)))
A(1,1,0)=A(1,0,ω)
A(1,1,1)=A(1,0,A(1,1,0))=A(1,0,A(1,0,ω))
A(1,1,2)=A(1,0,A(1,1,1))=A(1,0,A(1,0,A(1,0,ω)))
A(1,2,0)=A(1,1,ω) >>330じゃないけど a##b=a#a#a#・・・(b回)、K0=ω→3→2、Kn=A(0##K(n-1)) というのを定義したとき
A(0,ω)=A(A(0,ω-1))=A(A(A(0,ω-2))=A^ω(0,1)=A^ω(K0)=A^(ω-1)(K1)=A^(ω-2)(K2)=Kω
となりそう。ちなみに K0<ε0<K1<<A(0,ω) A(0#ω)=ε_0
A(0#ω+1)=ω^ε_0
A(0#ω+2)=ω^ω^ε_0
A(0#ω+ω)=A(0#ω×2)=ε_0^ε_0
A(0#ω×2+1)=ω^ε_0^ε_0
A(0#ω×2+2)=ω^ω^ε_0^ε_0
A(0#ω×2+ω)=A(0#ω×3)=ε_0^ε_0^ε_0
A(0#ω×4)=ε_0^ε_0^ε_0^ε_0
A(0#ω×ω)=A(0#ω^2)=ε_1
A(0#ω^2+1)=ω^ε_1
A(0#ω^2+2)=ω^ω^ε_1
A(0#ω^2+ω)=ε_0^ε_1
A(0#ω^2+ω×2)=ε_0^ε_0^ε_1
A(0#ω^2+ω×ω)=A(0#ω^2×2)=ε_1^ε_1
A(0#ω^2×3)=ε_1^ε_1^ε_1
A(0#ω^2×4)=ε_1^ε_1^ε_1^ε_1
A(0#ω^2×ω)=A(0#ω^3)=ε_2
A(0#ω^4)=ε_3
A(0#ω^5)=ε_4
A(0#ω^ω)=ε_ω
A(1)=A(0#ω^ω)=ε_ω A(2)=A(0#A(1))=A(0#A(0#ω^ω))=A(0#ε_ω) > A(0#ε_0^ω^2)=Γ_0 フィッシュの巨大数論を読んで、ご本人のなかではすでに解決してるかも
ラヨ関数は1階の集合論を対角化して得られる関数であり、1階の集合論は1階の述語論理で
記述される。
ラヨ命名する論理式によってある変数a_0はある自然数nに決定される。
1階の述語論理の完全性により、ラヨ命名する論理式の元でa_0=nが真であること
、nでない自然数mについてa_0=mが偽であることがそれぞれ証明可能である。
要するにラヨ命名する論理式が理論的な公理の役割を果たしている。
1階述語論理の完全性が重要でZFCとかフォン・ノイマン宇宙の対角化とかいうのは
あまり重要でないような
いっそのこと証明不可能レベルなんだとふっきれて、証明できないけれどある自然数を決定している
論理式が存在すると言ってしまうのもありだと思う。
ビッゲドンは真理述語が定義不能だからこそ形式的に真理述語を導入することで
強力な表現を可能としているし、さらに階層を高くしていくことでもうくぁwせdrftg
なんだろう
階層を高くしていくことで Hardyっぽいの
a, n: 自然数
X: 0個以上の自然数
Y: 0個以上の0
Rule 0. 表記ルール
0-1: (X1(0)X2) = (X1,X2)
0-2: (X1(X2)(X2)X3) = (X1(X2)0(X2)X3)
0-3: (Y(X1)X2) = (X2)
Rule 1. 終了ルール: (Y)[n] = n
Rule 2. 破滅ルール
2-0: (X)+1[n] = (X)[n+1]
2-1: (X)[n] = (next_n(X))[n]
2-2: next_n(X,a+1) = (X,a)+1
2-3: next_n(X,a+1,0,Z) = (X,a,n,Z)
2-4: next_n(X1,a+1(X2)Z) = (X1,a(X2)1{"(next_n(X2))" * n})
(1(1))[3]
= (0(1)1(0)(0)(0))[3] = (1(0)0(0)0(0)0)[3] = (1,0,0,0)[3]
= (3,0,0)[3] = (2,3,0)[3] = (2,2,3)[3] = (2,2,0)[6] = (2,1,0)[12] = (2,0,0)[24] = (1,24,0)[24] = (1,0,0)[2^24*24] = (2^24*24,0)[2^24*24]
= 2^(2^24*24)*2^24*24 = 2^(2^24*24+24)*24 ≒ 10^121210694*6.895
(1,0)[n] = (0,n)[n] = (n)[n] = f_2(n)
(1,0,0)[n] = (n,0)[n] = f_3(n)
(1(1))[n] = (0(1)1,0,0,...)[n] = (1,0,0,...)[n] = f_ω(n)
(1,0(1))[n] = (n(1))[n] = f_ω+1(n)
(1(1)(1))[n] = f_ω2(n)
(1(2))[n] = f_ω^2(n)
(1(1,0))[n] = f_ω^ω(n)
(1(1,1))[n] = f_ω^(ω+1)(n)
(1(2,0))[n] = f_ω^(ω2)(n)
(1(1,0,0))[n] = f_ω^ω^2(n)
(1(1(1)))[n] = f_ω^ω^ω(n)
(1(1(1(1))))[n] = f_ω^ω^ω^ω(n)
たぶん。
リスト部分だけ取り出すと順序数のリスト表記として使える >>335
ZFCやらがあまり重要でないことはないが、最低限自然数に関する公理を事前に準備しておけば
それだけで十分ということか。強力な公理を準備しておけばそれだけ命名する文字数も短くてすむようになるが、
Rayo(n+a)程度の効果にしかならないし、可能性を狭めかねない。
ところでフォン・ノイマン宇宙の対角化というのはラヨ自信の言葉なんだろうか? 順序数崩壊関数をある程度理解してこねこねできるようになったのでこんな関数を作った
θ(0) = 1
θ(1) = ω
θ(ω) = ω^ω
θ(Ω) = ε_0
θ(ε_(Ω+1)) = ψ_0(ψ_1(0))
θ(1,0) = Ω
θ(1,1) = Ω*ω
θ(1,Ω) = Ω*ω^Ω = Ω*Ω = Ω^2
θ(1,Ω^2) = Ω*ω^Ω^2 = Ω*(ω^(Ω*Ω)) = Ω*(ω^Ω)^Ω = Ω*Ω^Ω = Ω^Ω
θ(1,Ω_2) = ε_(Ω+1)
θ(2,0) = Ω_2
θ(Ω,0) = Ω_Ω
θ(Ω_Ω,0) = Ω_Ω_Ω
θ(I,0) = ψ_I(0)
θ(1,0,0) = I
θ(1,1,0) = I_2
θ(1,I,0) = I_I
θ(1,I_I,0) = I_I_I
θ(2,0,0) = χ(1,0)
θ(1,0,0,0) = M
θ(K,0,0,0) = Ξ(K,0)
θ(1,0,0,0,0) = K
こんな関数
多変数のいいところはどれだけでかい順序数を入れてもいいところだよね、とか言いつつ
計算があってるか怪しいし本当に定義できるかどうかも怪しいあやしーた関数
あやしーた関数で定義できないほど大きい巨大基数を仮に∞と置いて順序数崩壊関数的に使える
逆に定義を変えてθ(1,0)=ω_1^CK, θ(1,0,0)=I^CK, ...みたいにして∞=Ωにもできそう
θ(Ω) = ω_1^CK
θ(Ω^2) = I^CK
θ(Ω^3) = M^CK
θ(Ω^4) = K^CK
θ(Ω^ω) = ?
θ(Ω^Ω) = ??
θ(Ω^Ω^Ω) = ???
θ(1,0) = Ω
θ(1,Ω) = Ω^2
θ(1,Ω*2) = Ω^3
θ(1,0,0) = I ビジービーバー関数のそれぞれの値は、任意の推論が妥当かどうかを判断するアルゴリズムが
存在しないほど高度な、健全かつ無矛盾な論証体系で求めることができる(かもしれない)。
そんなもの本当に発見出来たらゲーデルの不完全性定理を計算可能な理論全体で克服できて
ZFCの無矛盾性やらが健全かつ無矛盾に証明できたりするし、そういう言語を対角化することで
現代の論理では根本から及ばないほど強力な関数が出来上がったりする。
フィールズ賞受賞レベル ラヨ数<BIG FOOT<Little Biggedon<ふぃっしゅ数バージョン7<Big Biggedon
かな。定義不可能な関数を導入した方が効率が良さそうだし、それでふぃっしゅ数バージョン8的なものを作りたい。
でももしかしたらDeedlit氏が既に何か作ってるのかもしれない。 どうやら(省略に無理あるけど)
魚4<ラヨ数<魚7<BIGFOOT<リトルビッケドン<サスクワッチ(ビッグビッケドン)
となるみたいですよ リトルビッゲドンについて初歩的な勘違いをしていた。
話変わるけど、oodle theory はウードル論理と訳したほうがいいんじゃなかろうか。
意味ではなく形式を定義するものだから。 logicじゃなくてtheoryだからFirst Order Set Theoryにあわせてウードル論で良さげか
ある言語で記述される理論の総称と考えればただ単に形式を定義したものでもないし >>341
Deedlitは去年の暮れにFOFTという理論を使ってBIG FOFTという巨大数を作っててそれがBig Biggedonが出るまでは長らく一位だったよ
http://googology.wikia.com/wiki/User_blog:Deedlit11/My_humble_extension_of_FOOT?useskin=oasis
比較に関しては
FOFT の func^0_0 = FOOT の Ord
FOFT^1_0 = FOOT
FOFT^1_0 = Little Biggedon の言語 {∈,T} < FOFT^2_0
なので
BB<F4<Rayo<F7<FOOT<Little Biggedon<FOFT<Big Biggedon ミスりました
FOFT^1_0 = FOOT
FOFT^1_1 = Little Biggedon の言語 {∈,T}
<FOFT^2_0
の間違い 可算個の字母集合で記述されるすべての有限の文字列の集合とすべての自然数から自然数への写像
の集合は同じ濃度を持つ。
可算個の字母集合からなる有限の文字列で任意の自然数から自然数への写像を定義すること
はできない。
証明は高校生の宿題にしよう kを非可算な基数とし、
濃度がkより小さい字母集合で記述されるすべての長さがkよりも短い文字列の集合
と、すべての自然数から自然数への写像の集合は同じ濃度を持つ。
が成り立たないとき、kは弱コンパクト基数 変なこと言ってしまったがこれ弱コンパクト基数でもなんでもないわ ↗m(0#n+1)=n+1
↗0(X[n変数],b+1)=↗0(X[n変数],b)↑↑↑(n+1)
↗m+1(X[n変数],b+1)=↗m(↗m+1(X[n変数],b)#n+1)
↗m(X,a+1,0#n+1)=↗m(X,a,↗m(X,0#n+1,a+1),0#n)
T(n)=↗n(n#n)とした時の T^1301(1301) なんかこういうの、無数に考えられてるけど、テキスト入れたら「はい、80点!」みたいに大きさ出てくるようにならないかな。
「はい、それは<f_θ(Ω_ε_ω+1)(0)!」でもいいし >>352
多分計算不能だろう。
テキストに制限をいれたらいけるかもだが。 いや、だいたいの大きさの見積もりをする話で。
みんなやってるじゃん。>>30 みたいな感じで。
2chに書き込めるってことは1024文字以内で見積もれてるわけで。 どう見積もるかにもよる。
計算可能であれば全部<ω^CKですませてもいいんだし 算術と巨大基数は関係ある?何というか、順序数に使われるけど 証明論的順序数、興味あるな。
ペアノ算術がε0とかだっけ? >>357
巨大基数は、算術に対してというよりもZFCに対して使われる >>360
横からですまんけど、巨大基数っていうのは全部無限の向こう側で、巨大数wikiに出てくるような順序数はまだ有限のめちゃくちゃ巨大な数ってこと?
なんか基数、順序数、א数とかもう訳わからない
ちゃんと高校生のとき数学勉強しとけばよかった 高校じゃならわんだろ。
大学でも数学科とかじゃないと習わんのじゃないか。 大学の数学科でもマニアックな部類に入るんじゃなかろうか。
藻の人も結構知らないことあるようだし 只でさえマニアックな公理的集合論の更にマニアックな分野。 >>362
いや、せめて数学記号だけでも読めたらちょっとは違ったのかなって思ったから ちなみにBIG FOOTを発見した人は今18才だって。
発見したのは3年前だから高校1年生くらいの時になるのか。
ノルウェー出身で今アメリカの大学に行ってるんだって。 進まないので適当に一つ(弱いけど)
回転斜め矢印表記
@多変数タワー表記
小文字アルファベット : 1以上の整数
X : 0個以上の1以上の整数
[a]↑b=a^b
[X,a]↑b=[X]↑^b a 注意
[X,a]↑^n b=[X,a]↑b
[X,a]↑^(n+1) (b+1)=[X,a]↑^n([X,a]↑^(n+1) b)
注意について:変数が1つの時は上のルールを使います。0変数のときに、1変数に変える事はできます。
Aシャープ収納表記
[X]"=[X]↑^y z
[a#b]"=[a,a,a(b個)a,a,a]"
[a#^n 1]"=[a]"
[a#^(n+1) (b+1)]"=[a#^n ([a#^(n+1) b]")]"
B右上矢印表記
[a]↗b=[a#^b a]↑^a b
この他は@の↑を↗に変えるだけです。
C回転斜め矢印表記
Bの定義の部分を、↗,↘,↙,↖,↗1,↘1,↙1,↖1,↗2 と言うように強化していきます。
D例
[52,7,43]{↘7}{↘7}{↘7}5=[52,7,43]{↘7}{↘7}([52,7,43]{↘7}{↘7}{↘7}4) 未だに新しい記号使って新しい関数作って〜とかやってんのか。 逆に全く新しい記号を使わずに何とかしようとすると最終的に0と1だけで頑張ることになる。
渋いな 左の値を加法でm個並べ、n個の演算子全てをhyper(n)に変更し
変更後の式を全て加法になるまで展開しn'個の演算子全てをhyper(n')に……という工程をm回繰り返す演算子¶
例) 2¶3 → 2+2+2 → 2*2*2 → 2+2+2+2 → 2^2^2^2 → 2+...(計32768個)...+2 →2(32767)2(32767)...2
タワー表記同様、¶をn個連ねた物を¶(n)と表記し、
A¶(n)BはB個のAに¶(n-1)を挟んだ式になる。
3¶(3¶(3¶3)3)3と入れ子にも出来る。 さっさと〜演算子を〜回繰り返すとかいう拡張の限界をもとめて終止符を打てばいいんじゃね? 演算子の拡張って手段として強いのか弱いのかよくわからん
でも矢印表記とかのわりとクラシックな巨大関数の頃からある手法だから陳腐感は否めないと思う >>391を見直して意味不明だったので改良
拡張ハイパー演算子の定義
A[hyper(N)M]B =
A[hyper(N+B)M-1]A[hyper(N+B)M-1]A[...]A
└── B ──┘
[hyper(N)0] = hyper(N)
3[+1]2 = 3^3 3[+1]3 = 3↑↑3↑↑3 3[+1]4 = 3↑↑↑3↑↑↑3↑↑↑3
3[↑1]2 = 3↑↑↑3 3[↑1]3 = 3↑↑↑↑3↑↑↑↑3 = 3→3→5
3[+2]3 = 3[↑↑1]3[↑↑1]3
= 3[↑↑1](3→3→6)
= 3 hyper(4 + 3→3→6) 3 hyper(4 + 3→3→6) 3 (...) 3
3[+(3[+3]3)]3 = 3[+(3[+3]3 - 1)]3[+(3[+3]3 - 1)]3... ZFC+マーロ基数とマーロ基数を崩壊させた関数。例えばこの二つに違いはあるのかとか、比べる意味がないとか、具体的な大きさが両方わからないけれど知りたい。 ZFC+マーロ基数(が存在するという公理)はこの理論で全域性を証明できるかどうかで強さを計れる。
マーロ基数を崩壊させる方はどう崩壊させるかによる。 マーロ基数や弱コンパクト基数の扱い方がまれによく間違われているような気がする。
Ξ(3,0)=C(Ω_2^3,0)=1-マーロ基数
Ψ[Ξ(3,0)](2,0)=C(Ω_2^2*C(Ω_2^3,0),0)=α→M_αとなる最小の不動点
Ψ[Ψ[Ξ(3,0)](2,0)](1,0)=C(Ω_2^2+Ω,0)=M+1-到達不可能基数
Ψ[Ψ[Ψ[Ξ(3,0)](2,0)](1,0)](0,0)=C(Ω_2^2+C(Ω_2^2+Ω,0),0)=M_M_M_・・・ 何が分かりやすいかってある程度突き詰めたところから先は人それぞれとしか言いようがなくて、
最終的にその人の努力に委ねられるなと思った。 順序数を崩壊させる方法と関数を対角化させる方法ってどういう関係にあるの。 とりあえず崩壊過程が複雑であればそれだけ強力な関数を対角化できる。
話変わるけどあれは論理的帰決と定理、存在論からいえば隔絶された神話的世界
から存在すると言われていることと観測可能であることを同列に語っている点が
どうしてももやもやするんだ。 やりたいことは巨大数の成長率の比べっこだから、じゃあ欲張りクリーク列とかはFGHで評価できるか、みたいな問いになるのかな テトレーション以降の複素数域への拡張は、ただ見解が統一されてないだけで
無数にあるのね 3^3^3^{3^(1/3)}かな
有理数のテトレーションは一般化可能だが無理数のテトレーションとなると見当もつかない ていうか有理数で可能ならその極限としてそのまま無理数に持って行けるんじゃ。 f(0)=ω
f(n+1)=ω^f(n)
f(0)=ω
f(1)=ω^ω
f(2)=ω^ω^ω
f(ω)=ε_0
f(ω+1)=ω^ε_0
f(ω+2)=ω^ω^ε_0
f(ω×2)=ε_0^ε_0
f(ω×3)=ε_0^ε_0^ε_0
f(ω^2)=ε_1
f(ω^2+1)=ω^ε_1
f(ω^2+2)=ω^ω^ε_1
f(ω^2+ω)=ε_0^ε_1
f(ω^2+ω×2)=ε_0^ε_0^ε_1
f(ω^2×2)=ε_1^ε_1
f(ω^2×3)=ε_1^ε_1^ε_1
f(ω^3)=ε_2
f(ω^4)=ε_3
f(ω^ω)=ε_ω
f(ω^ω+1)=ω^ε_ω
f(ω^ω+2)=ω^ω^ε_ω
f(ω^ω+ω)=ε_0^ε_ω
f(ω^ω+ω×2)=ε_0^ε_0^ε_ω
f(ω^ω+ω^2)=ε_1^ε_ω
f(ω^ω+ω^2×2)=ε_1^ε_1^ε_ω
f(ω^ω+ω^3)=ε_2^ε_ω
f(ω^ω+ω^4)=ε_3^ε_ω
f(ω^ω×2)=ε_ω^ε_ω
f(ω^ω×3)=ε_ω^ε_ω^ε_ω
f(ω^(ω+1))=ε_(ω+1)
f(ω^(ω+1)+1)=ω^ε_(ω+1)
f(ω^(ω+1)+2)=ω^ω^ε_(ω+1)
f(ω^(ω+1)+ω)=ε_0^ε_(ω+1)
f(ω^(ω+1)+ω×2)=ε_0^ε_0^ε_(ω+1)
f(ω^(ω+1)+ω^2)=ε_1^ε_(ω+1)
f(ω^(ω+1)+ω^2×2)=ε_1^ε_1^ε_(ω+1)
f(ω^(ω+1)+ω^3)=ε_2^ε_(ω+1)
f(ω^(ω+1)+ω^4)=ε_3^ε_(ω+1)
f(ω^(ω+1)+ω^ω)=ε_ω^ε_(ω+1)
f(ω^(ω+1)+ω^ω×2)=ε_ω^ε_ω^ε_(ω+1)
f(ω^(ω+1)×2)=ε_(ω+1)^ε_(ω+1)
f(ω^(ω+1)×3)=ε_(ω+1)^ε_(ω+1)^ε_(ω+1)
f(ω^(ω+2))=ε_(ω+2)
f(ω^(ω+3))=ε_(ω+3)
f(ω^(ω×2))=ε_(ω×2)
f(ω^(ω×3))=ε_(ω×3)
f(ω^ω^2)=ε_(ω^2)
f(ω^ω^3)=ε_(ω^3)
f(ω^ω^ω)=ε_(ω^ω)
f(ε_0)=ε_(ε_0)
f(ε_(ε_0))=ε_(ε_(ε_0))
f(ε_(ε_(ε_0)))=ε_(ε_(ε_(ε_0)))
f(η_0)=η_0 n状態のチューリングマシンでチューリング完全でないものが読み取ることができる関数の上限
ビジービーバー的な関数の値を求めるのはある程度探究されてるがこっち方面も面白そう たとえばSコンビネータだけ、Kコンビネータだけとか。
Iコンビネータだけだと定数関数、ステップ数を数えあげても後者関数にしかならない。 Kコンビネータだけだと加法の計算しかできないし、ステップ数かぞえてもx+aくらいの
関数にしかならんな。
Sコンビネータはいろいろできそうだ。Sを0、SSSを後者関数としてなんやかやと。
Sコンビネータのみに限定したΞ関数は計算可能なはずだが、どれくらいの強さになるだろう。 Sのみによる計算が終了するかどうかを評価するΩコンビネータを考える。ビッゲドンみたいに高階化してもよい。
KのみIのみと違い計算が終了しないことがある。
S(S(SSS))(S(SSS)(SSS))とか
とても強そう。計算可能? バシク行列もそうだけど、チューリング完全よりも弱い言語を対角化した関数を定義できる言語を・・・
という構造は型システムで表現できる。これは見方を変えれば、チューリング完全な言語による
表現の内、計算が終了すると証明できる形(バシク行列でいう標準形)のみを対角化できる言語を・・・
ということになる。型システムの場合は型検査で証明する。バシク行列システムでは
まだもろもろ証明もできてないし、標準形の判断方法も定まっていない。
しかしそれらの問題を解決できたら、CoCはおろかCICをはるかに上回る証明支援システム
として扱うことができるのではなかろうか。 このレベルになると計算可能レベルも計算不可能レベルと同じように言語を開発して殴り合う戦いに
なりそうだ。
出来上がったら証明支援ツールにそのまま応用が利くし、プログラミング業界にも何か恩恵があるかもしれない、
とか適当なことを言ってみる チューリング完全な言語で遺伝的アルゴリズムとか使って巨大数を生成したら
ビジービーバーにどこまで迫れるんだろう?
チューリング完全をはずれて真の乱数生成装置とかが使えると仮定したら
ビジービーバーに追いつく可能性も出てくるんだろうか。 計算可能性の証明って、システムが強力であればある程、必然的になにかしらの巨大基数公理を
生み出すのだな ε0は切がいい順序数のように見えるけどその次の切の良い順序数ってГ0あたり? 巨大基数公理ってどこまで巨大になっていくんだろ
計算不可能レベルの巨大数も可算基数も不可算基数も、大きさのイメージとかが掴めない
それぞれの違いがわかりやすい解説とか無いのかな >>419
ε_0は文字が変わるから切りがいいように見えて本質はω↑↑ωっていうだけだよ。
ω^ωに比べて大したことない。 >>419
多変数ヴェブレン関数で表すと、
ε_0(イプシロン・ノート) = φ(1,0)
Г_0(フェファーマン・シュッテの順序数) = φ(1,0,0)
どちらの順序数もヴェブレン関数の変数が1個増えるターニングポイントという点では
キリがいいのかも
(※同様の順序数として
ω = φ(1)、アッカーマン順序数φ(1,0,0,0)、小ヴェブレン順序数φ(1,0,…,0)(0がω個)
等がある模様) しかし>>421さんを見るとε_0が人為的に文字に置き換えられてる感も否めなくなるな…
ε0より大きい順序数でもわざわざ新しい記号を使わなくともωだけでも表せそうな気もするし
(例えばω↑↑↑↑ω、{ω,ω,1,2}みたいな感じで)
その方が直感的で分かり易そうなんだが今の所そういう表し方は見た事が無い
やはりこの表し方だと何かしらの問題があるのだろうか? バードがやっているよ
http://mrob.com/users/chrisb/Beyond_Nested_Arrays_I.pdf
ここに書かれているように、
ω^^(ω+1) = ω^(ω^^ω) = ω^ε_0 = ε_0
となってしまうため、通常の計算規則だとε_0よりも大きくならない。
そこで、バードは
ω^^(ω+1) = ω^(ε_0+1)
かつ、 ω^^β = ε_αのときに
ω^^(β+1) = ω^(ε_α+1)
であると「定義を変える」ことで、ωに関する演算の定義を拡張している。
ただ、このように「定義を変える」ことは必ずしも自明のことではないので、
表記するときにはいちいちことわらなければならないし、
数学的には Veblen 階層や順序数崩壊関数を使う方が自然なので、
そのような表記法はあまり一般的ではない。 {ω,ω,1,2}みたいなのを発展させたのがレギオン配列とかじゃないの? そう。それで、ω^^(ω+1)がε_0よりも強くならないから、BEAFのテトレーション配列
以上は定義がうまくできていない、と Hyp cos が指摘をした、ということが「巨大数論」の
221ページに書かれている。 なるほど、ありがとう
という事は矢印表記は右結合だからω↑↑…↑↑ωの矢印を幾ら増やそうが
この調子でその拡張であるチェーンやBEAFを使おうが
結局はω↑↑(ωの式)の形に行きついてε_0止まりなのか…
超限順序数ならではの奇妙な現象だ
左結合である下矢印表記を使えばより大きくできるのかとか
そもそもなぜω^ε_0 = ε_0が成り立つのかとか
まだまだ謎が尽きないな
自分でももっと色々調べてみた方がよさそうだ 配列を記述する配列の計算ルールを左結合になるよう変えて成り立つようにしてたよな 御風結界
巨大数を作ったけど
近似してくれないですか
画像で説明したいけど
どう貼り付けたらいいの
ふぃしゅ数ver1.2よりはでかいのはわかってるけど
自分でも大きさがわからない
バード数よりも大きい気がする
タワー数とチェーン表記に行きつくけど
行きつかないくらいでかい感じがする
バードの拡張表記をさらに拡張した感じの巨大数
合成前のスタート地点を(3.3.3.3)$(3.3)と配列表記では定義する ★★★数学徒は論理的な考察により客観的に暮らし、日頃から深い学術を志すべき。★★★
¥ ω(↑^ω)ωの濃度はアレフ0、つまり可算だと言っているだけで、特に不思議はないような。 ★★★馬鹿板は悪い習慣であり、大脳が劣化します。なので早く止めましょう。★★★
¥ 天文学的確率でエントロピーが自然に減少することがなかったっけ?
グラハム数分の1よりは大きいんだろうけど >>454の現象
<宇宙の取りりうる全パターンの順列
<グラハム数 ビジービーバー関数BB(n)は、任意の自然数nについてその値が定まると言っていいのだろうか?
例えば連続体仮説でよく知られるように、"可算無限濃度より大きく、連続体濃度より小さい濃度の個数"
の値はZFCのモデルのとり方によって変わり、連続体仮説が真となるモデルなら0、そうでないなら0以外となる。
BB(n)の値も、自然数のモデルのとり方によって変わってしまうことはないか。
"自然数論(ペアノ算術)における妥当な論理式を枚挙し、矛盾を導出したら停止するチューリング機械M"
を構成すると、 これが停止する <=> 自然数論は矛盾 となるから、
自然数論が無矛盾ならこの機械は停止しないはずである。
一方で、自然数論が無矛盾なら自己の無矛盾性は証明できないから、Mが停止しないことを証明できない。
一階述語論理の完全性より、恒真ならば証明可能なので、停止することも停止しないことも証明不能なら
停止するモデルと停止しないモデルの2つがありえる、ということになる。
(一階述語論理の完全性と呼ばれるものは、ゲーデルの第一不完全性定理で言うところの完全性(任意の論理式に
ついて、その肯定か否定のどちらかが証明可能)とは全く意味が異なることに注意)
そもそもチューリング機械Aが停止するとは、"Aがnステップ目で停止状態"を意味する論理式H_A(n)に対し、
∃n (H_A(n))が真であることだと言える。
∃n (H_M(n))が成り立つモデルと成り立たないモデルがあるとはどういうことか。
単純に、∃n (H_M(n))が成り立つ自然数論のモデルはより多くの自然数を含んでいる、ということである。
(集合論で言うところの、巨大基数公理が成り立つモデルのほうが、そうでないモデルよりたくさんの
集合を含んでいることに似ている) では、自然数論の公理PAに、∃n (H_M(n))を加えたことによって追加される自然数とは何か。
自然数論が無矛盾なら、Mは1ステップ目で停止しないだろう。同様に、2,3,4,...ステップ目でも停止しない。
追加される自然数はMが停止するまでにかかるステップ数だから、これをcとすると、
0<c, 1<c, 2<c, 3<c, 4<c,...が成り立つことになる。つまり、PAだけから存在を証明できるいかなる自然数
よりもcのほうが大きい、という奇妙な性質があることが分かる。このcが超準的自然数と呼ばれるもので、
これを含むモデルは超準モデルと呼ばれる。
冒頭の話に戻ると、状態数m以下でMを構成できるなら、Mが停止するモデルを選択すれば、
BB(m)の値は超準的自然数になってしまい、意味をなさなくなってしまう。
ならばBB(n)の定義に補足を加え、
"状態数n以下で(いかなる自然数のモデルでも)停止する機械のうち最も多く1を出力するもの"
とすればこのような問題は起きないと思うかもしれない。
実はそれでもBB(n)の値は超準的自然数になってしまうのだが、それはまた後日の話とする。 ヲヨ数のイメージがいまいち掴みづらいのですが、
たとえば円周率は第一階述語論理の言語で表記するとどうなるのですか? >>456
自然数論単体は矛盾するか矛盾しないかのどちらかであり、1階述語論理の完全性と健全性
により矛盾すればモデルは存在せず、無矛盾であれば存在する
無矛盾であれば、たとえばPA+TとPA+SでBB(x)が取る値が異なることが考えられるのではないか、
ということになるが、どちらの理論も自然数論を含む以上自然数型を部分集合としてもっており、
自然数型をもっていれば異なるモデルに属していても大きさを比べることができ、それなら同じ文字数制限で
出力される最大の数でどちらが大きいかを比べることができ、BB(x)の値が一意に定まる。
自然数型のすべてを持っている必要もない
でいいだろうか BB(x)はモデルによる制限がない、というのを付け加えるのを忘れていた 超準的自然数を出力する(とあるモデルで解釈される)プログラムは有限の値を出力しない
=停止しないものと見なされると言うことで “加算無限濃度より大きく連続体濃度より小さい濃度の個数”というだけでは
答えが自明にならないため、自明になるまでいろいろ理論を付け加えなければ
ある数を命名したことにはならない、というのがラヨ関数のルールのひとつ つまりチューリングマシンも1階述語論理も自然言語や人間の持つあいまいさから完全には解放されていないというわけだ >>458
lim[n→inf]Σ[n=0~N]4(-1^n)/2n+1 >>463
解放されていなんじゃなくて、関わっていない。曖昧な領域は対象外。 より曖昧な部分をなんとか扱えるようにしていくことで、より強力なFOOTやFOFTなんかができるわけだし。
>>459
自然数型をもってるというより自然数型と同型な部分構造を持っている、といった方が正確かな 「1階述語論理で円周率を表現する」といわれるとまず実数を定義するところから
始めるべきだろうか
1階述語論理じゃ実数「のように見えるもの」までしか作れない。
まぁ普通は見えるだけで十分かもしれない 一般的に簡単な具体例を挙げれば分かりやすく説明できるのに、その簡単な具体例がなかなか挙げられない
のがこのあたりの難しいところ。
1+1=2をノート一冊まるまるつかって証明するような世界だもの 反響があるとは意外。
>>459 多分勘違いをしていると思う。
まず、集合論でも連続体仮説が成り立つモデルと成り立たないモデルがとれることからも分かるように、
一般に、ある一つの無矛盾な公理系に対して、それが成り立つモデルはたくさん存在する。
そして、PA + ∃n (H_M(n))のモデルは、当然PAも成り立つから、同時にPAのモデルでもある。
(PA + ∃n (H_M(n))は矛盾していない。PAが無矛盾なら、PAから ¬∃n (H_M(n))が導出されてしまう心配は無いのだから)
PAのモデルに属していれば自然数であるから、∃n (H_M(n))の証拠となる超準的自然数さえも、自然数であることに
変わりなく、0,1,2のようなPAだけから存在を証明できる自然数(仮に普通の自然数と呼ぼう)と比較可能で、
どんな普通の自然数よりも大きい。
だから、異なるモデルでも大きさを比較できるのはその通りだが、超準的自然数を含んでいるモデルのほうが圧倒的に有利である。
超準的自然数を出してしまえば、超準的自然数を含まないモデルに属する自然数に必ず勝てるのだから。
そして機械Mの状態数がm以下であれば、BB(m)には超準的自然数が採用されるだろう。
機械Mを構成するのに必要な状態数はせいぜい普通の自然数で足りるだろう。 >>461で言うところの、超準的自然数を出力するプログラムは停止しないものと見なす、というのは、
それこそまさしく>>457で言った補足入りBB(n)の定義と同じではないか。
いかなる自然数のモデルでも停止する機械、と言っているのだから、停止するまでにかかるステップ数を表す自然数が、
モデルによってあったりなかったりする可能性は無くなる。
>>462については後にしよう。
>>457で後日にすると約束した、補足入りBB(n)の定義においてさえも(普通の自然数に対して)超準的自然数を返すという話が
そっくりラヨ関数にも適用できるため、その話をしてからのほうが良さそうだ。
あと、こちらはBB(n)の値の一意性を問題にしてるわけではない。問題にしてるのは、ある程度大きな数nについてのBB(n)、
例えばBB(100)とかBB(10000)とかBB(10^20)とかについて、その返り値がPAのモデルのとりかたによらず存在してるのか、
言い換えると普通の自然数でありえるのか、という存在性についてである。 >>457の続き
証明の前に、用語の確認をしておく。
公理がω矛盾であるとは、ある論理式Q(n)について、∃n ∈ (自然数)(Q(n))が証明可能であるのに、
Q(0),Q(1),Q(2),...のうちのいずれも証明不能であることである。
公理がω無矛盾であるとは、任意の論理式Q(n)について、∃n ∈ (自然数)(Q(n))が証明可能ならば、
Q(0),Q(1),Q(2),...のうちのどれかが証明可能であることである。
ある公理がω無矛盾ならば、その公理は無矛盾でもある。
したがって自己の無矛盾性を証明できない公理は、自己のω無矛盾性も証明できない。
BB(n)の定義は
"状態数n以下で、自然数論PAのモデルのとりかたによらず、停止するまでにかかるステップ数である
自然数が存在するようなチューリング機械のうち、最も多くの1を出力するものが出力する1の個数"
このままだと扱いにくいので、次に定義するS(n)によって代用する。
"万能チューリング機械に、桁数n以下の二進数でコードを与えエミュレートさせ、PAのモデルのとりかた
によらず停止するまでのステップ数である自然数が存在するコードのうち、最後に停止するものの総ステップ数+1"
S(n)がBB(n)の性質を反映しているということは明らかだろう。
証明することは、
"(PAがω無矛盾 ∧ ある自然数Nについて∃n (n = S(N))がPAのモデルによらず真 ) => 矛盾"
したがって "自然数論PAがω矛盾 ∨ ∃n (n = S(N))がモデルによっては偽 )"
なお、NはPAだけから存在を証明できる自然数とする。 ここから内容
PAがω無矛盾 ∧ ある自然数Nについて∃n (n = S(N))がPAのモデルによらず真
と仮定する。
∃n (n = S(N))がPAのモデルによらず真であるから、
一階述語論理の完全性(恒真 => 証明可能)より、∃n (n = S(N))はPAから証明可能
※PAがω無矛盾なので、0 = S(N), 1 = S(N), 2 = S(N),...のうちのいずれかがPAから証明可能
これからすることは、 n = S(N)という式を具体的な論理式に変換し、
それができたら 0 = S(N), 1 = S(N),...の証明の試みを(順番に子プロセスを生成しながら)
並列的に行うチューリング機械が作れ、かつそのような機械が※より停止することが保障されることから、
S(N)を実際に計算できてしまうということを示し、一般的にS(n)は計算不能であることとの
矛盾を示すことである。 以下のように動作するチューリング機械Mを考える。
(1)自然数nが与えられると、桁数n以下の二進数を枚挙する。(0,1,10,11,...,111...111)
(2)それぞれの二進数について、それを万能チューリング機械にコードとして与えたものを、
一階述語論理の論理式に変換する。
(この感覚は、Cook-Levinの定理(充足可能性問題はNP完全問題である)を証明するために
(非決定性)チューリング機械をそっくり命題論理の論理式に置き換えたことの無い
人には理解しがたいかもしれない。)
ここで、ある二進数を渡されたとき万能チューリング機械がどんなPAのモデルのもとでも
停止するようなステップ数があるということを確認する必要がある。
一階述語論理の完全性より、その二進数を渡された万能チューリング機械がモデルに
よらず停止するなら、そのことをPAから証明可能である。
PAから証明可能なら、その二進数を渡された万能チューリング機械が停止状態になる
ようなステップ数aが存在する、という論理式の証明を(PAの妥当な論理式を枚挙することで)
試みるチューリング機械が停止する。
ゆえに、次に行うべきことは、
(3)(1)で枚挙した各二進数について、それを入力された万能チューリング機械が停止する
という意味の論理式を(2)で作った論理式を利用して作る
(4)(3)で作ったそれぞれの論理式について、その証明を試みるチューリング機械のコードを生成する
(5)(4)で作った各コードについても、それが停止するという意味の論理式を同様に作る
(6)(1)で枚挙した各二進数について、
"(5)で作った論理式(が真) => その二進数を万能チューリング機械与えたときに停止するまでに
かかるステップ数((2)で作った論理式を利用して作れる論理式) < x"
という論理式を作る。 (7)(6)で作った論理式を、すべて∧でつなげた論理式をP(x)として、
yを自由変数とする論理式"P(y)∧∀x(P(x) => y ≦ x)" を作る。
ここで作られている論理式が、まさしく
"任意の、コード長n以下の、いかなるPAのモデルでも停止するコードが停止するまでに
かかるステップ数よりも大きい最小の数はyである"という意味になっていることに注意しよう。
今まで漠然とy = S(n)と書いてきた式を、しっかり一階述語論理の論理式に直したものだといってもよい。
(8)k = 0とする。
(9)(7)で作った論理式を、y = S(n)と表すとして、k = S(n)の証明を試みる子プロセスを生成する
(親プロセスと子プロセスは並列に実行されるものとし、
子プロセスは親プロセスの動作による影響を受けないものとする)
(10)どの子プロセスも停止していないなら、kを1増やして(9)に戻る
(11)どれか1つでも子プロセスが停止したなら、その停止した子プロセスが証明した論理式から、
S(n)の値を得られるため、その値を返す。
(12)終了
Mが停止しない可能性があるとしたら、それは(9),(10)のループ処理で、無限ループすることであるが、
それは※よりありえない。よってMは任意のnについて停止する。 皆さんは筑駒中学の入試問題を小学生の知識だけで解けますか?
純粋な質問ですが、気分を害したらすみません、 ここで、チューリング機械Mを万能チューリング機械でエミュレートできるようにコード化したもの
を<M>とし、機械Mに自然数nを与えた場合のコードを、nを二進数にしたものを<n>として、
<M><n>と表記する。<M>のコード長をmとすると、mは普通の自然数であり、<n>のコード長はlog_2(n)
である。
よって <M><n> のコード長は m + log_2(n)であり、もしNが十分大きな普通の自然数ならば、
m + log_2(N) < N が成り立つ。
しかし、 <M><N> をエミュレートするとS(N)を返すので、コード長N以下なのにS(N)の値を返すという
点で、S(n)の定義と矛盾 (ベリーのパラドックスに似る)
したがって、背理法より、自然数論PAがω矛盾であるか、またはある程度大きな普通の自然数Nについて
S(N)の返り値は普通の自然数ではない。
よってある程度大きな普通の自然数Nについて、
"自然数論PAがω無矛盾ならば、BB(N)の値は普通の自然数(PAだけから存在を保障できる自然数)ではない"
証明終わり 前述の証明によって、PAがω無矛盾ならBB(n)はある程度大きな(それが10000なのか10^10なのかは分からないが)
nについて普通の自然数の値をとることができない、と分かった。
もしPAがω矛盾であるとするなら、BB(n)がPAだけから存在を保障できる自然数になっていても
おかしくないが、その場合はPAのモデルがすべて奇妙な性質の自然数を含んでいるということになる。
さて、>>462についてだが、前述の論法を応用すればラヨ関数についても同様のことが言える。
ラヨ関数において、論理式によって命名されたと言えるためには、その論理式をみたす自然数が
集合論のモデルのとり方によらず存在していなければならない。
一階述語論理の完全性から、モデルのとり方によらず存在しているなら、そのことを集合論から
証明可能である。
記号数n以下の論理式を枚挙して前述のチューリング機械Mと似たようなことをする機械を構成すれば、
もし集合論がω無矛盾なら前述のものと同様にラヨ関数Rayo(n)を計算する計算機になる。
しかし、このようなチューリング機械も、一階述語論理の論理式に変換できるから、
そこからラヨ関数の定義との矛盾を導ける。
二階述語論理以降なら完全性が成り立たないからこの論法が使えないのは確かだが、
二階述語論理以降は一階述語論理を包含していて、ラヨ関数より増加が速いはずだから
結局二階以上バージョンのラヨ関数を作っても普通の自然数を返すようにはならない、と言える。 提案されている急増加計算不能関数は、まずビジービーバー関数が常に普通に自然数を返してくれること
が前提となっているように思える。しかし、これは暗黙のうちに前提としていいほど確かなものでもないだろう。
ビジービーバー関数の定義を初めて知った時、みんなはその"あらゆる計算可能関数よりも大きい"
という性質に、その理屈には納得しても気持ち悪さを感じなかっただろうか。
結局のところ、ビジービーバーが大きかったのは、入力が大きいとき、もし返り値が存在するような
PAのモデルを選んでいれば、それが必然的に超準的自然数になるのであって、
いかなる普通の自然数よりも大きいという反則的な性質のものを返していたからだ、ということになる。
常識のように受け入れられているものについて疑問を投げかけてみるのも、大事なことではないだろうか。 超準的自然数は超準的なモデルに属するのであって、ふつうのモデルには属さないんじゃ 我々とは隔絶した存在である超準星人が考えるビジービーバー関数、とかなら
いかなる普通の自然数より大きいという下りはわからんでもない、いや、冗談でなく真面目に 計算可能な関数の集合は可算集合だし、定義可能な範囲であらゆる計算可能な関数より強い関数が
あってもおかしくない、というかあるべきと思うのだわ。
あらゆる定義可能な関数より強い定義可能な〜ってのがあったら気持ち悪い ビジービーバー関数を超準的な世界で考えるのであれば、停止するかどうかも有限時間の
範囲だけでなく超準的な時間も含めた範囲で考えるべきじゃなかろうか 他にも超準的な世界で考えるとなるといろいろと自明でないことがあって、
普通のビジービーバー関数より強いというのも自明でないかな ビジービーバー関数の全域性は証明できないわけだから、
PAで存在を証明しようとしてできなかった、というのは当然では 証明できないけど、あると信じて話を進めるかどうか、というだけの話 巨大な数って何に役立ってるのでしょうか?素数は暗号って聞いた >>486
ある程度以上の巨大さになってくると、数学の研究にちょっと役立つくらいで応用性は無いよ ビジービーバー関数の全域性は1階述語論理で記述できる以上恒真であれば証明できる △△△馬鹿板をスルのは不埒な行為であり、脳が悪くなります。そやしセンでもヨロシ。△△△
¥ >>454が連続して起こることで宇宙が熱的死を起こしても急に不死鳥のごとく復活する可能性が
考えられるという説を昔なにかの本で読んだ。 ビジービーバー関数の全域性を証明するためには「ビジービーバー関数が全域関数である」と
同値の公理を入れない限り無理では >>502
お前の前提としてる公理系って何よって話。 >>513
それを問われるのは>>499では
「証明できる」と言ってるんだから ★★★馬鹿板は悪い習慣であり、大脳が崩壊します。なので早く止めましょう。★★★
¥ >>514
特に断りがなければZFCとするのが通常じゃね?
ZFCならビジービーバーの全域性は証明できたはず。
ZFCでないというなら>>514が立場をはっきりさせないと。 ★★★馬鹿板は悪い習慣であり、大脳が崩壊します。なので早く止めましょう。★★★
¥ >>516
ビジービーバー関数 BB(n) は(最大でも) n=7910 でZFCの限界を超えるので
ZFCで全域性の証明は無理
https://arxiv.org/abs/1605.04343 ★★★数学徒は馬鹿板をしない生活を送り、日頃から真面目に学問に精進すべき。★★★
¥ sage入れるところ間違えてない?
再帰関数すべてを支配できる公理をもってないと証明はできないだろう。しかし1階述語論理の
完全性から、理論と言うか、1階述語論理、より限定してFOSTによって記述された定義からその
まま証明できるはずなんだ。
逆にメタな視点からみてビジービーバー関数の全域性が成り立たないってどういうことだろう
n状態のチューリングマシンは全部で有限個存在し、停止するか停止しないかのどちらかで
あって、停止しないものは除く。停止するチューリングマシンも有限だけ存在するのであれば
出力する値の最大値が存在する。 全域性が成り立つようwell definedに定義されていれば、全域性を証明するのに必要な理論は
定義の中に含まれているということです >>528
怖くてリンク踏めないがn=7910という数値は何に由来するんだろ? ■■■輝かしい日本の未来の学問は、馬鹿板をしない国民一人一人が作るもの。■■■
¥ >>542
なんかコーネル大学図書館ってサイト
普通の大学機関だと思う ■■■輝かしい日本の未来の学問は、馬鹿板をしない国民一人一人が作るもの。■■■
¥ これって7910状態のビジービーバーの値を特定できないって話ではないのか?
ビジービーバーの存在とは別の話なんじゃないのか?
うーん。 チャイティンのΩも何ビット以上特定しようとすると公理を追加する必要がある
みたいな話はどこかで聞いたことがあるが、それと似たようなもんかなぁ。 ■■■輝かしい日本の未来の学問は、馬鹿板をしない国民一人一人が作るもの。■■■
¥ >>546
>>528の説明であってるんじゃない?
ビジービーバー関数BB(n)のZFCで扱える領域を越えるnの値が大きくても7910
nはテープの長さで、2状態のチューリングマシンだって ■■■輝かしい日本の未来の学問は、馬鹿板をしない国民一人一人が作るもの。■■■
¥ >>549
7910はテープの長さじゃなくて状態数、2は状態じゃなくてテープアルファベットの種類だろ? ■■■輝かしい日本の未来の学問は、馬鹿板をしない国民一人一人が作るもの。■■■
¥ >>456
"可算無限濃度より大きく、連続体濃度より小さい濃度の個数"をチューリングマシンを用いて求める事は可能なのか?
可能なら(計算量はともかく)一意に決まるだろうし、不可能ならそれはただの「外部変数」なのでは? ■■■輝かしい日本の未来の学問は、馬鹿板をしない国民一人一人が作るもの。■■■
¥ 結局、普通に公理とか証明とかやっている時点で計算可能関数の範囲から出ない。
計算不可能関数を与える神託なりチューリングジャンプを持ってこないといけない。 ★★★馬鹿板を長くヤルと脳が悪くなって軽蔑される。そやし早く止めるべき。★★★
¥ 「この変数がいくつの括弧の内側にあるか」という定数を変数一つ一つの横に付けるようにすると多重リストアッカーマンのn重リストを対角化できる
ひっくり返して「この変数がいくつの括弧の外側にあるか」とすれば拡張し易くもなる
更に「この変数がいくつの括弧の外側にあるか、という定数が無茶苦茶大きい変数」を作り出す変数が出来れば拡張が出来る
配列表記と同じように「0になった変数を1以上にするときに変数に関数を写像」するようにすれば ……多次元配列BEAF、かな?
という感じの内容の関数を作ったのだが 具体的にはこんな感じ
[a,b,c,d,x,y]は非負整数
A=左式内の「a+1」を「a」にしたもの
一:=<{0[x≧弐≧y]:}*X>
壱:=<{X[x≧弐≧y]:}*X>
x>y のとき
[x≧弐≧y]=<{[x]X<{[x-1≧弐≧y]}*X>}*X>
[x≧ニ≧y]=<{<{[x-1≧弐≧y]}*X>[x]0}*X>[x-1≧ニ≧y]
x=y のとき
[x≧弐≧y]=<{[x]X}*X>
[x≧ニ≧y]=<{[x]0}*X>
ア式
(a+1:一:)=a+2
(0:壱:)=2
(a+1:b+1:壱:)=(A:b:壱:)
イ式
(a+1:一:b+1:壱:)=(a+1:一:A[A]A[A]0:b:壱:)
(a+1:一:b+1[c≧弐≧d+1][d+1]e[d+1]0:壱:)=(a+1:一:b+1[c≧弐≧d+1][d+1]A[d+1]A[d]A[d]0:壱:)
B式
(a+1:一:b+1[c]d+1[c≧ニ≧0][0]0:壱)=(a+1:一:b[c]d+1[c≧ニ≧0][0]0:b+1[c]d[c≧ニ≧0][0]0:壱)
(a+1:一:b+1[c≧ニ≧d+1][d+1]e+1[d]f+1[d≧弐≧0][d+e+1≧弐≧0]:壱)=(a+1:一:b+1[c≧ニ≧d+1][d+1]e[d]f+1[d≧弐≧0][d+1]e+1[d]f[d≧弐≧0][d+e+1≧弐≧0]:壱)
(a+1:一:0[b≧弐≧0]:c+1[d≧ニ≧0][0]0:壱:)=(a+1:一:A[b≧弐≧0]:c[d≧ニ≧0][0]0:壱:)
(a+1:一:b+1[c≧ニ≧d+1][d+1]0[d≧弐≧0][d+1]e+1[d≧ニ≧0][c≧弐≧0]:壱:)=(a+1:一:b+1[c≧ニ≧d+1][d+1]A[d≧弐≧0][d+1]e[d≧ニ≧0][c≧弐≧0]:壱:)
ア式はちょっと弄ってるけどアッカーマン
イ式は(a:b:c:d:……)の形で始めるレギオンぽいの
ロ式ハ式を合わせると多重リストアッカーマンを改造したBEAFぽいの
かなぁ 修正
イ式
(a+1:0:一:b+1:壱:)=(a+1:0:一:A[A]A[A]0:b:壱:)
(a+1:0:一:b+1[c≧弐≧d+1][d+1]e[d+1]0:壱:)=(a+1:0:一:b+1[c≧弐≧d+1][d+1]A[d+1]A[d]A[d]0:壱:)
B式
(a+1:0:一:b+1[c]d+1[c≧ニ≧0][0]0:壱)=(a+1:0:一:b[c]d+1[c≧ニ≧0][0]0:b+1[c]d[c≧ニ≧0][0]0:壱)
(a+1:0:一:b+1[c≧ニ≧d+1][d+1]e+1[d]f+1[d≧弐≧0][d+e+1≧弐≧0]:壱)=(a+1:0:一:b+1[c≧ニ≧d+1][d+1]e[d]f+1[d≧弐≧0][d+1]e+1[d]f[d≧弐≧0][d+e+1≧弐≧0]:壱)
(a+1:0:一:0[b≧弐≧0]:c+1[d≧ニ≧0][0]0:壱:)=(a+1:0:一:A[b≧弐≧0]:c[d≧ニ≧0][0]0:壱:)
(a+1:0:一:b+1[c≧ニ≧d+1][d+1]0[d≧弐≧0][d+1]e+1[d≧ニ≧0][c≧弐≧0]:壱:)=(a+1:0:一:b+1[c≧ニ≧d+1][d+1]A[d≧弐≧0][d+1]e[d≧ニ≧0][c≧弐≧0]:壱:) 再修正
B式
(a+1:0:一:b+1[c]d+1[c≧ニ≧0][0]0:壱)=(a+1:0:一:b[c]d+1[c≧ニ≧0][0]0:b+1[c]d[c≧ニ≧0][0]0:壱)
(a+1:0:一:b+1[c≧ニ≧d+1][d+1]e+1[d]f+1[d≧弐≧0][d+e+1≧弐≧0]:壱)=(a+1:0:一:b+1[c≧ニ≧d+1][d+1]e[d]f+1[d≧弐≧0][d+1]e+1[d]f[d≧弐≧0][d+e+1≧弐≧0]:壱)
(a+1:一:0[b≧弐≧0]:c+1[d≧ニ≧0][0]0:壱:)=(a+1:0:一:A[b≧弐≧0]:c[d≧ニ≧0][0]0:壱:)
(a+1:0:一:b+1[c≧ニ≧d+1][d+1]0[d≧弐≧0][d+1]e+1[d≧ニ≧0][c≧弐≧0]:壱:)=(a+1:0:一:b+1[c≧ニ≧d+1][d+1]A[d≧弐≧0][d+1]e[d≧ニ≧0][c≧弐≧0]:壱:) このスレの住民が本気でIncremental Gameを作ったらどんなゲームになるんだろう
あ、Incremental Gameっていうのは昔あったクリッカーみたいな数字が増えていくゲームのことね
インフレが激しいゲームでもせいぜい10の何万乗とかになるだけで、テトレーションレベルにも達しないんだよね 巨大数にインクリメント(足し算)しても意味が無いから、
マキシマム・ゲームになる。
× a += b;
○ a = MAX(a, b); 購入する施設?の陳腐化が早すぎる
足し算の施設を毎秒x個増やす施設を毎秒増やす施設を・・・でハイパー演算子レベルか 一つの変数で扱える限界は
整数型なら符号無し長長整数型で1.84e+19(18446744073709551615)
倍精度実浮動小数点型なら1.79e+308まで。ただし下位の精度はない フィッシュ氏の巨大数論ってPDFはただなの?
偉い太っ腹やな?。 欲張りクリーク列
y=x[2]となるとき、(y,x[2m])=(x[2],[2m])はGの辺ではないということになる。
これはその列がGのクリークになることと矛盾する。
よって列はそれ以上長くはならない。
単純グラフの方の関数は比例関数レベルの強さにしかならないんじゃないか。 久しぶりに来ました
このスレで一番大きなのはどれですか?
候補でも 一番大きいわけではないと思うけど、
>>5は俺的に会心の出来なので暇なら感想聞かせておくれ。 10年以上前にこのスレにいた「たろう」です。
ざっと「フィッシュ」氏のPDFをみました。
(以前はひらがなだったような気が)
計算可能な分野では、「タラノフスキーのC表記」が最大なままで、
特に進展はないのでしょうか。
どなたかが収束列をまとめてくれていた気がします。
計算不可能な関数の分野では、
「ラヨ数」「ビッグフット」「サスクワッチ」など初めてみる物があって、
ずいぶんと進歩したようですね。
これから解読します。
私も昔4ページほどで「ゲーデル数」「自然数から再帰的順序数への全射」などを定義し、巨大数をつくりましたが、
もう全く太刀打ち出来ない感じですかね。 計算可能な分野は、「どれだけ大きな再帰的順序数を作れるか」ということになるので、
ヒドラでいえば、「タラノフスキーのC表記」の収束列を利用して作ったヒドラが今のところ最強でしょう。
フィッシュ氏のPDFでプログラムによる表記の分野が載ってましたね。
私も以前C++でそういうことをやったりしました。
141文字でF[ε_0]、146文字でF[φ_ω,(0)]、180文字でF[Bachmann-Howard ordinal]相当を作りました。
これは「タラノフスキーのC表記」を利用しました。
「ローダー数」がどのくらいの大きさかはわかりませんが、どちらが大きいかは非常に興味があります。
時間があったら調べてみようと思います。 >>5 はどのくらいの大きさでしょうか?
コードを読むのが大変なので解説していただけると。
>>1 の「たろう氏のまとめ」の ●H[多変数C0で生成する順序数](n)
に F[ψ(Ω^ω)] 相当のヒドラが定義されています。
逆に、こちらの感想を聞かせて頂けると。 >>9 によると >>5 はΓ_0 ですか。
1時間半で大きさを評価した >>9 は何者?
私はrubyが読めないんで...
「タラノフスキーのC表記」も更新され続けてるようですね。
なんかいろいろと増えたり変わったりしてるみたい。 >>622
その後>>217で下方修正されてます。
たろう氏まとめのC0関数は私が順序数やlimの定義などをちゃんと理解してないので
なんとなくデカそうだという雰囲気は伝わってくるのですがデカさの実感がわかないです。
すいません。 Cを超えそうな候補にバシク行列とか、強配列表記とか、欲張りクリーク列の一番強いやつとか、
いくつかある。
Cの定義自体はたぶん更新されてなくて、以前の解析が間違っていたことにTaranovsky自身が
2014年あたりに気づいて、実はもっと強いのかもしれないというのがいまの状況 >>5はそもそもノーマルなヒドラゲームをベースにヒドラの高さも増えるようにしたら
面白いんじゃないかという発想で出来ています。
>>5の説明の通り、ノードにはランクがありランクが0でないノードが切り離されたとき、
高さの高いヒドラが追加されます。
ヒドラノードはコピーされますからランクの高いノードもルール通りコピーされます。
ランクの高いノードによって高さの高いノードが生まれ、
高さの高いノードによってランクの高いノードが大量にコピーされ…
という風に相乗効果ででかくなります。 すいません。具体例を書きこもうとしたのですがNGワード?とやらに引っかかって投稿できませんでした。
実際に>>5のスクリプトはリンク先で実行できるので実行してみてください。
一行目のa=1と80行目のx=generate(1,3)のところの数値をいじると設定を変えられます。
aはノードがコピーされる回数と高いランクが消されたときの追加されるツリーの高さを表していて、
generateの第一引数が初期ノードのツリーの高さ、第二引数が初期ノードのランクとなります。
ランク0のノードが()で表され、ランク1のノードが[]で表され、ランク2のノードが<>で表され、ランク3のノードが{}で表されます。 >>5
F[ε_ω] じゃないかな?
いまいち効率が良くない 5には続きがあって5を超ヒドラ第一段階と呼びます
そしてランクを整数ではなく超ヒドラ第一段階に拡張したものを超ヒドラ第二段階と呼びます
同様に第三段階、第四段階と定義していき第n段階で真超ヒドラとなります ありがとうございます
順序数はε0くらいまでしかちゃんと理解してないのであれですが
そんな私の作った関数にしては巨大になったんじゃないかと思っています [いいね]ありがとうございます。
いつか順序数もちゃんと理解したいと思ってますが、説明読んでもいまいちピンときません。
ε0以下の順序数は通常のヒドラゲームの木と対応がつくのでなんとなくわかるのですが。 >>634 たろうさん、お久しぶりです。あの巨大数ミーテイングから10年たちますね。
あのミーティングを主催した小林銅蟲さんの「寿司 虚空編」が出版されて重版となり、
あの頃に書き始めた「巨大数論」は書籍版も出しました。
http://gyafun.jp/ln/
PDF は相変わらず無料で読めます。あのミーティングでポチさんに教えてもらった
ブーフホルツのヒドラも、当時はよくわかりませんでしたがこの本で紹介しました。
7章の後半には、まだ十分に大きさの比較ができていないものもありますので、
読んでいただいて、なにか気がついたことがあれば教えてください。 おお〜ふぃっしゅさん!
本物の書き込みをみれるとは感激! おお、たろう氏御無沙汰です。
みんな立ち去ってしまったと思ってたけど
ROMってただけで巨大数を愛する気持ちは変わってなかったんだな >>636
ふぃっしゅさん、お久しぶりです。
>>638
もやしっ子さん、お久しぶりです。
お二人とも、出版おめでとうございます。
あの時から10年ですか。
浦島太郎状態のたろうでした。 浦島太郎の方でしたか。
「帰ってきたウルトラマン」かと思っていました。 だいぶ怪しいからここに投下
KP+There exist Recursively Mahlo ordinals=CoC(文脈にΠ_0-文のみ)?
KP+There exist Recursively Weaky Compact ordinals=KP+Π_3-Reflection
Degrees of Reflection=KP+Π_n-Reflection=ZFC\P?=pDAN?
Z_2=DAN?
ZFC
ZFC+There exist Mahlo cardinals=CoC(文脈にΠ_n-文を含む)?
Taranovsky's C ?
Cはもっと弱いかもしれない。 ω:最初の極限順序数
X:0個以上の0以上の整数または順序数
a,b,n:0以上の整数または順序数
x#y:y個のx
{0}=ω
{a+1}=ω^{a}
{0#(n+1),0}={ω#(n+1)}
{0#(n+1),a+1}={{0#(n+1),a}#(n+1)}
{X,b+1,0#(n+1)}={X,b,ω#(n+1)}
{X,b+1,0#n,a+1}={X,b,{X,b+1,0#n,a}#(n+1)}
[0]={ω#ω}
[a+1]={[a]#[a]}
[0#(n+1),0]=[{ω#ω}#(n+1)]
[0#(n+1),a+1]=[[0#(n+1),a]#(n+1)]
[X,b+1,0#(n+1)]=[X,b,{ω#ω}#(n+1)]
[X,b+1,0#n,a+1]=[X,b,[X,b+1,0#n,a]#(n+1)] CoC(文脈にΠ_0-文のみ)って自分で書いておきながら何言ってるのか分からない。
hypcos氏はCはZ_2と同等かより弱いとみているようだ おお、古参メンバーさんたち何年ぶりかの生存レスですか
かく言う自分も12、3年ぐらいも前から巨大数スレの住人になってて、
今までぼちぼちROM続けてます ω={全ての自然数より大きな最初の極限順序数}
ε_0=ω^ω^ω^…{ω個}…^ω^ω
A=ε_0^ε_0^ε_0^…{ω個}…^ε_0^ε_0
B=ω^ω^ω^…{ε_0個}…^ω^ω
AとBはどちらが大きいの? Bのほうはそもそもwell definedなんだろうか B=ε_0
ω^ε_0=ε_0なので、ω個から増えない ω^ω・・・ω^ε_0=ε_0
有限の高さの指数タワーならわかるけど超限の高さの場合は自明でないと思う >>658
α=ω^α を満たす2番目の極限順序数 強配列表記の雑な説明
テトーレーション配列まではだいたいBEAFといっしょ、テトーレーション配列という言い方はしてないけど
ドット . または{1^.}(わかりづらいけどドットをすこし上に上げる)をテトーレーション空間の区切りとして使う。
さらに二次元方向のテトレーション空間の区切りは{2^.}、3次元で{3^.}、以下{1{2^.}2^.}とやっていって
ε_1まで。
つぎに{1^.}を{1´2}と表し、´2がテトレーション空間の区切りを意味するものとする。
すると´3でペンテーション空間の区切りを表すようになったり{1{1'1'2^'}2}となったりあれやこれやで
θ(ε_{Ω+1})まで
さらに{1''2}とか{1'''2}とかいう区切りを導入していってθ(Ω_ω)まで {1´2}がテトレーション空間の1次元方向の区切り、{2´2}で2次元、{3´2}で3次元
{1,2´2}でω次元方向への区切り 強配列とバシクはBEAFとは一線を画すと思ってる
それの本質は何か
それを語ってくれるのはほんとにうれしい 強配列とバシクまでいくと本人の考えを辿るのが難しい
発想をどうにか共有できたらなと思う
哲学というか 俺にはBEAFも難しいわ
アッカーマンは辛うじてわかる ビジービーバーより小さいのしか語られないのはなんでたぜ やっぱ具体的に計算する方法が無いのが痛いんじゃない バシク行列は展開することである素体を繰り返すことになるけれど、この素体がどんどん複雑になる
性質を加えればさらに強化できるのでは、
というアイディアが浮かんだけど、すでに行を増やす操作が間接的にそういう役割を果たしているんだろう >>662ペンテーション空間というものはもっと複雑かもしれん、φ(2,0)になるみたいな でもビジービーバーより小さい数しか作れないんでしょ? 計算可能関数はビジービーバー関数より弱いから競わせないでしょ。勝負はついているもの。 アルゴリズムがわかる方法で定義する
という条件はない 大きな実数を探索って、スレの指向は総じてが正しいか。
話題はこれに限らず自由に出せて、計算可能関数が今ホットだからと言いたかったが… じゃあ条件を勝手に付け加えて、
大きな素数とか大きな友愛数とかを語りはじめても良いのかな >>680
計算不可能関数も定義上は"ある一つの実数"を定義するものだもんな
やっぱり不思議な概念だわ
Wikipediaにあるビジービーバーの計算結果? ってどういう意味なんだろ
やっぱりわからなくなってきた Σ:ビジービーバー関数
n:自然数
f(1)=Σ(2)
f(n+1)=Σ(f(n))
S=f(100) 計算不可能でも、ある数を返すんだろうなって事は何となく分かる
ただ、この計算可能性の概念が数の強さからきているのかそれとも関数の性質からきているのかがイマイチようわからん
ある計算不可能関数によって返されると予想される数の強さがある計算可能関数で返される数より弱い、なんてこともあるのかな f(n) := Σ(n) の1の位
は値は小さいけど
恐らく計算可能ではない >>683構わないだろうがたいがい既存の理論で間に合いそう Σをビジービーバー関数としfを計算可能な無限に発散する単調増加関数とすると
f(Σ(x))はやはり全ての計算可能な関数より増加率が高いといえるか? >>687
>>688
ありがとう
計算不能関数を越える計算可能関数が見つかるといいな
見つからないことが証明されてしまわないことを祈ってる >>690
そりゃそうだ
>>691
Σ(n)を超える計算可能な関数が無いことの証明は簡単 ふぃっしゅ数バージョン4の神託機械の配備のされかたがよく分かんないんだけどどういうこと?関数って言ってるけど関数も何もテープとオートマトンしかないよね
バージョン7も関数fが出てきてよく分からない。fの定義はどこかにラヨ数で許されてる記号を使って記述するの?
どっちもビジービーバー関数とラヨ関数を書ける部品がほしい、っていう気持ちはなんとなく分かるんだけど F4もF7も定義は書いてない
おそらくふぃっしゅ氏の能力では厳密に定義出来ないと思われる
つまり、ふぃっしゅ数は定まっていない >>691
> 計算不能関数を越える計算可能関数が見つかるといいな
停止性問題が分かってないな…… 今巨大数界隈で主に何が分かってないのか分からない
なんかこう頭打ち感があるような F4はチューリングマシンに、現在のヘッダの位置から右に並んだn個の1を読み取り
読み終わった0の位置からさらにみぎがわにBB(n)個の1を入力(すでに1になっている場合は
上書き)して適当な次の状態に移行するという一連の動作をこなすオラクルな
状態を追加する、とかすることで簡単にwell definedにできる。
F7は式の中でラヨ関数を扱えるようにするとか、そのまんまですでにwell definedになってるんじゃないか? F7は神託式で拡張する方針をとってるけど、ラヨ階層を定義したならもう式の中で
ラヨ階層を扱えることにしたほうがよかったな。
FOOTでいうV_{Ord*2}を対角化した強さになるか? >>698
その「fはBB(n)です」「fはラヨ関数です」という身もふたもない定義がされてたら分かるんだけど、「f」って抽象的に書かれてるとそのfの選び方がよく分からない。
なんでもありにしちゃうとF4のfにラヨ関数のオラクル入れたらF7と同じくらい強くなるしリトルビッゲドン入れたらF7抜くよね ラヨ関数も細部は定義されてないように見えるけど
原文だと書いてあったりする? ラヨ関数は1番しっかり定義されてる部類じゃない?
どのページにも再帰的な式で定義が書いてあるぞ。 >>700
F4分かりました。再帰的定義の最初にf=x+1ってありましたね。でs(1)の定義に出力はそれを使ったビジービーバー関数とあるのでビジービーバー関数になります。ラヨ関数とかは出てきません。 定義されてないっていう人は、何を見て定義されてないって言ってるんだろうね >>700
関数fから関数gへの写像s'(1)の定義が書かれているわけだから、fとして
なんでも選ぶことができる。
>>703
s'(1)は関数ではなくて関数から関数への写像なので、「s'(1)がビジービーバー」は
正しくない。s'(1)f がビジービーバー関数となる。
そして、s'(1)^2 f は2次のビジービーバー関数、といったような計算はwikiにも
巨大数論にも書いてあるので、よく読めばわかるはず。 矢印表記やハイパー演算の自然な拡張といえば
チェーン表記、強配列表記(LAN)、BEAF/BAN(線形配列)あたりが思い浮かぶが
他にも何か良さそうなのあるかな?
自分でも考えてみたがやはりそう簡単に思いつくものではなかった
というかまず上の3つがよく出来過ぎてるわ… Σ(n) := ビジービーバー関数
a,b,n := 0以上の整数
X := 0個以上の0以上の整数
a;b := b個のa
f()=Σ(10^10^100)
f(0)=Σ(f())
f(a+1)=Σ(f(a))
f(0;n+1,0)=f(f();n+1)
f(0;n+1,a+1)=f(f(0;n+1,a);n+1)
f(X,b+1,0;n,0)=f(X,b,f();n+1)
f(X,b+1,0;n,a+1)=f(X,b,f(X,b+1,0;n,a);n+1)
s=f(f();f())
sはビジービーバー関数にグーゴルコンプレックスをぶち込んだ値を基に
再帰的に多変数化させて肥大化させてみた
これはデカイだろう ゴミ言うのはひどいが、再帰定義不可能なのが計算不可能レベルの強さであって、
計算不可能な関数を再帰で組み立てていくのはあんまり意味がない あそこまでやっても巨大数的なスケールではほぼ変わってないも同然なのか… f(x)<g(x)ならf(g(x))<g(f(x))といえるか? ビジービーバー関数は、x>yの時、Σ(x)>Σ(y)は成り立たないの? f(x)<g(x)ならf(g(x))<=g(f(x))といえるか。
ならどう? あまり実用的でないけど、ウルトラパワーで関数の強さを比較することもできるだろう。 f(x)=x^2
g(x)=3^x
f(g(1))>g(f(1)) うーん。
g(x)がf(x)を支配するならg(f(x))はf(g(x))を支配するか?
だったら成り立つかなぁ? a<b で f(x)=ax, g(x)=bx とか f(x)=x^a, g(x)=x^b だと f(g(x)) = g(f(x)) ですが、
f(x)=a^x, g(x)=b^x だとxがある値より大きいときに f(g(x)) > g(f(x)) ですね
https://twitter.com/kyodaisuu/status/866735484302639104 なんと
フィッシュさんが既に解決してた問題でしたか 巨大数論p.70参照
あるnがあって、x>nであればf(x)>g(x)が成り立つ時、fはgを支配する(dominate)と言う。 φ(1,0)=ε_0 φ(1,1)=ε_0*ω
φ(1,φ(φ(1,0)))=ε_0*ε_0 φ(1,φ(φ(1,0)+φ(φ(1,0))))=ε_0^ε_0
φ(1,φ(φ(1,0)*2))=ε_1 φ(1,φ(φ(1,0)*2+φ(φ(1,0)+φ(φ(1,0)*2))))=ε_1^ε_1
φ(1,φ(φ(1,0)*2+φ(φ(1,0)+φ(φ(1,0)*2)*2)))=ε_2
φ(1,φ(φ(1,0)*2+φ(φ(1,0)+φ(φ(1,0)*2)*3)))=ε_3
φ(1,φ(φ(1,0)*2+φ(φ(1,0)*2)))=ψ(Ω)
φ(1,φ(φ(1,0)*2+φ(φ(1,0)*2)*2))=ψ(Ω+1)
φ(1,φ(φ(1,0)*3))))=ψ(ε_{Ω+1}) φ(1,φ(φ(1,0)*2+φ(φ(1,0)+φ(φ(1,0)*2)*3)))=ε_3 から間違ってるかも ε_nの収束列ってこういう意味であってる?
ε_0 1,ω,ω^ω,ω^ω^ω
ε_0+ω ε_0,ε_0+1,ε_0+2,ε_0+3,⋯
ε_0×2 ε_0,ε_0+ω,ε_0+ω^ω,ε_0+ω^ω^ω,⋯
ε_0×ω 0,ε_0×1,ε_0×2,ε_0×3,⋯
ε_0^2 ε_0,ε_0×ω,ε_0×ω^ω,ε_0×ω^ω^ω,⋯
ε_0^ω 1,ε_0,ε_0^2,ε_0^3,⋯
ε_0^^2 ε_0,ε_0^ω,ε_0^ω^ω,ε_0^ω^ω^ω,⋯
ε_0^^ω 1,ε_0,ε_0^ε_0,ε_0^ε_0^ε_0,⋯
ε_0^^^2 ε_0,ε_0^^ω,ε_0^^ω^^ω,ε_0^^ω^^ω^^ω,⋯
ε_0^^^ω 1,ε_0,ε_0^^ε_0,ε_0^^ε_0^^ε_0,⋯
ε_1=ε_0^^ω
ε_2=ε_1^^ω=ε_0^^^ω
ε_3=ε_2^^ω=ε_1^^^ω=ε_0^^^^ω もしあっていたらε_nはωだけで表現出来るね
ε_0=ω^^ω
ε_1=ω^^^ω
ε_2=ω^^^^ω
ε_3=ω^^^^^ω つか、俺は根本的なところが分かってないんだが、順序数ってつまるところ集合なんでしょ?
収束列ってホントに厳密に集合を定義してるといえるの? 収束列による順序数定義の説明は、感覚的に理解するための便宜的なもので、
順序数の厳密な定義を知るにはみっちりと集合論をやらないと、では 収束列で順序数を定義することはできるが順序数で収束列を定義することはできない、では >>732
どういう定義で違うって言ってるんだろう? 煽りでなく、単純に気になる >>736
なるほど、こうなるのか
ε_0^^1=(ω^^ω)
ε_0^^2=(ω^^ω)^(ω^^ω)
ε_0^^3=(ω^^ω)^(ω^^ω)^(ω^^ω)
ε_1^^1=((ω^^ω)^^ω)
ε_1^^2=((ω^^ω)^^ω)^((ω^^ω)^^ω)
ε_1^^3=((ω^^ω)^^ω)^((ω^^ω)^^ω)^((ω^^ω)^^ω)
ε_2^^1=(((ω^^ω)^^ω)^^ω)
ε_2^^2=(((ω^^ω)^^ω)^^ω)^(((ω^^ω)^^ω)^^ω)
ε_2^^3=(((ω^^ω)^^ω)^^ω)^(((ω^^ω)^^ω)^^ω)^(((ω^^ω)^^ω)^^ω) >>740
どういう定義で正しいと思ってるんだろう?
φ(1,1) = ε_1 >> ε_0*ω >>742
あれは普通のφ関数をReflection並みの強さが得られるように改造したものなんです。 φ関数のことです。たぶんバシク氏がすでに通った道。
解析結果は>>730であってたかな たしかにTaranovsky的に妥当な式で考えるかどうかで結果が異なる Veblen関数とは関係ない、全然別の関数ってことね テトレーションが左結合ならそれでよかったんだが、↑^nは右結合でした
じゃあ左結合な↑^nを↓^nとかオレオレ定義してやればいいじゃないの、と思って、うわーっやったらζ_0でまた右結合になって頓挫している風景が↓です
https://i.imgur.com/R5Spa59.jpg 妥当な式の判定を間違えていて、>>743が正しいです。すみません。
以下、
φ(1,φ(φ(1,0)))=ε_{ε_0}
φ(1,φ(φ(1,0)*2))=ε_{ε_1}
φ(1,φ(φ(1,0)*2+φ(φ(1,0)+φ(φ(1,0)*2))))=ε_{{ε_1}^2}
φ(1,φ(φ(1,0)*2+φ(φ(1,0)+φ(φ(1,0)*2)*2)))=ε_{ε_2}
φ(1,φ(φ(1,0)*2+φ(φ(1,0)+φ(φ(1,0)*2+φ(φ(1,0))*2))))=ψ(Ω)
φ(1,φ(φ(1,0)*3))=ψ(ε_{Ω+1})
φ(1,φ(φ(φ(1,0)+1)))=φ(1,φ(φ(1,0)*ω))=ψ(Ω_ω)
φ(1,φ(φ(φ(1,0)*2)))φ=φ(1,φ(φ(1,0)^2))=ψ(ψ_I(0))
考え方はDegrees of Reflectionと同じです。定義をどうにかしないと ビジービーバー関数の存在が証明出来ないってどういうことですか?
どのチューリングマシンも有限ステップで止まるか止まらないかの2種類しかなく、
有限ステップで止まるチューリングマシン有限個の中から最大値を選ぶのも普通に出来ると思うのですが >>753
有限ステップで停止するチューリングマシンは無限個あるよ。 それぞれの状態の数に対しては有限個しか存在しないんじゃないの? 有限個の整数の中に最大値が存在する
当たり前ですね ラドーさんがず〜っと昔にビジービーバー関数の存在を証明してます >>155あたりへの亀レスになるけど、実際100億年以上の時間をかけて、まったくランダムに粒子が
飛び交っている状態から、人類の脳のような割と高度な証明をそれなりに意図して出力できる
形式体系が出来上がっていると言えるんだな ビジービーバー関数がどうこう言ってたあれって、超準的数と有限の普通の自然数をごっちゃに
してるのがそもそもの間違いなんじゃ >提案されている急増加計算不能関数は、まずビジービーバー関数が常に普通に自然数を返してくれること
が前提となっているように思える。
前提と言うか、そういう定義だよな よく分かってない人がよく分からない理屈で否定してるだけかな?
Σ^9 (9) も、厳密に定義されたあるひとつの実数です
普通の帰納的定義では絶対に到達出来ない大きさの 定義自体は非常に簡単です
これでいて非常に大きな数が作れる
この手法を使わない手はないですね >>757
> ラドーさんがず〜っと昔にビジービーバー関数の存在を証明してます
ビジービーバー関数が数学の関数の意味でwell-definedな定義を持つのは古典論理では明らかだけど
構成的数学(排中律あるいは二重否定の除去を認めない直観主義論理に基づき公理としては無制限の通常の選択公理は認めない)の
立場からすると、ビジービーバー関数の存在って証明できるのかな? 排中律を認めなかったら定理が存在しなくなるんじゃなかった?
FOSTで超準モデルの存在を否定できない線も考えてみたけど、2階算術で
自然数論の超準モデルを否定できるからラヨ関数の強さが揺らぐ問題でもなかった。 昔フラクタル言ってたのがいたけど、多重再帰関数とかある意味フラクタルだよな 書き下すと形がフラクタルになる演算方法があれば、有限スケールでどこまでも大きな数を作れそうだな ラムダ計算でもヒドラでもフラクタルでも、○○を使って巨大数を表記するor定義する
というのは表現の問題であって、新しい表現を使えば新しい強さを得られるかは別問題、
逆にすでに定義されている巨大数やシステムをラムダ計算なりヒドラなりフラクタルなりで
表現してもよし ビジービーバー関数は1〜4まではわかってるけど
ヲヨ関数の特殊値って求められているのかな 大きい数よりシンプルでスマートなシステムの方が興味ある 順序数ってどこまででも大きいのはあるけど、
全部の順序数を表現できるような構文があると仮定すると
ゲーデルの不完全性定理に抵触するとかそんな感じなんですか? 可算種有限文字数で記述できる順序数の数は可算種類
ざっくり言って、計算可能な関数しか定義できない言語のモデルでは、ω^CKと第一非可算順序数の
区別がつかない。
1階述語論理のモデルではすべての順序数が(外から見て)Ωの中に収まることも考えられる。 順序数の大きさを競うスレじゃないから
巨体な実数を作るのに利用出来る順序数しか意味がない a,c,n := 0以上の整数
X := 0個以上の0以上の整数
Y := 1個以上の0以上の整数
a#b := a個のb
N := 十分に大きな自然数
g(x) := 1変数の増加関数
f(…) は、g(N)に対してω^ωの強化
f(…)(…) は、g(N)に対してω^(ω×2)の強化
f(0)=N
f(a+1)=g(f(a))
f(0#(n+1),0)=f(N#(n+1))
f(0#(n+1),a+1)=f(f(0,a)#(n+1))
f(X,b+1,0#(n+1))=f(X,b,N#(n+1))
f(X,b+1,0#n,a+1)=f(X,b,f(X,b+1,0#n,a)#(n+1))
f(0)(0)=f(N#N)
f(0)(a+1)=f(f(0)(a)#f(0)(a))
f(0#(n+1),0)(0)=f(N#(n+1))(N#N)
f(0#(n+1),0)(a+1)=f(f(0#(n+1),0)(a)#(n+1))(f(0#(n+1),0)(a)#f(0#(n+1),0)(a))
f(X,b+1,0#n)(0)=f(X,b,N#n)(N#N)
f(X,b+1,0#n)(a+1)=f(X,b,f(X,b+1,0#n)(a)#n)(f(X,b+1,0#n)(a)#f(X,b+1,0#n)(a))
f(Y)(0#(n+1),0)=f(Y)(N#(n+1))
f(Y)(0#(n+1),a+1)=f(Y)(f(Y)(0,a)#(n+1))
f(Y)(X,b+1,0#(n+1))=f(Y)(X,b,N#(n+1))
f(Y)(X,b+1,0#n,a+1)=f(Y)(X,b,f(Y)(X,b+1,0#n,a)#(n+1)) 繰り返しの単位を強化するより繰り返しの単位を変化させる方法を強化したほうが
強くなるというのはなんとなくわかる>バシク行列系
でもそろそろ、ある単位を変化させながら繰り返す操作よりも上に来る概念が欲しい バシク行列ある意味チューリング完全よりは弱いプログラミング言語ということになる。
チューリング完全よりは弱いがバシク行列系よりは強い言語を所望する。 >>788
「繰り返しの単位を変化させる方法を強化させる方法」を強化する >>790
そういう単純な話でなくて・・・というかそうやって重ねるのはもはや意味がないレベルかと そうやって重ねるのがもはや意味がない関数
っていうのを数学的に表現すればいい 意味がないというよりは、システムを強くするにはいろんなやり方があるけれど、
そういうのは+1程度の意味しかないということだな。
たしかにシステムを強くしようとすると必然的にそうなるけど、そういうのは基本中の基本
であってもはや本質ではないって感じ 今までは原始再帰とか、ペアノ算術とか、型理論とか、ZFC+巨大基数公理とか、それぞれの
意味から具体的に巨大数を出力する何かしらの形を作ることができたけど、バシク行列は
もはや意味論的に人類未踏の領域に入ってるかもしれない。
・・・というのはまだ先走り過ぎかもしれない >>789
なんでチューリング完全より弱い方が良い?
巨大な実数を検索するスレだぞ いわゆる計算可能性で言えば
>>764も計算可能
ただ単に計算可能でない関数が表現に出てくるだけ 無勝負に持ち込まれなければやり方次第で二局やって誰でも一勝はできるよ。 >>804
そんなゴミみたいな数
1スレッド目じゃないんだから “[“ と “]” だけでどこまで大きな数が表現できるか
[]=1
[][]=2
[][][]=3
[[]]=ω
[[]][]=ω+1
[[]][][]=ω+2
[][[]]=ω×2
[][[]][]=ω×2+1
[][[]][][]=ω×2+2
[][][[]]=ω×3
[][][[]][]=ω×3+1
[][][[]][][]=ω×3+2
[[]][[]]=ω^2
[[]][[]][]=ω^2+1
[[]][[]][][]=ω^2+2
[[]][][[]]=ω^2+ω
[[]][][[]][]=ω^2+ω+1
[[]][][[]][][]=ω^2+ω+2
[[]][][][[]]=ω^2+ω×2
[[]][][][[]][]=ω^2+ω×2+1
[[]][][][[]][][]=ω^2+ω×2+2
[][[]][[]]=ω^2×2
[][[]][[]][]=ω^2×2+1
[][[]][[]][][]=ω^2×2+2
[][[]][][[]]=ω^2×2+ω
[][[]][][[]][]=ω^2×2+ω+1
[][[]][][[]][][]=ω^2×2+ω+2
[][[]][][][[]]=ω^2×2+ω×2
[][[]][][][[]][]=ω^2×2+ω×2+1
[][[]][][][[]][][]=ω^2×2+ω×2+2
[][][[]][[]]=ω^2×3
[][][[]][[]][]=ω^2×3+1
[][][[]][[]][][]=ω^2×3+2
[][][[]][][[]]=ω^2×3+ω
[][][[]][][[]][]=ω^2×3+ω+1
[][][[]][][[]][][]=ω^2×3+ω+2
[][][[]][][][[]]=ω^2×3+ω×2
[][][[]][][][[]][]=ω^2×3+ω×2+1
[][][[]][][][[]][][]=ω^2×3+ω×2+2
[[]][[]][[]]=ω^3
[[]][[]][[]][[]]=ω^4
[[][]]=ω^ω [[][]][]=ω^ω+1
[[][]][][]=ω^ω+2
[[][]][[]]=ω^ω+ω
[[][]][[]][[]]=ω^ω+ω^2
[[][]][[]][[]][[]]=ω^ω+ω^3
[][[][]]=ω^ω×2
[][][[][]]=ω^ω×3
[[]][[][]]=ω^(ω+1)
[[]][[]][[][]]=ω^(ω+2)
[[][]][[][]]=ω^(ω×2)
[[][]][[][]][[][]]=ω^(ω×3)
[[][][]]=ω^ω^2
[[][][]][[][][]]=ω^(ω^2×2)
[[][][][]]=ω^ω^3
[[][][][][]]=ω^ω^4
[[[]]]=ω^ω^ω
[[[]]][[[]]]=ω^(ω^ω×2)
[[[]][]]=ω^ω^(ω+1)
[[[]][]][[[]][]]=ω^(ω^(ω+1)×2)
[[[]][][]]=ω^ω^(ω+2)
[[][[]]]=ω^ω^(ω×2)
[[][][[]]]=ω^ω^(ω×3)
[[[]][[]]]=ω^ω^ω^2
[[[]][[]][[]]]=ω^ω^ω^3
[[[][]]]=ω^ω^ω^ω
[[[][]]][[[][]]]=ω^(ω^ω^ω×2)
[[[][]][]]=ω^ω^(ω^ω+1)
[[[][]][]][[[][]][]]=ω^(ω^(ω^ω+1)×2)
[[[][]][][]]=ω^ω^(ω^ω+2)
[[[][]][[]]]=ω^ω^(ω^ω+ω)
[[[][]][[]]][[[][]][[]]]=ω^(ω^(ω^ω+ω)×2)
[[[][]][[]][]]=ω^ω^(ω^ω+ω+1)
[[[][]][[]][]][[[][]][[]][]]=ω^(ω^(ω^ω+ω+1)×2)
[[[][]][[]][][]]=ω^ω^(ω^ω+ω+2)
[[[][]][][[]]]=ω^ω^(ω^ω+ω×2)
[[[][]][][[]]][[[][]][][[]]]=ω^(ω^(ω^ω+ω×2)×2)
[[[][]][][[]][]]=ω^ω^(ω^ω+ω×2+1)
[[[][]][][][[]]]=ω^ω^(ω^ω+ω×3)
[[[][]][[]][[]]]=ω^ω^(ω^ω+ω^2)
[[][[][]]]=ω^ω^(ω^ω×2)
[[[]][[][]]]=ω^ω^ω^(ω+1)
[[[]][[]][[][]]]=ω^ω^ω^(ω×2)
[[[][]][[][]]]=ω^ω^ω^ω^2
[[[][]][[][]][[][]]]=ω^ω^ω^ω^3
[[[][][]]]=ω^ω^ω^ω^ω [[[][][]]][[[][][]]]=ω^(ω^ω^ω^ω×2)
[[[][][]][]]=ω^ω^(ω^ω^ω+1)
[[[][][]][][]]=ω^ω^(ω^ω^ω+2)
[[[][][]][[]]]=ω^ω^(ω^ω^ω+ω)
[[[][][]][][[]]]=ω^ω^(ω^ω^ω+ω×2)
[[[][][]][[]][[]]]=ω^ω^(ω^ω^ω+ω^2)
[[[][][]][[]][[]][[]]]=ω^ω^(ω^ω^ω+ω^3)
[[[][][]][[][]]]=ω^ω^(ω^ω^ω+ω^ω)
[[[][][]][[][]]][[[][][]][[][]]]=ω^(ω^(ω^ω^ω+ω^ω)×2)
[[[][][]][[][]][]]=ω^ω^(ω^ω^ω+ω^ω+1)
[[[][][]][[][]][[]]]=ω^ω^(ω^ω^ω+ω^ω+ω)
[[[][][]][[][]][[]][]]=ω^ω^(ω^ω^ω+ω^ω+ω+1)
[[[][][]][[][]][][[]]]=ω^ω^(ω^ω^ω+ω^ω+ω×2)
[[[][][]][[][]][[]][[]]]=ω^ω^(ω^ω^ω+ω^ω+ω^2)
[[[][][]][][[][]]]=ω^ω^(ω^ω^ω+ω^ω×2)
[[[][][]][[]][[][]]]=ω^ω^(ω^ω^ω+ω^(ω+1))
[[[][][]][[]][[]][[][]]]=ω^ω^(ω^ω^ω+ω^(ω+2))
[[[][][]][[][]][[][]]]=ω^ω^(ω^ω^ω+ω^(ω×2))
[[[][][]][[][]][[][]][[][]]]=ω^ω^(ω^ω^ω+ω^(ω×3))
[[][[][][]]]=ω^ω^(ω^ω^ω+ω^ω^2)
[[][][[][][]]]=ω^ω^(ω^ω^ω+ω^ω^3)
[[[]][[][][]]]=ω^ω^(ω^ω^ω×2)
[[[]][[]][[][][]]]=ω^ω^(ω^ω^ω×3)
[[[][][]][[][][]]]=ω^ω^ω^ω^ω^2
[[[][][][]]]=ω^ω^ω^ω^ω^ω
[[[][][][][]]]=ω^ω^ω^ω^ω^ω^ω
[[[[]]]]=ε_0 [[[[]]]](4重ネスト)がε_0なので、まだまだ余裕で大きくなると思うけど疲れたのでここまで 結論を言えばどこまでも大きな可算順序数を表現できる 通常のヒドラより強いてことだよね
どこで強くなってるんだろう >>811
可算順序数に限らず、定義可能な順序数全てを表現出来る
その定義した順序数を [ などと表記することにすればいい
じゃあ指定した順序数未満を全て表現可能な[ ]2文字からなる表記法があるか?
その具体例を示せ
という問題だと急に難しくなる ω^3+ωは
[[]][[]][][[]]で、
ω^3+ω^2+ωは
[[]][][[]][][[]]
って感じで合ってる?
すごいなこれ >>807
ここは大きな実数を探索するスレッドですよ ε_0みたいな極小順序数、いまさらどうでもよくね? >>807-809を素直に解釈すれば[[[[...[]...]]]]は何になるの? ええと、有限数可算種文字での話をしているとして、
どこまでも大きな可算順序数までを表現する方法は存在するけど、第一非可算順序数までの
すべての可算順序数を表現することはできない、ということね。 >>764は計算可能部門では実質超えられない数だろう。
それにでかさがすべてというもんでもない。 Σ^1000 (1000)を計算可能な言語で表そうとしたらΣ^999(1000)文字位ひつようかな? >>821
いや、でかさが全てだ
ここはそういうスレ Λ(0)=Σ^[1000](1000)
Λ(n+1)=Σ^[Λ(n)](Λ(n))
Λ(1000) >>820
ω_2^CK までを表現する具体例をよろしく! でかさが全てと言ってしまうと探索の幅はえらく狭められてしまうさ そうか?
そんなに完成されてないぞ
まだまだ先がある そりゃどこまで行ったってそう言えるよ。
「でかい」という結果ばかりにこだわればその内に秘める本質や流れを探究できるというものではない。
>>838
無限時間チューリングマシンなりSKIΩコンビネータなりFOSTなり、好きなのをどうぞ >>841
無限時間チューリングマシンだと
0, ω, Γ_0, ω_1^CK, ω_1^CK + Γ_0 + ω
はそれぞれどういう表記になりますか? 最近Γ_0に興味が湧いてきた。
Γ_0相当の巨大関数ってどんなのがある? >>841
本質を知らないとデカい数は作れない
>>824が良い例 >>708 もひどいが、これは明らかに釣りだろう
コンプレックス >>855でかい数を作れば本質をなんでも知れるというものではない 本当に数学板の住人?
>>867は>>855の否定になってないわけだが 否定しているわけではなくて、それがすべてではないと言いたかっただけです でかさが全てという主張の中で、計算可能関数と不可能関数はそれぞれ別に考えるのか、
計算可能関数はこのスレで扱うに値しないと考えるのか、気になる。
>>842はプログラミング言語やSKIΩコンビネータでやるならともかく、直接チューリングマシンで
やるのは不可能でないにしても難しいし分かりづらい。
概要を言えば、とりあえず後者関数を0として、そこから急増加関数でもなんでもいいから
関数と順序数を対応させていくことになる。
海外勢によってω^ω辺りまではチューリングマシンによる表現がみつかっているか? プログラミング言語による表現を直接機械が扱う表現に翻訳すればいい話ではある >>807
>>811
>>814
>>820
>>838
という流れがわからずに
>>841を書いちゃったってことですか? ω_2^CK までを表現する具体例の存在を疑っての>>838だと思ったんだ。
こちらの深読みしすぎでした。すまん チューリングマシンじゃなくてもいいから
具体例をよろしく! >>824なんかは、Σじゃなくて後者関数ならわーすごーいってなるけどビジービーバー関数
使ってるから種のわりにしょぼいってなるんだ 「でかさが全てだ」という主張に対する皮肉だと思うよ 計算不能関数全てを対角化すると言い出しそうな勢いだな。なさそうだけど 枠組みごとに大きな実数を探索でいいでしょ。
そう決まっていればラヨ関数の増加率未満の話題にラヨ関数出すような馬鹿も出ない。
今のところこのスレだけで事足りると思う。 巨大数入門者部門
巨大数初級部門
巨大数中級部門
一般部門 このスレの住人の総力で大きな数を定義しよう
という方向はないのかな? 強い=でかいというものでもない。
高階述語論理を扱えるCoCを対角化したloader.cよりもFOSTで記述可能なビジービーバー関数
の方が強い。しかし基となる言語はFOSTより高階述語論理の方が強い。
実装の仕方、計算可能などの満たさなければならない条件も関係してくる、かと >>902
サスカッチが意味不明なので、一旦なかったと考えて、リトルビッゲドンを超える巨大数を考えてどうぞ ε_0以降を表現しようと思ったがε_0^ε_0で挫折
>>819は遠い
[[[[]]]][]=ε_0+1
[[[[]]]][][]=ε_0+2
[[[[]]]][[]]=ε_0+ω
[[[[]]]][[]][[]]=ε_0+ω^2
[[[[]]]][[][]]=ε_0+ω^ω
[[[[]]]][[][]][[][]]=ε_0+ω^(ω×2)
[[[[]]]][[][][]]=ε_0+ω^ω^2
[[[[]]]][[][][][]]=ε_0+ω^ω^3
[[[[]]]][[[]]]=ε_0+ω^ω^ω
[[[[]]]][[[][]]]=ε_0+ω^ω^ω^ω
[[[[]]]][[[][][]]]=ε_0+ω^ω^ω^ω^ω
[][[[[]]]]=ε_0×2
[][][[[[]]]]=ε_0×3
[[]][[[[]]]]=ε_0×ω
[[]][[]][[[[]]]]=ε_0×ω^2
[[][]][[[[]]]]=ε_0×ω^ω
[[][][]][[[[]]]]=ε_0×ω^ω^2
[[][][][]][[[[]]]]=ε_0×ω^ω^3
[[[]]][[[[]]]]=ε_0×ω^ω^ω
[[[][]]][[[[]]]]=ε_0×ω^ω^ω^ω
[[[][][]]][[[[]]]]=ε_0×ω^ω^ω^ω^ω
[[[[]]]][[[[]]]]=ε_0^2
[[[[]]][]]=ε_0^ω
[[[[]]][]][[[[]]][]]=ε_0^(ω×2)
[[[[]]][][]]=ε_0^ω^2
[[[[]]][[]]]=ε_0^ω^ω
[[[[]]][[]]][[[[]]][[]]]=ε_0^(ω^ω×2)
[[[[]]][[]][]]=ε_0^ω^(ω+1)
[[[[]]][[]][][]]=ε_0^ω^(ω+2)
[[[[]]][][[]]]=ε_0^ω^(ω×2)
[[[[]]][][][[]]]=ε_0^ω^(ω×3)
[[[[]]][[]][[]]]=ε_0^ω^ω^2
[[[[]]][[]][[]][[]]]=ε_0^ω^ω^3
[[[[]]][[][]]]=ε_0^ω^ω^ω
[[[[]]][[][]]][[[[]]][[][]]]=ε_0^(ω^ω^ω×2)
[[[[]]][[][]][]]=ε_0^ω^(ω^ω+1)
[[[[]]][[][]][][]]=ε_0^ω^(ω^ω+2)
[[[[]]][[][]][[]]]=ε_0^ω^(ω^ω+ω)
[[[[]]][[][]][[]][[]]]=ε_0^ω^(ω^ω+ω^2)
[[[[]]][][[][]]]=ε_0^ω^(ω^ω×2)
[[[[]]][][][[][]]]=ε_0^ω^(ω^ω×3)
[[[[]]][[]][[][]]]=ε_0^ω^ω^(ω+1)
[[[[]]][[]][[]][[][]]]=ε_0^ω^ω^(ω+2)
[[[[]]][[][]][[][]]]=ε_0^ω^ω^(ω×2)
[[[[]]][[][][]]]=ε_0^ω^ω^ω^2
[[[[]]][[][][]][[][][]]]=ε_0^ω^ω^ω^3
[[[[]]][[][][][]]]=ε_0^ω^ω^ω^ω [[[[]]][[][][][]]][[[[]]][[][][][]]]=ε_0^(ω^ω^ω^ω×2)
[[[[]]][[][][][]][]]=ε_0^ω^(ω^ω^ω+1)
[[[[]]][[][][][]][][]]=ε_0^ω^(ω^ω^ω+2)
[[[[]]][[][][][]][[]]]=ε_0^ω^(ω^ω^ω+ω)
[[[[]]][[][][][]][[]][[]]]=ε_0^ω^(ω^ω^ω+ω^2)
[[[[]]][[][][][]][[][]]]=ε_0^ω^(ω^ω^ω+ω^ω)
[[[[]]][[][][][]][[][]]][[[[]]][[][][][]][[][]]]=ε_0^(ω^(ω^ω^ω+ω^ω)×2)
[[[[]]][[][][][]][[][]][]]=ε_0^ω^(ω^ω^ω+ω^ω+1)
[[[[]]][[][][][]][[][]][[]]]=ε_0^ω^(ω^ω^ω+ω^ω+ω)
[[[[]]][[][][][]][[][]][[]][[]]]=ε_0^ω^(ω^ω^ω+ω^ω+ω^2)
[[[[]]][[][][][]][][[][]]]=ε_0^ω^(ω^ω^ω+ω^ω×2)
[[[[]]][[][][][]][[]][[][]]]=ε_0^ω^(ω^ω^ω+ω^(ω+1))
[[[[]]][[][][][]][[][]][[][]]]=ε_0^ω^(ω^ω^ω+ω^(ω×2))
[[[[]]][[][][][]][[][][]]]=ε_0^ω^(ω^ω^ω+ω^ω^2)
[[[[]]][[][][][]][[][][]][[][][]]]=ε_0^ω^(ω^ω^ω+ω^ω^3)
[[[[]]][][[][][][]]]=ε_0^ω^(ω^ω^ω×2)
[[[[]]][][][[][][][]]]=ε_0^ω^(ω^ω^ω×3)
[[[[]]][[]][[][][][]]]=ε_0^ω^ω^(ω^ω+1)
[[[[]]][[]][[]][[][][][]]]=ε_0^ω^ω^(ω^ω+2)
[[[[]]][[][]][[][][][]]]=ε_0^ω^ω^(ω^ω+ω)
[[[[]]][[][]][[][]][[][][][]]]=ε_0^ω^ω^(ω^ω+ω×2)
[[[[]]][[][][]][[][][][]]]=ε_0^ω^ω^(ω^ω+ω^2)
[[[[]]][[][][]][[][][]][[][][][]]]=ε_0^ω^ω^(ω^ω+ω^3)
[[[[]]][[][][][]][[][][][]]]=ε_0^ω^ω^(ω^ω×2)
[[[[]]][[][][][][]]]=ε_0^ω^ω^ω^(ω+1)
[[[[]]][[][][][][]][[][][][][]]]=ε_0^ω^ω^ω^(ω+2)
[[[[]]][[][][][][][]]]=ε_0^ω^ω^ω^(ω×2)
[[[[]]][[][][][][][]][[][][][][][]]]=ε_0^ω^ω^ω^(ω×3)
[[[[]]][[][][][][][][]]]=ε_0^ω^ω^ω^ω^2
[[[[]]][[][][][][][][]][[][][][][][][]]]=ε_0^ω^ω^ω^ω^3
[[[[]]][[][][][][][][][]]]=ε_0^ω^ω^ω^ω^ω
[[[[]]][[][][][][][][][][][][][][][][][]]]=ε_0^ω^ω^ω^ω^ω^ω
[[[[]]][[][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][]]]=ε_0^ω^ω^ω^ω^ω^ω^ω
[[][[[]]]]=ε_0^ε_0 「ZFC+巨大基数」の公理系上で
適当な言語n文字で定義可能な最大の実数
とかっていう感じで定義出来ない? ビジービーバーとおんなじ理屈で存在しそうな気もするけど
逆に存在しないとしたらどういう理由でなんだろ。 すでにフリードマンかだれかがそういうのやってなかった? ただ微妙に計算可能関数なので計算不可能関数のビジービーバーよりは弱い
計算不可能関数化はできるけど全ての公理系を対角化してるラヨ数が発見された後だと今更感ある 計算可能ってフリードマンの超越整数のこと?
それともZFCのn文字でってやつのこと? >>924
>>923の主語は超越整数のつもりだった >>926それ言うたらloader.cも話にならん
>>927有限公理化可能であればFOSTの対角化でいける。そうでなくてもFOOTなんかの
対角化でいけると思う
その全域性をその言語で有限文字数で記述できなければいける・・・? >>927
ZFC+好きな巨大基数を思い浮かべ、ラヨ数に含まれるか考えて
好きな公理を思い浮かべて
ラヨ数に含まれるか考えて 使用するプログラム言語を1つ決める。
n文字のプログラムコードで実数を出力させるプログラムを作る。
エラーなくコンパイルできる。
実行後有限時間内で終了する。
これらを満たす条件の全てのプログラムコードの実行結果の内、
最大の正の実数の出力をMaxCode(n)とする。 チューリング完全な言語ならMaxCode(n)の値はどれも同じオーダーになるんだっけ?
どういう理屈か知らんけど。 チューリング完全だけどBBの2倍の状態を使う計算モデルを使った巨大数関数はΣ(n/2)になる。
つまりBBより増加が遅い。
入力 n に対して、なぜかΣ(n)-n^2個の無駄な状態を経ないと正しい値を出してくれない恣意的な計算モデルを使った巨大数関数はn^2になる。
でも計算モデルとしてはチューリング完全。
つまりいくらでも増加は遅くなるので >>932 は偽、かな。 後半
そういう非常識な物まで考えるならたとえばHardy階層も意味がなくねるね
ωの収束列はいくらでも大きなものもあるしいくらでも小さなものもあるんで チューリング完全の正確な定義ってしらんけど
>Σ(n)-n^2個の無駄な状態を経ないと正しい値を出してくれない恣意的な計算モデル
これはチューリング完全の定義に反しないの?
シミュレートする際の状態数は定数倍じゃなきゃいけないとかなんかないのか? Σ(n)個の状態、もしくは文字数で最大nが出力される言語を対角化するとnになる、
というようなことを言ってるのか?
だとしたらそのような言語はチューリング完全にはなり得ないということを証明すべ
ほかの言語をシミュレートするには固定された翻訳器とその言語が受けとるプログラムがあればいい いや「とか」じゃなくて、その相反する2つの主張のうちのどっちかを指してるのは分かってるんだけどどっちか分からなかったから聞いたんだけども。 Turing完全な計算モデルとはTuring機械で計算可能な任意の問題をその計算モデルで計算できれば良いのであって
計算量のオーダーがTuring機械のそれと一致する(高々、定数倍の違いしかない)ことを保証する必要はない
従って>>934が正しく>>932や>>938は間違い >>934や>>938の言ってることがよくわからない
>・・・正しい値を出してくれない恣意的な計算モデル
の正しい値って、ビジービーバー関数の値? チューリング完全だけど異常に効率が悪いマシン
の話
そんな、作れるかどうかもわからない屁理屈マシンのことなどどうでもいい とりあえず>>935-936で、同じオーダーにならないものはチューリング完全にならないというのが結論では いやいやいや
チューリング完全っていうのは入出力が同じならコストやオーダーはは有限の範囲でどうなってても関係ないでしょ?
っていう感じの>>934はクッソしょうもない揚げ足取りなだけだから>>935->>936の言う通りどうでもいい事なんだよ
いつまでこの話してんのw ε_1の定義がいまいちのみこめない。
そもそもε_0^ε_0というのもイメージが掴みずらいし。 1をスタート地点として、加算をどれだけ重ねてもたどり着けない数としてωを一旦崇める
ωをスタート地点として加算をどれだけ重ねても辿りつけない数がω×2、ω×2をスタート地点として加算をどれだけ重ねても辿りつけない数がω×3、そんなわけでそんな感じのどんな数をスタート地点にしても「加算で」辿りつけないのがω^2なのでそれも一旦崇める そんな感じで一旦ε_1は初めて見たときは当然崇めたい部類 野球でバッターがボールを打った後たまたま垂直に立ったバットくらい こんなイメージで崇めればいいかと
ε_0=ω^ω^ω…{ω個}…^ω^ω
ε_0^ω=(ω^ω^ω…{ω個}…^ω^ω)^ω
ε_0^ω^ω=(ω^ω^ω…{ω個}…^ω^ω)^ω^ω
ε_0^ω^ω^ω=(ω^ω^ω…{ω個}…^ω^ω)^ω^ω^ω
ε_0^ε_0=(ω^ω^ω…{ω個}…^ω^ω)^(ω^ω^ω…{ω個}…^ω^ω)
ε_0^ε_0^ε_0=(ω^ω^ω…{ω個}…^ω^ω)^(ω^ω^ω…{ω個}…^ω^ω)^(ω^ω^ω…{ω個}…^ω^ω)
ε_1=ε_0^ε_0^ε_0…{ω個}…^ε_0^ε_0 アッカーマン関数は、多変数の場合1階テンソル、多重リストの場合2階テンソルと見なして
多階テンソルを引数とするようにしたらいいかも ビジービーバー関数を超えないと意味が無いというものがいる一方で計算不可能レベルは
屁理屈だというものもあり、ままならない 屁理屈www
自分が理解できないものを屁理屈と言って否定するのか
負の数や虚数も否定されてたね昔 宇宙全体の知的生命体や人工知能や計算機の処理結果に最も大きい数を提示させる。
その中で最も大きな値をΠ(0)と定義する。
同じ手順でΠ(0)を超える最も大きい数を提示させ、その中で最も大きな値をΠ(1)と定義する。
同様の手順でΠ(1)を超えるものをΠ(2)、Π(2)を超えるものをΠ(3)というように値を定義していく。
Π(n)は、どれだけ大きくなるのか。 お前さん、世界でいちばん大きなものを食ったと?
そう言うお前をわしゃ食ったわい
とっぴんぱらりのぷぅ 負の数や虚数が否定された流れとは違うと思うがなぁ。
上で例えられているけど、サバンナで一番速い動物を特定するのが計算可能レベルで、
特定せずにただ単に「サバンナで1番速い動物」で済ませてしまうのが不可能レベル
ふわふわした感じがすっきりしないんじゃないか? グッドスタイン数列の収束速度をもっと遅くしたいなぁ
何かいい方法ないだろうか ビジービーバーも嫌いじゃないけどね。
そろそろΣ(5)とかΣ(6)を確定させてほしいもんだ。 なんか俺が計算不可能レベルを屁理屈言ってることになってる?
再帰が意味をなさなくなって、独自性を認められるハードルが高い感じ ビジービーバー関数とかラヨ関数とかの計算不可能関数をちゃんと定義されてると考えるか寿司屋の卵焼きと考えるかはその人自身の哲学の問題だから大変よね '9' を横に並べて大きな数を表現してる人からすれば
指数表記が反則に見えるのも仕方が無いが
枠を越えないと進歩がない googleが将棋とチェスに参入したようだ。巨大数にも加わってほしい。無理か 論理ボンブとして急膨張させる目盛り利用料の嫌がらせソフトウェアジャンルの需要は高い。 <<978
全域性を証明することができない関数に対して、十分な定義がされている
と考えるかどうかってこと 補足すると、全域性を証明することができないというのはその関数を作るために対角化した言語で証明できない
という意味であってまったくできないというわけではない >>986
この場合において、函数と写像を区別する必要性って何?
反論したい訳じゃなく、純粋に教えてほしい >>987
関数というのは、とにかく定義されていればいい。 写像というのは、定義域と値域が与えられていないと始まらない。 >>989
函数には、定義域や値域は無いんでしょうか? ん???
たとえばビジービーバー関数は普通に定義域も値域も自然数だけど
疑問の余地があるか? 自然数すべてに対してちゃんと定義されているよ
少なくともビジービーバー関数は >>991
定義されていれば定義域はそれで決まる。値域は不明でも構わない。 >>994
よくわかりません。
値域が不明なのと無いのとは別ではないんでしょうか? つまり関数には定義域は与えられていても値域が与えられていなことが考えられる、という主張だろうか?
言語の表現力の問題のような気がする >>997
>言語の表現力の問題のような気がする
kwsk このスレッドは1000を超えました。
新しいスレッドを立ててください。
life time: 321日 17時間 1分 20秒 5ちゃんねるの運営はプレミアム会員の皆さまに支えられています。
運営にご協力お願いいたします。
───────────────────
《プレミアム会員の主な特典》
★ 5ちゃんねる専用ブラウザからの広告除去
★ 5ちゃんねるの過去ログを取得
★ 書き込み規制の緩和
───────────────────
会員登録には個人情報は一切必要ありません。
月300円から匿名でご購入いただけます。
▼ プレミアム会員登録はこちら ▼
https://premium.5ch.net/
▼ 浪人ログインはこちら ▼
https://login.5ch.net/login.php レス数が1000を超えています。これ以上書き込みはできません。