巨大数探索スレッド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重リストであることを示すためです。
■ このスレッドは過去ログ倉庫に格納されています