巨大数探索スレッド7
■ このスレッドは過去ログ倉庫に格納されています
0001１３２人目の素数さん
2006/11/19(日) 23:44:01http://www.geocities.co.jp/Technopolis/9946/
前スレ、過去スレ、避難所はこのページからどうぞ。
「前の数＋1」
「1/x x→0」
「∞」
「９を延々と書き続けるプログラム」
「本日からこのスレでは、いっさいの数学的ではない話を禁止する。
私以外で検証する能力を持っている人間はいないようなので、
数学的に明確に証明できた場合以外は反論しないように。
特に今日のような低俗な煽りには徹底して放置で対応すること。」
という類の投稿は放置推奨。
0002もやしっ子
2006/11/19(日) 23:57:02巨大数研究室からのリンク張り換えました。
0003もやしっ子
2006/11/20(月) 00:54:09(現在、無限絡みの巨大数生成プロセスの議論が込み入ってるのです)
・ωって何？
「0,1,2,… したがって、ω本の電柱がある」(抜粋)
というイメージだそうで、
「全ての有限の数よりも大きい"最初"の数」＝ω とのことです。
・ωとかが絡んだ演算はどうなの？
ぶっちゃけ、定義があって大丈夫なようになってるみたいです。
・ε_0ってどんな？
とにかくωより十分でかいみたいです。タワーを使うと
ω↑↑ωという記述ができますが、これをε_0 と呼んでるみたいです。
こいつは ω^ε＝ε を満たす最初の数、とのことです。
そんで、もっと上もその上も、作れるみたいです。
とりあえず上の2種だけ噛み砕いてみました。
0004１３２人目の素数さん
2006/11/20(月) 01:42:17つくれるのかな？今日一日カントールとか考えてたけど思いつかなかった
0005１３２人目の素数さん
2006/11/20(月) 02:59:470006１３２人目の素数さん
2006/11/20(月) 03:58:240007１３２人目の素数さん
2006/11/20(月) 04:19:430008１３２人目の素数さん
2006/11/20(月) 04:31:440009１３２人目の素数さん
2006/11/20(月) 17:53:330010１３２人目の素数さん
2006/11/20(月) 21:10:190011１３２人目の素数さん
2006/11/22(水) 19:30:140012１３２人目の素数さん
2006/11/22(水) 23:43:43それとも無理なわけ？
0013１３２人目の素数さん
2006/11/23(木) 08:10:32両方巨大数を生み出せるという点では共通しているがその他の性質
が違いすぎるので比べるのは至難の技だと思う
0014１３２人目の素数さん
2006/11/24(金) 12:46:00計算可能ならばBBの方が大きいだろうし、
計算不可能ならば…計算不可能なもの同士の大小を
比べるのは、至難だろうね。
00155-682
2006/11/24(金) 23:10:37前スレを参照すればわかるかもしれませんが
ω式の巨大数(関数)は超限帰納的なので計算可能だと思います。
ただ計算可能だからBB関数のほうが大きいかどうかは
よくわからないところです。
0016１３２人目の素数さん
2006/11/24(金) 23:21:390017１３２人目の素数さん
2006/11/24(金) 23:28:290018１３２人目の素数さん
2006/11/24(金) 23:39:59f(m)はBB(n+log(m))を超えられないようなキガス。
厳密なことはおれにはわからんが。
0019１３２人目の素数さん
2006/11/25(土) 00:00:33fを計算するチューリングマシンを走らせればよい。
テープにmを書くチューリングマシンはlog(m)状態で
実現できるので、f(m)の値を得るには入力を生成する部分と
ｆを計算をする部分でn+log(m)状態あればよい。
BB(n+log(m))はn+log(m)状態で一番大きい数を出力するので
f(m)はBB(n+log(m))を超えられない。
0020１３２人目の素数さん
2006/11/25(土) 00:06:04とすると2^f(m)とBB(n+log(m))を比べないといけない？
すまん。よくわからなくなってきた。
0021１３２人目の素数さん
2006/11/25(土) 00:23:53２のべき乗を計算するチューリングマシンの状態をpとすれば
f(m)はBB(n+p+log(m))を超えられない。
スレ汚しスマソ。
0022１３２人目の素数さん
2006/11/25(土) 00:46:05ウィキペに載ってた。
0023１３２人目の素数さん
2006/11/25(土) 06:58:27厳密な定義がある概念ですよ。
0024１３２人目の素数さん
2006/11/25(土) 08:32:44テープに状態を記録できるから状態数は∞のはずじゃ？
0025１３２人目の素数さん
2006/11/25(土) 09:20:18ここで言う「状態」はマシンの内部状態のことでせう
0026１３２人目の素数さん
2006/11/25(土) 15:20:490027１３２人目の素数さん
2006/11/25(土) 15:21:300028１３２人目の素数さん
2006/11/25(土) 15:51:570029１３２人目の素数さん
2006/11/25(土) 16:10:510030１３２人目の素数さん
2006/11/26(日) 04:49:430031１３２人目の素数さん
2006/11/26(日) 10:46:120032１３２人目の素数さん
2006/11/26(日) 18:07:420033１３２人目の素数さん
2006/11/29(水) 21:30:250034１３２人目の素数さん
2006/11/29(水) 21:40:55というかチューリングマシン勉強したら習うだろ。
0035１３２人目の素数さん
2006/11/30(木) 12:48:220036１３２人目の素数さん
2006/11/30(木) 14:49:590037１３２人目の素数さん
2006/11/30(木) 15:11:230038１３２人目の素数さん
2006/12/03(日) 19:27:50厄介だな。
0039１３２人目の素数さん
2006/12/05(火) 21:26:31ｍ以上の入力を書くのにはBB＾-1(m)状態あればいいから
f(m)はBB(n+p+BB^-1(m))を越えられないって事だな。
nもpも定数だしBB^-1(m)もほとんど定数みたいなもんだから
計算可能な関数はBBからみればまさに止まって見えるつーことだな。
0040１３２人目の素数さん
2006/12/07(木) 18:06:550041１３２人目の素数さん
2006/12/07(木) 21:52:44kwsk
0042１３２人目の素数さん
2006/12/07(木) 22:01:030043１３２人目の素数さん
2006/12/07(木) 22:13:450044１３２人目の素数さん
2006/12/07(木) 23:59:19λ計算ではヒルベルト論理体系で構築できる全ての関数を計算可能
（まあ別にヒルベルトじゃなくてもいいけど）
だからBBを超えるにはλ計算の構築が不可能な論理体系に基づく関数が必要
とまで書いて気付いたけど不動点定理とか非停止問題があったな・・・
0045１３２人目の素数さん
2006/12/13(水) 21:54:14俺には無理だが。
0046１３２人目の素数さん
2006/12/17(日) 15:15:130047１３２人目の素数さん
2006/12/17(日) 15:15:530048１３２人目の素数さん
2006/12/17(日) 15:18:490049１３２人目の素数さん
2006/12/17(日) 15:33:05n 番目の素数を検索できたりするのかな？
0050１３２人目の素数さん
2006/12/17(日) 17:14:130051１３２人目の素数さん
2006/12/19(火) 22:30:37俺はBB(G+1)の方が大きいんじゃないかと思ってるんだが。
もちろんこんなもん比べようも無いがみんなの意見聞かせて。
0052１３２人目の素数さん
2006/12/20(水) 15:20:24漏れもBB(G)↑↑BB(G)＜BB(G+1)説に同意
そのレベルになるともう1増えるだけで全然違うだろうからな
0053１３２人目の素数さん
2006/12/21(木) 22:44:310054KingOfUniverse ◆667la1PjK2
2006/12/21(木) 23:32:390055KingOfUniverse ◆667la1PjK2
2006/12/21(木) 23:33:280056１３２人目の素数さん
2006/12/22(金) 00:18:13階乗なんかは滑らかな関数に延長できるんだっけ？
0057１３２人目の素数さん
2006/12/22(金) 00:55:38まぁBBに関しては無理だろう。
BB(X)とBB(X+1)に計算可能な関係が存在しないんだから。
0058１３２人目の素数さん
2006/12/22(金) 01:02:490059１３２人目の素数さん
2006/12/23(土) 08:18:44BB(x+1)<BB(y+1)-BB(y)+BB(x)
ということなので
まあ成り立つ
0060１３２人目の素数さん
2006/12/23(土) 14:09:53BB(3)-BB(2) = 2
(･д･)
0061１３２人目の素数さん
2006/12/23(土) 18:26:410062１３２人目の素数さん
2006/12/23(土) 18:42:28引数が小さなときだけの特殊な場合なのか、
もっと大きいときでも逆転が起こるのか興味あるな。
逆転が起こるとしたらどんな理由だろ？
0063１３２人目の素数さん
2006/12/23(土) 20:24:240064１３２人目の素数さん
2006/12/24(日) 08:33:550065１３２人目の素数さん
2006/12/24(日) 19:37:08=BB(x+1)<BB(x+2)-BB(x+1)+BB(x)
=2BB(x+1)<BB(x+2)+BB(x)
xが充分に大きければBB(x+1)<<<<<<<<<<<<<<<<<<<<<<<<<BB(x+2)
みたいになるからほぼ成り立つだろう
0066１３２人目の素数さん
2006/12/25(月) 21:39:06いや、58はそもそもBB(x+1)<<<<<<<<<<<<<<<<<<<<<<<<<BB(x+2)
を疑っているのだろう。
BB(x+1)-BB(x)>BB(y+1)-BB(y)
は無理かもしれないが、
BB(x+1)/BB(x)>BB(y+1)/BB(y)
くらいなら案外ありうるかも。
0067１３２人目の素数さん
2006/12/25(月) 22:53:30( ﾟдﾟ )
0068１３２人目の素数さん
2006/12/25(月) 23:09:570069１３２人目の素数さん
2006/12/25(月) 23:36:02俺定義。
0070もやしっ子
2006/12/31(日) 04:36:27前スレからHardy functionのもう少し堅いやつを拾ってきたので
性懲りもなくまた貼ります。言いだしっぺはあの人でした。懐かしい…
****
60 名前：有流才蔵 ：03/04/06 11:13
Hardy Function のHierarchyというのが面白そう。
以下、[]の0,a,λは順序数(ordinal)
H[0](x)=x+1
H[a+1](x)=H[a](x+1)
H[λ](x)=H[Λ(x)](x)
λは極限順序数、
Λ(x)はλに収束する基本列
(canonical fundamental sequence)
三行目はふぃっしゅ氏の"対角化"に似ているけれども
違うのは"Λ(x)"ってところ。
61 名前：有流才蔵 ：03/04/06 11:25
Hardy FunctionのHierarchyでいうと、
primitive recursive functionはH[ω＾ω]より小さく
multiply recursive functionはH[ω＾ω＾ω]より小さく
general recursive functionはH[ε0]より小さいそうだ。
（ε0とはω＾ω＾･･･なる順序数）
***
勝てない相手より、こっちの観戦がしたいです(他力本願)
対角化っていまだに何だか理解してないですから。ええ。
0071もやしっ子
2006/12/31(日) 04:56:34アルゴリズムや定義論みたいなのに行ってしまいましたが。まあいいか。
巨大数スレ6のDATを募集中です。
0072もやしっ子
2006/12/31(日) 05:47:37チェーンの簡易表記の解説でもしようかな。
a→b→c→dをf(a,b,c,d)と表記されたのは画期的でした。
同じことな訳ですが、初見で面食らう方もいると思うので
定義の同じところだけ噛み砕こうと思います。
f(a)=a
これはチェーンでいえば何もない状態なので、a＝aってことです。
f(a,b)=a^b
これはa→bのことですね。つまりa→b＝a^bです。
f(a,…,x,y,1)=f(a,…,x,y)
これは、a→…→x→y→1と同じです。
チェーンの最後の数が1のときはこれを落とすことができるので、
a→…→x→y→1＝a→…→x→y ということです。
f(a,…,x,1,z)=f(a,…,x)
同様に、a→…→x→1→zのことです。1より後ろは落とせるので
a→…→x→1→z＝a→…→x となります。
f(a,…,x,y,z)=f(a,…,x,f(a,…,x,y-1,z),z-1)
a→…→x→y→zのことです。チェーンの定義より、
a→…→x→y→z
＝a→…→x→(a→…→x→(y-1)→z)→(z-1) となります。
0073もやしっ子
2006/12/31(日) 05:49:09第一歩、こんな定義をしてる模様。
f((a,…,z),(1))=f(a,…,z)
ほら、なんとなく分かるかも？
続きは来年…
00745-682
2006/12/31(日) 19:24:25今Veblen関数とリスト構造を組み合わせた
巨大増加関数の案がまとまりつつあります。
（Veblen関数の変数中をリスト構造で表したものです。）
さらに一言付け加えるとすれば
リスト構造を順序数ωのように表すことができるようです。
これで順序数を大幅に拡張できます。
これを使ってナゴヤ関数をもっと詳しく
説明できるかもしれませんね。
さらにナゴヤ関数Ver２まで発展していきたいところです。
0075１３２人目の素数さん
2006/12/31(日) 19:47:16どうしても(＾ω＾)が見えてきてしまうのは俺だけか
0076１３２人目の素数さん
2007/01/01(月) 00:19:49↓このスレを見ている人はこんなスレも見ています。(ver 0.20)
0077１３２人目の素数さん
2007/01/03(水) 07:49:220078もやしっ子
2007/01/04(木) 15:43:34時に激しく。
で、73の続きですが、途中で分からない箇所があったので
(前スレで解決があったのかもしれませんが見てないです)、
わかるとこまで書きます。
>>77
ナゴヤ関数というのは現時点でも超強い関数、のはずです。
BBはすべての計算可能関数より強いので比較するまでもなく鬼強い、はずです。
(適当)
0079もやしっ子
2007/01/04(木) 15:54:36レス順ずれちゃいました。どもども。
現在前スレを読めないので、どの関数がどんなんだったか
サイトに記載した以外のものはド忘れしております。申し訳ない。
僕としては強いのが産まれれば何でもいいというか(BBは仕方ないもんなぁ)、
うまくまとまることを願ってやみません。またそれをイノセントな方々に
語り部として咀嚼するのが自分のささやかな使命、ってことでひとつ。
以前ロジシャンやプログラマの面々まで首を突っ込んで頂いた
well-defined がそもそも何だったのか、と(ヘボ)。
well-definedな関数でないと、何が起こってしまうのでしょうか。
なぜあの議論になったのかであるとか、結論などを記載していかないと
埋もれてしまうかな、と思ったり…
0080もやしっ子
2007/01/04(木) 20:16:51f((a),(n))＝a なぜ個々に括弧？ つまり、 f(a,n)とすると
a→nという式と同じになってしまうので区別してる訳です。
f((a,b),(n))＝f((a,…,(b個),…,a),(n-1))
もうチェーンでは表現できないかな。でも怖くないですよ。たぶん…
f((a,…,x,y,1),(n))＝f((a,…,x,y),(n)) 最後の1が落ちただけです。
f((a,…,x,1,z),(n))＝f((a,…,x),(n)) これも1以下が落ちただけ。
f((a,…,x,y,z),(n))＝f((a,…,x,f((a,…,x,y-1,z),(n)),z-1),(n))
ここがミソです。
手前の(a,…,x,y,z)が化ける訳です。後ろ2つのy,zが。
zは(z-1)になるだけなので怖くないです。むしろyですよ。
yは、f((a,…,x,(y-1),z),(n))といった具合に肥大化します。
0081もやしっ子
2007/01/04(木) 20:35:41さっき入れた(n)、これが(*,…,*)という「リスト」に拡張されるという。
と、進む前に一応。nも他のaやzのように、こちらが数を決めて
ぶっこんでもよい、みたいです。つまり例えば、
f((4,6,2,3,5),(10))と書いても平気で、これは一意の巨大数として決まると。
で、(*,…,*)ですが、これがどういうニュアンスなのかちとわからんです。
(n)は1次で、2次以上だと(*,…,*)と書いて、リストと呼ぶってことなのかなぁ。
この次数がどう決まるのか、とかわからんです。
ひょっとしてf_nの定義から逆読みしていけばちゃんと決まるのかなぁ。
あと、m重リストってのは、
m＝1で(*,…,*)
m＝2で((*,…,*),(*,…,*)) みたいに続くのかな。
これらリストの次数は互いに異なってもいいのかな。あはん
0082１３２人目の素数さん
2007/01/04(木) 22:10:28(*,…,*)というのは、その前に(a,…,z)とか書いていたのと同じ意味です。
つまり、(*,…,*)は具体的には(31,41,5,9,2)とか(2,71,8)とか(6)のようなものです。
(1重)リストの定義はきちんと書けば下の通りです。
{(a_1,a_2,…,a_n)|ｎは自然数; ∀i=1,…,n , a_iは自然数}
nを要素の個数、a_iを(i番目の)要素と呼ぶ。
任意のリストを表す記号として(*,…,*)を使っています。(n)は要素が1個のリストです。
同様に、m重リストは下のように再帰的に定義します。
{(L_1,L_2,…,L_n)|ｎは自然数; ∀i=1,…,n , L_iは(m-1)重リスト}
注：L_iの要素の個数は互いに異なっていても構わない
2重リストなら((*,…,*),…,(*,…,*))となります。
f((a),(n))＝aというのは、((a),(n))という2重リストにfが作用していると見ることができます。
個々に括弧がついているのは、(a)と(n)が1重リストであることを示すためです。
0083もやしっ子
2007/01/05(金) 00:50:221重リストは多分わかりました。(*,…,*)をきちんと書くとそうなるという
理解でいいのかしら。
2重リストはそうすると、定義が
{(L_1,L_2,…,L_n)|ｎは自然数; ∀i=1,…,n , L_iは1重リスト}
ですよね。
例えばn＝4なら
(L_1,L_2,L_3,L_4) となって、L_1番目からL_4番目までリストが入ってると。
でもって、この4つのリストの要素の個数は互いに異なってもよいのですね。
つまり((4),(3,8,5,7),(2,9,3),(6,5))とかやっても大丈夫。
順番にやらないと分からん脳みそなので、次は3重リストの例も書きます。
0084もやしっ子
2007/01/05(金) 01:14:11{(L_1,L_2,…,L_n)|ｎは自然数; ∀i=1,…,n , L_iは2重リスト} ということで、
例えばn＝5で書きましょう。5にしている意味は別にないです。
やはり見た目は(L_1,L_2,L_3,L_4,L_5) となる訳ですが、今度は
L_1〜L_5が、それぞれ2重リストでなければならないみたいです。
ちょっと戻っていいですか。
1重リストにおいてn＝1のとき、
(L_1) ただし L_1は自然数
2重リストにおいてn＝1のとき、
(L_1) ただし L_1は1重リスト 1重リストは(*,…,*)の形態をとる訳ですが、
この場合、1重リストの要素の個数にもn＝1を適用するかというと、そうではないと。
なぜなら、定義よりL_1の要素の個数が互いに異なってもよいから。
さて戻ります。さっき作った3重リスト
(L_1,L_2,L_3,L_4,L_5) L_1〜L_5はそれぞれ2重リスト ですが、
L_1〜L_5の要素(内包する1重リストの個数)も互いに異なってよい訳です。
ということは、
(((2,3,4),(5,6)),((7,8,9,8)),((7,6),(5),(4,3,2,3)),((4,5,6,7,8),(9,8)),((7),(6,5),(4),(3,2,3)))
とかどうでしょうか。大丈夫でしょうか。
(((7)))なんかも3重リストですか。
0085もやしっ子
2007/01/05(金) 01:41:45リストがなんなのかを踏まえたということで、f関数のルールいきましょう。
原文で「リストの列」と呼ばれる(*,…,*),…,(*,…,*)を短縮して[L]と表記してみます。
ちなみにこいつは1重リストですね。(n)も同じく1重リストですが、ちょいと区別しときます。
では2重リストのf関数のルールを。
f([L],(1))＝f([L])
f([L],(1,b))＝f([L])
f([L],(a,b))＝f([L],(f([L],(a-1,b)),b-1))
f([L],(a,…,x,y,1))＝f([L],(a,…,x,y))
f([L],(a,…,x,1,z))＝f([L],(a,…,x))
f([L],(a,…,x,y,z))＝f([L],(a,…,x,f([L],(a,…,x,y-1,z)),z-1))
f([L],(1),(n))＝f([L])
f([L],(a),(n))＝f([L],(a))
f([L],(1,b),(n))＝f([L])
f([L],(a,b),(n))＝f([L],(a,…,a),(n-1)) ただしaはb個
f([L],(a,…,x,y,1),(n))＝f([L],(a,…,x,y),(n))
f([L],(a,…,x,1,z),(n))＝f([L],(a,…,x),(n))
f([L],(a,…,x,y,z),(n))＝f([L],(a,…,x,f([L],(a,…,x,y-1,z),(n)),z-1),(n))
最後の行、原文はf([L],(a,…,x,f([L],(a,…,x,y-1,z),n),z-1)とありましたが、
nに括弧がないのは誤植でしょうか。
括弧の展開は、例によって一番ケツから定義に従って開いていけばよいです。
こうしてみると、チェーンのお約束にリストがぶりぶりくっついた物体のように
見えないこともないかな、と。
0086もやしっ子
2007/01/05(金) 02:03:48f(m重リストの列,(a,b),(n))=f(m重リストの列,((a,…,a),…,(a,…,a)),(n-1))
ただし((a,…,a),…,(a,…,a))はm重リストで、各リストの要素はb個。
[L]がm重になって、後のルールは概ね同様ってことでいいでしょうか。
そんな気がする年頃。
じゃあf_2関数いきましょう。
関数のルールが変わるだけです。びびらずに…
f_2の計算法はfとほとんど同じだが、下の式が違う。
f_2(a,b)=f((a,…,a),…,(a,…,a))
ただし((a,…,a),…,(a,…,a))はb重リストで、各リストの要素はb個。
f関数は、f(a,b)=a^bとなっていました。ここんとこを強化してる訳です。
この強化方式を悶々と拡張していった結果、こんな関数ができます。
f_n(a,b)=f_(n-1)((a,…,a),…,(a,…,a))
リストが何なのか分かれば、関数の構造自体は割とシンプルなようです。
しかしそれでいて、バード数がf_63(3,3)に到底及ばないという強力さ。
そんで思ったのは、関数がシンプルでこれだけ強いんだから、強化方式に
ふぃっしゅ系のなんかよくわからんアレをうまいこと組み込んだら
どんな感じでしょうか。有意でしょうか。
とりあえずこんな感じで…
0087１３２人目の素数さん
2007/01/05(金) 07:15:30最後の例はちゃんと3重リストになってます。
>>85
nには括弧が必要ですね。
>>86
これを書いたときは「三重以降も同様」で済むかと思ってましたが、
三重のときはもう少しきちんと書くべきだと思ったので次のレスで書いておきます。
バード数より大きくするには、実はf_2どころか3重リストを持ち出すまでもなく、
要素がたった3個の2重リストでも十分です。バード数＜f((3,3),(3,3),(3,3,2))
0088１３２人目の素数さん
2007/01/05(金) 07:17:03f(((a,…,z)),((1)))=f(a,…,z)
f(((a)),((n)))=a
f(((a,b)),((n)))=f(((a,…,a),…,(a,…,a)),((n-1))) ただしaはb個,(a,…,a)もb個
f(二重リスト,((n)))で上記に当てはまらないときは、二重リスト部分を二重リストのみの時と同様に計算。
二重リストの列を[L2]と書くと、
f([L2],((1)))=f([L2])
f([L2],((1,b)))=f([L2])
f([L2],((a,b)))=f([L2],((f([L2],((a-1,b))),b-1)))
f([L2],二重リスト)で上記に当てはまらないときは、二重リスト部分を二重リストのみの時と同様に計算。
f([L2],((1)),((n)))=f([L2])
f([L2],((a)),((n)))=f([L2],((a)))
f([L2],((1,b)),((n)))=f([L2])
f([L2],((a,b)),((n)))=f([L2],((a,…,a),…,(a,…,a)),((n-1))) ただしaはb個,(a,…,a)もb個
f([L2],二重リスト,((n)))で上記に当てはまらないときは、二重リスト部分を二重リストのみの時と同様に計算。
特に分かりにくいのは、f(((*,…,*),(m)),((n)))のようになっているときに
(m)も((n))もそのままにして(*,…,*)の部分を計算することだと思います。
例えばf(((a,…,y,z),(m)),((n)))=f(((a,…, f(((a,…,y-1,z),(m)),((n))) ,z-1),(m)),((n)))
0089もやしっ子
2007/01/05(金) 07:51:14リストを使ったふぃっしゅ系関数との比較とかやれるもんなんでしょうか。
眠れないので過去ログを読んでいました。
僕が読み飛ばしてただけで、結構皆さんチェーン拡張の可能性を
探ってたんですね。当時は喧嘩ログばかり読んでたもんで…
懲りずにVeblen関数の定義を見ましたが、やはり模様にしか見えませんでした。
0090１３２人目の素数さん
2007/01/05(金) 08:29:15ということは
f_2(a,b)には(a,…,a)（aがb個の一重リスト）がb^b-1個あるということ？
気が遠くなる........
f_n(a,b)なんて化け物ですはい、僕にはf_n(a,b)=g(n,a,b)ぐらいしか次が思い浮かびません
0091１３２人目の素数さん
2007/01/05(金) 15:44:45初代スレから今までのスレで登場した色んな巨大数の大きさを
わかりやすくランキング形式でまとめてもらえまへんか？
とリクエスト
0092もやしっ子
2007/01/05(金) 16:07:26それはなかなか難儀なことなのです。総て挙げればかなりの量です。
各々の比較はいまだ途上ですし、好みや難易度などの問題もあります。
基本的にはスレが進むにつれ強力な関数が出てくるので、研究室のログを
全部読むと把握しやすいと思います。不明な点は聞けば誰かしら答えるかと。
産まれた経緯なんかも含めて面白いんです。
とりあえず、いま上に書いてある関数は相当強いですよ。
0093１３２人目の素数さん
2007/01/05(金) 19:07:55さらにg(n,a,b)もg((a)(b)(c)(d)(e))みたいに多重リスト化していって
それを繰り返してf1_2(a,b)=f_2(a,b) f2_2(a,b)=g_2(a,b)
みたいに定義できたら.........う〜ん
0094１３２人目の素数さん
2007/01/05(金) 19:08:39まあBBには勝てないと思うけどね
0095１３２人目の素数さん
2007/01/05(金) 19:50:29f_2(a,b)=f(((…(((a,…,a),…,(a,…,a)),…,((a,…,a),…,(a,…,a)))…)))とか書いた方が良かったかも。
>>90
一重リストの個数よりは、m重リストのmが大きいことの方がずっと重要です。
後で気付いたことですが、下のような式が成り立ちますし。
f_2(a,b)=f(((…((a,b))…)),((…((2))…))) (b+1)重リスト
この式には一重リストは2つしかありません。
こういう風に、無駄なところで頑張らずに単純かつ効果的な拡張を行うことが
巨大数作りには重要だと思います。
>>94
BB(n)は「ｎ文字のプログラムで計算できる最大の数」というのと似たような意味なので、
プログラムを書けるような関数を考えている時点でBBには勝てないはず。
0096もやしっ子
2007/01/05(金) 21:13:06増やしても大差ない列というのはありましたね。初期のふぃっしゅ関数の
改良の中でも。最小限で最高の効率を得るにはどうチョイスするかですが、
こういうのはやはり再帰的帰納なんとかを知らないといかんのでしょうか。
そういえばn重帰納云々の議論は埋もれましたね。結局は絶対安心な定義が
無かったんでしょうかあれは。
あと、ログ漁ってたら
＞無限順序数は有限の数ではないが、関数を定義すれば
＞有限の数はすぐに得られる
という発言がありました。そうなのですか。
長いこと揉めてますが、とりあえずのシンプルな
「ωを導入した、有限数を得る関数」を見たいです。
どういう仕組みで動くのか興味があります。
0097１３２人目の素数さん
2007/01/05(金) 22:02:14A(x+1,y+1) = A(x,A(x+1,y))
a→...→x→y→z＝a→...→x→(a→...→x→y-1→z)→z-1
という定義だと思います。
ここには何重にも入れ子にする強さが隠れているわけで、リスト関数の定義でもこうした定義を使っています。
あとは、↑表記の持つ、並べることの強みを使っています。
そして、f_nの定義では、ふぃっしゅ数の持つ特徴のうちの一つである、
大元の関数をどんどん強くするという強みを使っています。
そう考えると、リスト関数は色々なものの長所を併せ持っていると言えるかもしれません。
>>93
リスト関数の拡張としては、f_nのnの部分を多重リストにするというのが考えられます。
たとえばf_(y,z)(多重リスト)=f_( f_(y-1,z)(多重リスト) ,z-1)(多重リスト)のようにして、
f_(多重リスト)という関数を定義するとか。
ただ、初めてリスト関数を書き込んだときにはあまり反響がなかったので、
それ以上先を考えることはしなかったけど。
0098１３２人目の素数さん
2007/01/06(土) 04:11:21ただ、ω^ω^nよりも先には進めませんでした。
(n)=(n,1)＜(1,2)=ω
右側に1を付け足しても同じものとします。
ただし、fの計算と違って(a,1,b)≠(a)です。途中に1があっても消せません。
また、右側の数字が大きいリストの方が大きいとします。
すると、(1,2)はどんな自然数nよりも大きいのでωと同一視できます。
(n+1,2)=ω+n
一番左の数字にnを足すのは、順序数にnを足すのと同じとみなせます。
すると、以下のような式が成り立ちます。
(1,3)=ω+ω=ω*2 (1,n+1)=ω*n (1,1,2)=ω*ω=ω^2 (1,1,3)=ω^2+ω^2=ω^2*2
(1,1,1,2)=ω^2*ω=ω^3 (1,1,1,1,2)=ω^4
多重リストの大小関係としては、右側のリストが大きい多重リストの方が大きいとします。
(1,1,1,1,2)=((1,1,1,1,2),(1))＜((1),(2))=ω^ω ((1),(3))=ω^ω+ω^ω=ω^ω*2
((1),(1,2))=ω^ω*ω=ω^(ω+1) ((1),(1,1,2))=ω^(ω+1)*ω=ω^(ω+2)
((1),(1),(2))=ω^(ω+ω)=ω^(ω*2) ((1),(1),(1),(2))=ω^(ω+ω)=ω^(ω*3)
(((1)),((2)))=ω^(ω*ω)=ω^ω^2 (((1)),((1),(2)))=ω^ω^2*ω^ω=ω^(ω^2+ω)
(((1)),((1),(1),(2)))=ω^(ω^2+ω*2) (((1)),((1)),((2)))=ω^(ω^2+ω*ω)=ω^(ω^2*2)
((((1))),(((2))))=ω^(ω^2*ω)=ω^ω^3 (((((1)))),((((2)))))=ω^ω^4
((…(1)…),(…(2)…))=ω^ω^n ただし(n+1)重リスト
0099１３２人目の素数さん
2007/01/06(土) 04:25:45最終的にどんなリストよりも「小さい」自然数に変換していると考えられます。
fは順序数(の一部)から自然数への関数ともみなせます。
もしもε_0やη_0を表すことができるリスト構造を作ることができたなら、
リスト関数をもっと強力なものに拡張できるのではないかと思います。
順序数の話はよく分からなくて読み飛ばしていたので、似たような構想は既にあるのかもしれませんが。
0100１３２人目の素数さん
2007/01/06(土) 05:35:39＞順序数を使う代わりに2変数にしたりするのが通常のやり方といえます。
＞（結果n変数になったりリストが入れ子になったりして行き詰まる）
という書き込みが見つかった。これって私が今陥っている状況そのものだろうか。
ちなみに、多重リストのm重リストを(m,2)重リストと表し、
多重リストの多重リストのm重リストを(m,3)重リストと表し、
…として（多重リスト）重リストなるものを定義したら、
ω＾ω＾…＾ω＾ωはリストとして表せました。でも、ε_0には到達できませんでした。
（どうしても（（…（（多重リスト）重リスト）…重リスト）重リスト）重リストから先に進めない）
0101もやしっ子
2007/01/06(土) 05:49:20僕はこれだけで十分満足です。
試しに咀嚼してもいいですか。
まず、ここでの1重リスト(n)は、どう頑張ろうが有限の自然数です。
(最終的に ある関数f(n)がこの形から有限数を出力する必要があるため？
出口が無限では意味がなかろう、と勝手に理解。)
定義よりイコールなので(n,1)も有限の自然数です。
関数とリストがごっちゃになりそうですが、よーするにリストとは
記法の問題で、ルールに沿って展開していけばいつかは一意に定まった
数になりますから、つまりは数なんです。そうしましょう。
さて、前とは展開のルールが若干異なるようなので気を付けつつ…
新ルールは、右端の数(またはリスト)の大小を優先的に評価するからなのか、
途中の1は飛ばせない仕様になっているようです。
「右端の数(リスト)が大きいものが、大小関係で上に立つ」ルールにより、
(n,1)＜(1,2) という不等式が書けます。
これはつまり、
[任意の大きさの自然数]＜(1,2) ということです。
ここで(1,2)の1は飛ばせません。最もコンパクトな形になってます。
そして、(1,2)とは(n,1)より大きいリストのうち最小のものです。
繰り返しますが、リストとは1つの数です。すると…
(1,2)とは「任意の有限の数よりも大きい最初の数」ということになります。
そして「任意の有限の数よりも大きい最初の数」とは、ズバリωのことです。
だから(1,2)=ω なんでございます。いかがでしょうか。
■ このスレッドは過去ログ倉庫に格納されています