2ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

巨大数探索スレッド7

1 :132人目の素数さん:2006/11/19(日) 23:44:01
巨大数研究室
http://www.geocities.co.jp/Technopolis/9946/

前スレ、過去スレ、避難所はこのページからどうぞ。

「前の数+1」
「1/x x→0」
「∞」
「9を延々と書き続けるプログラム」
「本日からこのスレでは、いっさいの数学的ではない話を禁止する。
私以外で検証する能力を持っている人間はいないようなので、
数学的に明確に証明できた場合以外は反論しないように。
特に今日のような低俗な煽りには徹底して放置で対応すること。」

という類の投稿は放置推奨。

2 :もやしっ子:2006/11/19(日) 23:57:02
ありがとうございます。
巨大数研究室からのリンク張り換えました。

3 :もやしっ子:2006/11/20(月) 00:54:09
いきなり無限の話ですが、「数の本」を片手に少々。
(現在、無限絡みの巨大数生成プロセスの議論が込み入ってるのです)

・ωって何?
「0,1,2,… したがって、ω本の電柱がある」(抜粋)
というイメージだそうで、
「全ての有限の数よりも大きい"最初"の数」=ω とのことです。

・ωとかが絡んだ演算はどうなの?
ぶっちゃけ、定義があって大丈夫なようになってるみたいです。

・ε_0ってどんな?
とにかくωより十分でかいみたいです。タワーを使うと
ω↑↑ωという記述ができますが、これをε_0 と呼んでるみたいです。
こいつは ω^ε=ε を満たす最初の数、とのことです。

そんで、もっと上もその上も、作れるみたいです。
とりあえず上の2種だけ噛み砕いてみました。

4 :132人目の素数さん:2006/11/20(月) 01:42:17
巨大数とは逆に小さい数の話だけど冪集合の濃度がN_0になるような自然数の部分集合って
つくれるのかな?今日一日カントールとか考えてたけど思いつかなかった

5 :132人目の素数さん:2006/11/20(月) 02:59:47
アレフ_0なら無理

6 :132人目の素数さん:2006/11/20(月) 03:58:24
アレフゼロが最小だというのは証明されていた気がする。どんな証明だったっけ?

7 :132人目の素数さん:2006/11/20(月) 04:19:43
選択公理を使用

8 :132人目の素数さん:2006/11/20(月) 04:31:44
無限集合は可算無限集合を部分集合として持つからアレフゼロ以上になるわけか

9 :132人目の素数さん:2006/11/20(月) 17:53:33
このスレは新しい巨大基数の公理でも見つけるスレなのかね

10 :132人目の素数さん:2006/11/20(月) 21:10:19
じゃなく高速に有限巨大数を作る方法を考えるスレかな?そのために順序数を利用しようという流れかと。

11 :132人目の素数さん:2006/11/22(水) 19:30:14
ビジービーバーはどうなった?

12 :132人目の素数さん:2006/11/22(水) 23:43:43
ωとか使えばビジービーバーを抜ける可能性があるわけ?
それとも無理なわけ?


13 :132人目の素数さん:2006/11/23(木) 08:10:32
>>12
両方巨大数を生み出せるという点では共通しているがその他の性質
が違いすぎるので比べるのは至難の技だと思う

14 :132人目の素数さん:2006/11/24(金) 12:46:00
ωを使った巨大数は、計算可能なの?

計算可能ならばBBの方が大きいだろうし、
計算不可能ならば…計算不可能なもの同士の大小を
比べるのは、至難だろうね。

15 :5-682:2006/11/24(金) 23:10:37
>>14
前スレを参照すればわかるかもしれませんが
ω式の巨大数(関数)は超限帰納的なので計算可能だと思います。
ただ計算可能だからBB関数のほうが大きいかどうかは
よくわからないところです。


16 :132人目の素数さん:2006/11/24(金) 23:21:39
BBはあらゆる計算可能な関数より大きいことになっている。


17 :132人目の素数さん:2006/11/24(金) 23:28:29
証明があるってことか?

18 :132人目の素数さん:2006/11/24(金) 23:39:59
ある関数fがn状態のチューリングマシンで計算可能で、入力がmなら
f(m)はBB(n+log(m))を超えられないようなキガス。
厳密なことはおれにはわからんが。



19 :132人目の素数さん:2006/11/25(土) 00:00:33
f(m)を計算するにはテープにmが書かれた状態で
fを計算するチューリングマシンを走らせればよい。
テープにmを書くチューリングマシンはlog(m)状態で
実現できるので、f(m)の値を得るには入力を生成する部分と
fを計算をする部分でn+log(m)状態あればよい。
BB(n+log(m))はn+log(m)状態で一番大きい数を出力するので
f(m)はBB(n+log(m))を超えられない。



20 :132人目の素数さん:2006/11/25(土) 00:06:04
と思ったけどBBの定義はテープに1を何個かけるかだっけ?
とすると2^f(m)とBB(n+log(m))を比べないといけない?
すまん。よくわからなくなってきた。


21 :132人目の素数さん:2006/11/25(土) 00:23:53
とおもったけど2のべき乗を計算する処理も入れてやれば良いのか?
2のべき乗を計算するチューリングマシンの状態をpとすれば
f(m)はBB(n+p+log(m))を超えられない。
スレ汚しスマソ。


22 :132人目の素数さん:2006/11/25(土) 00:46:05
BBの逆概念風なものに、コルモゴロフ複雑性ってのがあるんやね。
ウィキペに載ってた。

23 :132人目の素数さん:2006/11/25(土) 06:58:27
「計算可能」っていうのは単に「計算出来そう」という意味じゃなくて
厳密な定義がある概念ですよ。

24 :132人目の素数さん:2006/11/25(土) 08:32:44
オートマトンには状態数があるけどチューリングマシンの状態数って?
テープに状態を記録できるから状態数は∞のはずじゃ?

25 :132人目の素数さん:2006/11/25(土) 09:20:18
>>24
ここで言う「状態」はマシンの内部状態のことでせう

26 :132人目の素数さん:2006/11/25(土) 15:20:49
オートマトンには状態遷移表みたいなのが内蔵されるんよー。

27 :132人目の素数さん:2006/11/25(土) 15:21:30
まちがえた、チューリングマシンだった。

28 :132人目の素数さん:2006/11/25(土) 15:51:57
TMの状態数は計算可能性には関係ないんじゃなかったっけ?

29 :132人目の素数さん:2006/11/25(土) 16:10:51
1状態でも停止できないものが作れるからな。

30 :132人目の素数さん:2006/11/26(日) 04:49:43
状態数と計算可能性に関係がないのなら上限値にBB(n+log(m))のようにnが含まれるのは変な気がする

31 :132人目の素数さん:2006/11/26(日) 10:46:12
計算可能性と上限値に関連はないと思うけど。

32 :132人目の素数さん:2006/11/26(日) 18:07:42
状態数が多いほど計算できる関数は増える。


33 :132人目の素数さん:2006/11/29(水) 21:30:25
チューリングマシンを使わずに計算不能な関数は定義できるか?


34 :132人目の素数さん:2006/11/29(水) 21:40:55
出来る。再帰的でない函数のことなんだから。

というかチューリングマシン勉強したら習うだろ。

35 :132人目の素数さん:2006/11/30(木) 12:48:22
結局現時点で一番大きな数はなんなの?

36 :132人目の素数さん:2006/11/30(木) 14:49:59
範囲を有限にしないとこのスレの意味無いじゃん。

37 :132人目の素数さん:2006/11/30(木) 15:11:23
数自体は自然数しか扱っていないよ

38 :132人目の素数さん:2006/12/03(日) 19:27:50
なんつーかBBがある限り計算可能な関数の議論は白けてしまうっつーか。
厄介だな。

39 :132人目の素数さん:2006/12/05(火) 21:26:31
>>18-21の理屈で行くとfが単調増加関数だとするとテープに
m以上の入力を書くのにはBB^-1(m)状態あればいいから
f(m)はBB(n+p+BB^-1(m))を越えられないって事だな。
nもpも定数だしBB^-1(m)もほとんど定数みたいなもんだから
計算可能な関数はBBからみればまさに止まって見えるつーことだな。


40 :132人目の素数さん:2006/12/07(木) 18:06:55
ヒルベルト論理体系を超えた関数を作ろうぜ

41 :132人目の素数さん:2006/12/07(木) 21:52:44
>>40
kwsk

42 :132人目の素数さん:2006/12/07(木) 22:01:03
kwskというか意味がわからん

43 :132人目の素数さん:2006/12/07(木) 22:13:45
>>40がなんか面白そうなアイディアを持ってそうなのでkwsk聞きたかったのだが。


44 :132人目の素数さん:2006/12/07(木) 23:59:19
チューリングマシンで計算可能な関数はλ計算でも計算可能。逆も真
λ計算ではヒルベルト論理体系で構築できる全ての関数を計算可能
(まあ別にヒルベルトじゃなくてもいいけど)
だからBBを超えるにはλ計算の構築が不可能な論理体系に基づく関数が必要

とまで書いて気付いたけど不動点定理とか非停止問題があったな・・・

45 :132人目の素数さん:2006/12/13(水) 21:54:14
>>39の要領でフィッシュ数がBBのいくつ以下とか出せそうな気がする。
俺には無理だが。

46 :132人目の素数さん:2006/12/17(日) 15:15:13
ωって結局なによ?有限?無限?

47 :132人目の素数さん:2006/12/17(日) 15:15:53
sage忘れスマソ

48 :132人目の素数さん:2006/12/17(日) 15:18:49
チューリングマシンはバンダイで売っていますか?

49 :132人目の素数さん:2006/12/17(日) 15:33:05
量子コンピュータができたら高速で任意の
n 番目の素数を検索できたりするのかな?

50 :132人目の素数さん:2006/12/17(日) 17:14:13
そばで机を指でたたくと値が変わる

51 :132人目の素数さん:2006/12/19(火) 22:30:37
Gをグラハム数としてBB(G)↑↑BB(G)とBB(G+1)ってどっちが大きいと思う?
俺はBB(G+1)の方が大きいんじゃないかと思ってるんだが。
もちろんこんなもん比べようも無いがみんなの意見聞かせて。

52 :132人目の素数さん:2006/12/20(水) 15:20:24
>>51
漏れもBB(G)↑↑BB(G)<BB(G+1)説に同意
そのレベルになるともう1増えるだけで全然違うだろうからな

53 :132人目の素数さん:2006/12/21(木) 22:44:31
BBって滑らかなのかぁ。などと言ってみるテスト。


54 :KingOfUniverse ◆667la1PjK2 :2006/12/21(木) 23:32:39
talk:>>53 滑らかの定義から分かるように、必ず滑らかでない。

55 :KingOfUniverse ◆667la1PjK2 :2006/12/21(木) 23:33:28
talk:>>53 それとも、滑らかである関数に延長できるのか?

56 :132人目の素数さん:2006/12/22(金) 00:18:13
kingこのスレみてたのか。
階乗なんかは滑らかな関数に延長できるんだっけ?


57 :132人目の素数さん:2006/12/22(金) 00:55:38
ガンマ関数のことかー。
まぁBBに関しては無理だろう。
BB(X)とBB(X+1)に計算可能な関係が存在しないんだから。

58 :132人目の素数さん:2006/12/22(金) 01:02:49
x<yならばBB(x+1)-BB(x)<BB(y+1)-BB(y)といえるか?


59 :132人目の素数さん:2006/12/23(土) 08:18:44
>>58
BB(x+1)<BB(y+1)-BB(y)+BB(x)
ということなので
まあ成り立つ

60 :132人目の素数さん:2006/12/23(土) 14:09:53
BB(2)-BB(1) = 3
BB(3)-BB(2) = 2

(・д・)


61 :132人目の素数さん:2006/12/23(土) 18:26:41
w

62 :132人目の素数さん:2006/12/23(土) 18:42:28
>>60
引数が小さなときだけの特殊な場合なのか、
もっと大きいときでも逆転が起こるのか興味あるな。
逆転が起こるとしたらどんな理由だろ?


63 :132人目の素数さん:2006/12/23(土) 20:24:24
n次元空間の構造みたいな話になっていきそうでアレだなぁ。

64 :132人目の素数さん:2006/12/24(日) 08:33:55
>>59がすでに証明できていれば良いのだが


65 :132人目の素数さん:2006/12/24(日) 19:37:08
BB(x+1)<BB(y+1)-BB(y)+BB(x)
=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)
みたいになるからほぼ成り立つだろう


66 :132人目の素数さん:2006/12/25(月) 21:39:06
>>65
いや、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)
くらいなら案外ありうるかも。

67 :132人目の素数さん:2006/12/25(月) 22:53:30
(2^3)/(2^2)=(2^2)/(2^1)

( ゚д゚ )

68 :132人目の素数さん:2006/12/25(月) 23:09:57
巨大数の定義は?

69 :132人目の素数さん:2006/12/25(月) 23:36:02
具体的に想像もできないくらい巨大な数。
俺定義。

70 :もやしっ子:2006/12/31(日) 04:36:27
どうも。BBすげえ強そうですね。どうでしょう、ひとまず無視しては(笑)。
前スレから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とはω^ω^・・・なる順序数)

***

勝てない相手より、こっちの観戦がしたいです(他力本願)
対角化っていまだに何だか理解してないですから。ええ。

71 :もやしっ子:2006/12/31(日) 04:56:34
あー前スレで順序数の議論もやってたみたいですね。
アルゴリズムや定義論みたいなのに行ってしまいましたが。まあいいか。
巨大数スレ6のDATを募集中です。

72 :もやしっ子: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) となります。

73 :もやしっ子:2006/12/31(日) 05:49:09
まずはこれを踏まえて、いざリスト関数の解読!(どうだか…)
第一歩、こんな定義をしてる模様。
f((a,…,z),(1))=f(a,…,z)

ほら、なんとなく分かるかも?
続きは来年…

74 :5-682:2006/12/31(日) 19:24:25
大晦日に久しぶりレス。

今Veblen関数とリスト構造を組み合わせた
巨大増加関数の案がまとまりつつあります。
(Veblen関数の変数中をリスト構造で表したものです。)
さらに一言付け加えるとすれば
リスト構造を順序数ωのように表すことができるようです。
これで順序数を大幅に拡張できます。
これを使ってナゴヤ関数をもっと詳しく
説明できるかもしれませんね。
さらにナゴヤ関数Ver2まで発展していきたいところです。

75 :132人目の素数さん:2006/12/31(日) 19:47:16
>>70
どうしても(^ω^)が見えてきてしまうのは俺だけか

76 :132人目の素数さん:2007/01/01(月) 00:19:49
↓うるせーんだよ
↓このスレを見ている人はこんなスレも見ています。(ver 0.20)

77 :132人目の素数さん:2007/01/03(水) 07:49:22
難し杉で議論に入れないナゴヤ関数ってなに?BBと比べるとどうなの?

78 :もやしっ子:2007/01/04(木) 15:43:34
あけましておめでとうございます。今年もちんたらやりましょう。
時に激しく。

で、73の続きですが、途中で分からない箇所があったので
(前スレで解決があったのかもしれませんが見てないです)、
わかるとこまで書きます。

>>77
ナゴヤ関数というのは現時点でも超強い関数、のはずです。
BBはすべての計算可能関数より強いので比較するまでもなく鬼強い、はずです。
(適当)

79 :もやしっ子:2007/01/04(木) 15:54:36
>>74
レス順ずれちゃいました。どもども。
現在前スレを読めないので、どの関数がどんなんだったか
サイトに記載した以外のものはド忘れしております。申し訳ない。
僕としては強いのが産まれれば何でもいいというか(BBは仕方ないもんなぁ)、
うまくまとまることを願ってやみません。またそれをイノセントな方々に
語り部として咀嚼するのが自分のささやかな使命、ってことでひとつ。

以前ロジシャンやプログラマの面々まで首を突っ込んで頂いた
well-defined がそもそも何だったのか、と(ヘボ)。
well-definedな関数でないと、何が起こってしまうのでしょうか。
なぜあの議論になったのかであるとか、結論などを記載していかないと
埋もれてしまうかな、と思ったり…

80 :もやしっ子:2007/01/04(木) 20:16:51
さて、リスト関数の続き。

f((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))といった具合に肥大化します。

81 :もやしっ子: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で((*,…,*),(*,…,*)) みたいに続くのかな。
これらリストの次数は互いに異なってもいいのかな。あはん

82 :132人目の素数さん:2007/01/04(木) 22:10:28
>>81
(*,…,*)というのは、その前に(a,…,z)とか書いていたのと同じ意味です。
つまり、(*,…,*)は具体的には(31,41,5,9,2)とか(2,71,8)とか(6)のようなものです。

(1重)リストの定義はきちんと書けば下の通りです。
 {(a_1,a_2,…,a_n)|nは自然数; ∀i=1,…,n , a_iは自然数}
 nを要素の個数、a_iを(i番目の)要素と呼ぶ。
任意のリストを表す記号として(*,…,*)を使っています。(n)は要素が1個のリストです。

同様に、m重リストは下のように再帰的に定義します。
 {(L_1,L_2,…,L_n)|nは自然数; ∀i=1,…,n , L_iは(m-1)重リスト}
 注:L_iの要素の個数は互いに異なっていても構わない
2重リストなら((*,…,*),…,(*,…,*))となります。

f((a),(n))=aというのは、((a),(n))という2重リストにfが作用していると見ることができます。
個々に括弧がついているのは、(a)と(n)が1重リストであることを示すためです。

83 :もやしっ子:2007/01/05(金) 00:50:22
>>82
1重リストは多分わかりました。(*,…,*)をきちんと書くとそうなるという
理解でいいのかしら。

2重リストはそうすると、定義が
{(L_1,L_2,…,L_n)|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重リストの例も書きます。

84 :もやしっ子:2007/01/05(金) 01:14:11
3重リストの定義は、
{(L_1,L_2,…,L_n)|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重リストですか。

85 :もやしっ子:2007/01/05(金) 01:41:45
ということでm重リストもそんな感じでしょう(適当)。
リストがなんなのかを踏まえたということで、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に括弧がないのは誤植でしょうか。

括弧の展開は、例によって一番ケツから定義に従って開いていけばよいです。
こうしてみると、チェーンのお約束にリストがぶりぶりくっついた物体のように
見えないこともないかな、と。

86 :もやしっ子:2007/01/05(金) 02:03:48
さてm重リストのf関数は、こうです。

f(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)に到底及ばないという強力さ。

そんで思ったのは、関数がシンプルでこれだけ強いんだから、強化方式に
ふぃっしゅ系のなんかよくわからんアレをうまいこと組み込んだら
どんな感じでしょうか。有意でしょうか。

とりあえずこんな感じで…

87 :132人目の素数さん:2007/01/05(金) 07:15:30
>>84
最後の例はちゃんと3重リストになってます。
>>85
nには括弧が必要ですね。
>>86
これを書いたときは「三重以降も同様」で済むかと思ってましたが、
三重のときはもう少しきちんと書くべきだと思ったので次のレスで書いておきます。

バード数より大きくするには、実はf_2どころか3重リストを持ち出すまでもなく、
要素がたった3個の2重リストでも十分です。バード数<f((3,3),(3,3),(3,3,2))

88 :132人目の素数さん:2007/01/05(金) 07:17:03
三重リストの計算法
f(((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)))

89 :もやしっ子:2007/01/05(金) 07:51:14
レスどうもです。改めて咀嚼しようと思います。サイト更新なども。
リストを使ったふぃっしゅ系関数との比較とかやれるもんなんでしょうか。

眠れないので過去ログを読んでいました。
僕が読み飛ばしてただけで、結構皆さんチェーン拡張の可能性を
探ってたんですね。当時は喧嘩ログばかり読んでたもんで…

懲りずにVeblen関数の定義を見ましたが、やはり模様にしか見えませんでした。

90 :132人目の素数さん:2007/01/05(金) 08:29:15
>>86
ということは
f_2(a,b)には(a,…,a)(aがb個の一重リスト)がb^b-1個あるということ?
気が遠くなる........
f_n(a,b)なんて化け物ですはい、僕にはf_n(a,b)=g(n,a,b)ぐらいしか次が思い浮かびません



91 :132人目の素数さん:2007/01/05(金) 15:44:45
最近このスレを知った初心者ですが、
初代スレから今までのスレで登場した色んな巨大数の大きさを
わかりやすくランキング形式でまとめてもらえまへんか?
とリクエスト


92 :もやしっ子:2007/01/05(金) 16:07:26
>>91
それはなかなか難儀なことなのです。総て挙げればかなりの量です。
各々の比較はいまだ途上ですし、好みや難易度などの問題もあります。
基本的にはスレが進むにつれ強力な関数が出てくるので、研究室のログを
全部読むと把握しやすいと思います。不明な点は聞けば誰かしら答えるかと。
産まれた経緯なんかも含めて面白いんです。

とりあえず、いま上に書いてある関数は相当強いですよ。

93 :132人目の素数さん:2007/01/05(金) 19:07:55
>>90の続き
さらに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)
みたいに定義できたら.........う〜ん

94 :132人目の素数さん:2007/01/05(金) 19:08:39
>>93の続き
まあBBには勝てないと思うけどね

95 :132人目の素数さん:2007/01/05(金) 19:50:29
f_2(a,b)=f((a,…,a),…,(a,…,a))だと二重リストのように見えますね。
f_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)は「n文字のプログラムで計算できる最大の数」というのと似たような意味なので、
プログラムを書けるような関数を考えている時点でBBには勝てないはず。

96 :もやしっ子:2007/01/05(金) 21:13:06
>>95
増やしても大差ない列というのはありましたね。初期のふぃっしゅ関数の
改良の中でも。最小限で最高の効率を得るにはどうチョイスするかですが、
こういうのはやはり再帰的帰納なんとかを知らないといかんのでしょうか。
そういえばn重帰納云々の議論は埋もれましたね。結局は絶対安心な定義が
無かったんでしょうかあれは。

あと、ログ漁ってたら
>無限順序数は有限の数ではないが、関数を定義すれば
>有限の数はすぐに得られる
という発言がありました。そうなのですか。
長いこと揉めてますが、とりあえずのシンプルな
「ωを導入した、有限数を得る関数」を見たいです。
どういう仕組みで動くのか興味があります。

97 :132人目の素数さん:2007/01/05(金) 22:02:14
アッカーマン関数やチェーン表記が持っている最大の強みは、
A(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_(多重リスト)という関数を定義するとか。
ただ、初めてリスト関数を書き込んだときにはあまり反響がなかったので、
それ以上先を考えることはしなかったけど。

98 :132人目の素数さん: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)重リスト

99 :132人目の素数さん:2007/01/06(土) 04:25:45
リスト関数fは、与えられた多重リストを上に述べた意味でより「小さい」多重リストに変換し、
最終的にどんなリストよりも「小さい」自然数に変換していると考えられます。
fは順序数(の一部)から自然数への関数ともみなせます。
もしもε_0やη_0を表すことができるリスト構造を作ることができたなら、
リスト関数をもっと強力なものに拡張できるのではないかと思います。

順序数の話はよく分からなくて読み飛ばしていたので、似たような構想は既にあるのかもしれませんが。

100 :132人目の素数さん:2007/01/06(土) 05:35:39
過去ログを読んでたら、
>順序数を使う代わりに2変数にしたりするのが通常のやり方といえます。
>(結果n変数になったりリストが入れ子になったりして行き詰まる)
という書き込みが見つかった。これって私が今陥っている状況そのものだろうか。

ちなみに、多重リストのm重リストを(m,2)重リストと表し、
多重リストの多重リストのm重リストを(m,3)重リストと表し、
…として(多重リスト)重リストなるものを定義したら、
ω^ω^…^ω^ωはリストとして表せました。でも、ε_0には到達できませんでした。
(どうしても((…((多重リスト)重リスト)…重リスト)重リスト)重リストから先に進めない)

101 :もやしっ子:2007/01/06(土) 05:49:20
(n)=(n,1)<(1,2)=ω  まさに目から鱗です。こういう作り方があるとは…
僕はこれだけで十分満足です。

試しに咀嚼してもいいですか。
まず、ここでの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)=ω なんでございます。いかがでしょうか。

102 :もやしっ子:2007/01/06(土) 06:19:27
さて、関数で無限から有限に落とすとのことですが。やってみます。

f{4}(1,2)というものを考えてみました。
この関数f{m}(*)は、(*)がωを用いた式で表せる超限順序数だったとして、
ωをnに置き換えた式に自然数mを代入した値を出力するというものです。
(ヘボは承知なので、あまり突っ込まないように…)

したらばf{4}(1,2)は、(1,2)=ωなのでこれをnに引きずり落として、
nに4を代入して、そのまんまですが4が出力されます。

例2。
f{10}((1),(1,2)) 

((1),(1,2))=ω^(ω+1)なのでn^(n+1)に引き下げてnに10を代入。
よって出力は10^11=100000000000 みたいな。

定義がやばい上に弱いですが、個人的に無限を組み込んだ関数から
有限の出力を得たので勝手に納得。
あまりにクルクルパーであればご指導ください。

103 :132人目の素数さん:2007/01/06(土) 08:04:38
>>101
途中の1を飛ばすと、多重リスト自体は「小さく」なります。
リスト関数では、多重リストをどんどん小さくしていく必要があるので、
途中の1を飛ばすことが許されるわけです。
一方、多重リストを順序数と対応させるときは、リストの「大きさ」が変わるような変化は許されません。
末尾の1が自由に付け外しできるのは、有限小数の末尾に無限個の0が省略されているのと同様に、
「多重リストの末尾には無限に1が並んでいるが、省略されている」と考えているからです。

再帰的に関数を定義するときは、ある引数がどんどん小さくならないときちんと定義されません。
リスト関数の場合は、リストそのものが小さくなっていく「引数」と考えられます。
「小さくなる」という考え方ができるということは「順序関係を持っている」ということであり、
順序数と対応付けられるのは自然なことなのかもしれません。

104 :132人目の素数さん:2007/01/06(土) 08:10:01
リスト関数をもう少し単純に定義してみます。

m重リストを表す括弧には_mをつけて表記する。(ただし_1は省略)
また、あるリストの唯一の要素となっている多重リストの括弧は省略する。
(例えば、((a,b))は(a,b)_2、((a),(b))は((a),(b))_2、(((n)))は(n)_3のように表記)

f(a)_m=a
f(a,b)_m=a^b

多重リストの要素に自然数の1または1のみを要素とする多重リストがあるとき、そこから右側の要素をすべて取り去る。

リストの右側のカンマから順番に見ていき、以下の表記に当てはまる最初のカンマに対し変換を適用する。
f(…y,z…)_m=f(… f(…y-1,z…)_m ,z-1…)_m
f(…(y),(z)…)_m=f(…(y,…,y),(z-1)…)_m ただしyはy個
f(…(y)_n,(z)_n…)_m=f(…((y)_(n-1),…,(y)_(n-1))_n,(z-1)_n…)_m ただし(y)_(n-1)はy個

f_n(a)_m=f_(n-1)((a)_(a-1),…,(a)_(a-1))_a ただし(a)_(a-1)はa個

定義は以上です。以前のリスト関数と定義が一部変わっているので
二重リスト以上に対しては異なる値となりますが、
f(a,b,…,y,z)=a→b→…→y→zなことには変わりはありません。
これだと、>>100で述べた(多重リスト)重リストにも拡張しやすいと思います。

105 :もやしっ子:2007/01/06(土) 09:06:39
なんか僕が個人教授を受けているな雰囲気に…いや楽しいですが。

なるほど、1を飛ばす根拠はその辺りにあったのですね。ははあ。
しかし順序数をガチで学ぼうとするとZFCの公理系とかで即コケます。
全順序とか半順序とか、関係についてすら定義ありますもんね。うう…

>>104ではかなりスマートになりましたね。かつ明解。
軽く咀嚼を混ぜて改訂版を研究室に載せたいですね。

106 :132人目の素数さん:2007/01/06(土) 20:57:43
なんか自分の思いつくままに色々なことを書き連ねている気がします。

それはともかく、リストに対する別の見方について。
一重リストは、自然数から自然数への関数と対応付けることができます。
つまり、(a_1,a_2,…,a_n)というリストは、1→a_1, 2→a_2, …, n→a_n, n+1→1, … という関数に対応付けられます。
もしも多重リストの(a_1,a_2,…,a_n)要素というのを、
n重リストのa_n番目の要素である、(n-1)重リストのa_(n-1)番目の要素である、…、
2重リストのa_2番目の要素である、1重リストのa_1番目の要素と定義すれば、
多重リストは一重リストから自然数への関数と対応付けられます。
同様に考えれば、多重リストから自然数への関数と対応付けられるリスト構造を考えることができます。
それは、>>100で少しだけ書いた(一重リスト)重リストと同じものです。
同様にして(多重リスト)重リスト、((一重リスト)重リスト)重リスト、…というリスト構造が作れます。

そして、リストと順序数の対応を考えて見ます。
ωより小さい任意の順序数は、自然数と対応付けできます。
ω^ωより小さい任意の順序数は、一重リストと対応付けできます。
ω^ω^ωより小さい任意の順序数は、多重リストと対応付けできます。
そして、ω^ω^ω^ωより小さい任意の順序数は、(一重リスト)重リストと対応付けできます。
すると、上で考えたリスト構造は、ε_0より小さい任意の順序数と対応付けできます。
ε_0から先を表すには、また別の工夫が必要でしょう。

107 :132人目の素数さん:2007/01/07(日) 01:18:33
つ前スレ
ttp://up.spawn.jp/file/up63970.lzh.html
かちゅの.datを圧縮しただけ あとはまかせる

108 :132人目の素数さん:2007/01/07(日) 04:41:05
下手にごちゃごちゃしたリスト構造を作るより、
順序数表記をリスト構造の表記法とみなす方がいいように思えてきた。

ε_0より小さい順序数はω^α*aの形の項の和として表されます。
>>106で多重リストの(*,…,*)要素という言い方を考えたのですが、
(*,…,*)の部分は指数αであり、要素の値は係数a+1となっています。
例えば、((1),(1,2))=ω^(ω+1)を考えると、指数はω+1=(2,2)、係数は1です。
リストを見ると、(2,2)要素が係数+1の2となっています。
このような見方をすれば、リスト関数は順序数の係数を変化させていく関数と言えます。

注:(a)というリストにはa-1という順序数を対応させないと自然な関係になりません。
  つまり、(1)=0, (2)=1, (3)=2, …

109 :132人目の素数さん:2007/01/07(日) 18:06:00
ごめんなさい。>>104の定義はおかしいです。
 f((3,3),(2))_2=f((f((f((1,3),(2))_2,2),(2))_2,2),(2))_2
 =f((f((1,2),(2))_2,2),(2))_2=f((1,2),(2))_2=1
となってしまい、二重リスト以上で常に1になってしまいます。

110 :132人目の素数さん:2007/01/07(日) 21:29:28
リスト関数とHardy functionを比較してみました。
Hardy functionの定義は、大きく分けると下の二種類があるようです。
 F[0](x)=x+1
 F[α+1](x)=F[α]^x(x) (αは順序数)
 F[λ](x)=F[Λ(x)](x) (λは極限順序数、Λ(x)はλに収束する基本列)
 H[0](x)=x
 H[α+1](x)=H[α](x+1)
 H[λ](x)=H[Λ(x)](x)
FとHの間には、F[α](x)=H[ω^α](x)という関係が成り立つそうなので、以下ではFを使います。

順序数についての説明。
 自然数を小さい順に並べると、0,1,2,3,…となります。
 そして、あらゆる自然数よりも大きい「数」の中で最小のものをωと表します。
 ωのような「数」を導入しても順序関係は保たれるので、このような「数」を順序数と呼びます。

 ωよりも大きい順序数を順番に考えると、ω,ω+1,ω+2,ω+3,…のようになります。
 ω,ω+1,ω+2,ω+3,…のうちのどの順序数よりも大きい最小の順序数は、ω*2=ω+ωと書けます。
 このとき、ω,ω+1,ω+2,ω+3,…をω*2に収束する基本列と呼びます。
 この基本列をΛ(x)としたときには、Λ(x)=ω+xです。
 また、基本列を用いて定義した順序数を極限順序数と呼びます。
 同様に、ω*3=ω*2+ω, ω*4=ω*3+ω, …という順序数を考えることができます。

 そして、Λ(x)=ω*xという基本列を考えます。
 この基本列のどの数よりも大きい最小の順序数をω^2=ω*ωと書きます。
 ω*a+b(a,bは自然数)に対し、ω*a+b<ω*a+ω=ω*(a+1)<ω*ω=ω^2ですから、ω*a+b<ω^2です。
 そして、ω^2+1,ω^2+2,…と順に考えれば、ω^2+ω, ω^2+ω*n, ω^2*2=ω^2+ω^2, ω^2*nが表せます。
 Λ(x)=ω^2*xを考えると、ω^3=ω^2*ωが表せます。
 同様にω^nを表し、Λ(x)=ω^xを考えればω^ωが定義できます。

111 :132人目の素数さん:2007/01/07(日) 21:58:15
 そしてω^(ω+1)=ω^ω*ω, ω^(ω*2)=ω^(ω+ω), ω^ω^2=ω^(ω*ω)などを考えていけば、
 ω^ω^ω, ω^ω^ω^ω, ω^ω^ω^ω^ωなどが表せます。
 Λ(x)=ω^ω^…^ω^ω(ωはx個) としたときの収束先がε_0です。
 ω^ε_0という数を考えると、ω^Λ(x)=ω^ω^…^ω^ω(ωはx+1個)よりも大きい最小の順序数となりますが、
 これはε_0です。よってω^ε_0=ε_0という関係が成り立ちます。

細かい計算を書くと長くなるので省略しますが、
Hardy functionのF[α]でαに1を足すことは、リスト関数でxの右の数に1を足すことに相当します。
また、αにωを足すことは、リスト関数でxを一つ右に移動させることに相当します。
αにω^2を足すことは、リスト関数でxの一つ右の一重リストの数に1を足すことに相当し、
αにω^3を足すことは、リスト関数でxを一つ右の一重リストに移動させることに相当します。
一般に、αにω^(2n)を足すことは、xの一つ右のn重リストの数に1を足すことに相当し、
αにω^(2n+1)を足すことは、xを一つ右のn重リストに移動させることに相当します。
f_2を使うとn重リストのnをいくらでも大きくできるので、f_2はF[ω^ω]に相当します。

結論として、f_(n+1)はF[ω^ω*n]に相当します。
過去ログによれば、ふぃっしゅ関数ver.1<F[ω^2]、ふぃっしゅ関数ver.2<F[ω^3]、
ふぃっしゅ関数ver.3はF[ω^ω*63]程度だそうなので、
f_64(3,3)はふぃっしゅ数ver.3程度の大きさということになります。

多重リストはω^ω^ωより小さい順序数に対応しますが、f_2≒F[ω^ω]=H[ω^ω^ω]なので、
リスト構造を拡張してε_0未満まで表せるようにしてもせいぜいH[ε_0]程度でしょう。
それならばリスト関数を使わずともHardy functionを使えばいいわけで、
リスト関数を拡張する意味はもはやないと思います。

それはともかく、このスレから読み始めた人向けの順序数やHardy functionの説明も必要でしょうね。
前スレでの順序数やHardy functionの説明はまとまってないので。

112 :もやしっ子:2007/01/07(日) 23:50:03
ログありがとうございます。
それにしても、えらいことになってきましたな…

113 :132人目の素数さん:2007/01/08(月) 20:47:46
巨大数を作るための方針についての考え。
今までは、
 急激に増加する関数を作る→関数を利用して巨大数を作る
という考えだったわけです。
ところが、多変数関数やリスト構造などを利用した大抵の関数よりもH[ε_0]の方が大きい。
それならば、巨大な順序数を作ってHardy functionを利用する方が簡単に大きな関数が作れます。
では、巨大な順序数を作るにはどうすればいいか。
それには、順序数から順序数への大きな関数を作ればいいわけです。つまり、
 急激に増加する順序数の関数を作る→関数を利用して巨大な順序数を作る
 →Hardy functionを利用して巨大数を作る
ということです。順序数の関数を作るには、Veblen関数を拡張するのがいいでしょう。
結局、これはナゴヤ関数と同じ考えです。
これから先、効率よく巨大数を作っていくためには、
順序数、Veblen関数、Hardy functionの理解が欠かせないと思います。

>>105
ZFCの公理系とか、全順序・半順序とかはひとまず無視しても支障はないかと思います。
ε-δ論法を知らなくても極限や微積分についてある程度理解はできるように、
そういうことを知らなくても順序数やVeblen関数、Hardy functionは理解できると思います。
ただ、Veblen関数やHardy functionについてのまとまった説明がないのが難しいところですが。

114 :132人目の素数さん:2007/01/08(月) 21:44:46
>>89
Veblen関数については、6-292の定義だけを見ても全く分からないと思います。
Veblen関数で定義される順序数への収束列というのを考えると理解しやすいでしょう。
以下の説明では具体例を書くと長くなるので、具体例は自分で考えてみてください。

α(n) (ただしnは自然数)という順序数の数列を考えたとき、
α(n)のどの項よりも大きい順序数の中で最小のものをαとすれば、
α(n)はαへの収束列です。ωへの収束列はω(n)=nとして考えます。

Veblen関数に入る前に、和や積に関する収束列を考えます。
以下では、βとγはそれぞれβ(n)とγ(n)の収束先になっているとします。
α=β+γのとき、α(n)=β+γ(n)とします。
α=β*(m+1) (mは自然数)のとき、α(n)=β*m+β(n)とします。

α=φ_0(γ)=ω^γとします。
γ=0のとき、α=ω^0=1なので収束列は考えません。
γ=γ'+1と表されるとき、α(n)=φ_0(γ')*n=ω^γ'*nとします。
α(n)の収束先は、ω^γ'*ω=ω^(γ'+1)=ω^γとなり、αに一致します。
γへの収束列がγ(n)のとき、α(n)=φ_0(γ(n))=ω^(γ(n))とします。

α=φ_(β'+1)(γ)とします。
γ=0のとき、α(0)=φ_β'(0)、α(n+1)=φ_β'(α(n))という漸化式で定義します。
γ=γ'+1のとき、α(0)=φ_(β'+1)(γ')+1、α(n+1)=φ_β'(α(n))とします。
γへの収束列がγ(n)のとき、α(n)=φ_(β'+1)(γ(n))とします。

βへの収束列がβ(n)のとき、α=φ_β(γ)とします。
γ=0のとき、α(n)=φ_(β(n))(0)とします。
γ=γ'+1のとき、α(n)=φ_(β(n))(φ_(β)(γ')+1)とします。
γへの収束列がγ(n)のとき、α(n)=φ_(β)(γ(n))とします。

115 :5-682:2007/01/08(月) 23:13:01
皆さん順序数やリスト関数についての説明ご苦労様です。

最初の案のナゴヤ関数はF[*](x)の*の部分が
2変数以上のリストのとき、HardyFunctionを利用して
順序数から巨大な順序数を作ることになるということです。
例えばF[1, 1](x) = F^x[ω](x) = F[F[ ... F[ω](ω) ... ](ω)](x)
となり、[ ]のネストで順序数ωから巨大順序数が作られます。
つまり、順序数→順序数変換の段階からHardyFunctionを
使っていることになります。

116 :5-682:2007/01/08(月) 23:24:06
続き。

ところでHardyFunctionでは
F[ε0](x) >=(( ... m(x) ...)m(2)f)(x) となることがわかっているので
F[ε0](ω)はふぃっしゅ関数Ver5相当の巨大な順序数になります。
ということはVeblen関数を多変数に拡張してもF[ε0](ω)には
足元にも及ばないと思われます。
(それどころか(多重リスト)リストに拡張しても追いつかないと考えられる)
したがって、ナゴヤ関数はF[2, n](x)の段階で
多重リスト関数に拡張したVeblen関数を使ったHardyFunctionを
はるかに越える巨大増加関数になってしまいます。


117 :5-682:2007/01/08(月) 23:51:12
ただ、現時点での問題として、F[ε0](ω)が
どの形の順序数で表されるかが問題になっています。
例えばF[1](x) = x + 1として、
F[ω](x) = x*2
F[ω*2](x) = x*2^x
F[ω*3](x) = ( ... (x*2^x)* ... )*2^(x*2^( ... (x*2^x) ...)) > x*2^^x
F[ω*2^ω](x) >= F[ω*ω](x) >= 2^^ ... ^^x = ak(2, x, x)
となり、途中で2^xとか2^2^ ... 2^xが出てくるところが曲者です。
今はF[λ(2^ω)](x) = F[λ(2^x)](x)としているところです。


118 :132人目の素数さん:2007/01/09(火) 04:42:57
順序数に対するHardy functionの定義をきちんと考えてみる必要がありそうですね。
順序数に対する演算は自然数に対する演算と性質が違うので、
単純にxとωを置き換えても、一意に定まる保障がありません。
例えば、1+x=x+1ですが、1+ω=ω≠ω+1です。
そして、2^ω=ωとなってしまいます。
2^ω=ωなのに2^xとxという違うものに置き換えてしまうと、一意的に定義されるのかが不安です。

もし、順序数に対するHardy functionの定義を最初に戻って考えるとすれば、
 H[0](x)=x H[α+1](x)=H[α](x+1)
に対しては
 H[0](β)=β H[α+1](β)=H[α](β+1)
とすればいいですが、
 H[α](x)=H[α_x](x)
に対しては、α_βが定義できなければ単純な置き換えはできません。
もしも、α_βはβが極限順序数のときにα_β_nの極限だとしてしまうと、α_ωはαそのものになります。
すると、H[α](ω)=H[α_ω](ω)=H[α](ω)となって定義されません。
なので、α_nのnを順序数に拡張することはできません。
かといって、H[α](β)をH[α_n](β_n)の極限としてもおかしくなります。
というのも、H[α](ω)はH[α_n](n)の極限ですが、
H[α_n](n)は自然数なのでその極限はωであり、H[α_n](ω)=ωとなってしまいます。
そして、H[α](β)をH[α_n](β)の極限としたときには、H[ω](β)=β+ωまではうまく定まるのですが、
H[ω+1](β)=β+1+ω=β+ωとなってしまい、これ以上大きくなりません。
こういった変なことを起こさずに、うまく順序数に対するHardy functionを定義できるのでしょうか。

119 :132人目の素数さん:2007/01/09(火) 04:45:38
順序数に対するHardy functionの定義をきちんと考えてみる必要がありそうですね。
順序数に対する演算は自然数に対する演算と性質が違うので、
単純にxとωを置き換えても、一意に定まる保障がありません。
例えば、1+x=x+1ですが、1+ω=ω≠ω+1です。
そして、2^ω=ωとなってしまいます。
2^ω=ωなのに2^xとxという違うものに置き換えてしまうと、一意的に定義されるのかが不安です。

もし、順序数に対するHardy functionの定義を最初に戻って考えるとすれば、
 H[0](x)=x H[α+1](x)=H[α](x+1)
に対しては
 H[0](β)=β H[α+1](β)=H[α](β+1)
とすればいいですが、
 H[α](x)=H[α_x](x)
に対しては、α_βが定義できなければ単純な置き換えはできません。
もしも、α_βはβが極限順序数のときにα_β_nの極限だとしてしまうと、α_ωはαそのものになります。
すると、H[α](ω)=H[α_ω](ω)=H[α](ω)となって定義されません。
なので、α_nのnを順序数に拡張することはできません。
かといって、H[α](β)をH[α_n](β_n)の極限としてもおかしくなります。
というのも、H[α](ω)はH[α_n](n)の極限ですが、
H[α_n](n)は自然数なのでその極限はωであり、H[α_n](ω)=ωとなってしまいます。
そして、H[α](β)をH[α_n](β)の極限としたときには、H[ω](β)=β+ωまではうまく定まるのですが、
H[ω+1](β)=β+1+ω=β+ωとなってしまい、これ以上大きくなりません。
こういった変なことを起こさずに、うまく順序数に対するHardy functionを定義できるのでしょうか。

120 :132人目の素数さん:2007/01/09(火) 06:22:16
二重に投稿されてますね。すみません。
Hardy functionのもう一つの定義である、
 F[0](x)=x+1 F[α+1](x)=F[α]^x(x) F[α](x)=F[α_x](x)
を使えばうまく定義できそうです。
 F[0](β)=β+1
 F[α+1](β)=F[α]^β(β)
 F[α](β)はF[α_n](β)の極限(ただしβ<ωのときn=β)
ただし、F[α]^β(γ)は以下のように定義します。
 F[α]^0(γ)=γ
 F[α]^(β+1)(γ)=F[α](F[α]^β(γ))
 F[α]^β(γ)はF[α]^(β_n)(γ)の極限
こうすると、F[1](β)=β*2、F[2](β)=β*2^β、F[3](ω)=ε_0となります。
ただ、F[3](ω)への収束列はω, ω^2, ω^ω, ω^ω^ω, …となり、
ε_0への普通の収束列とは少し異なります。

121 :132人目の素数さん:2007/01/09(火) 07:37:32
訂正
F[3](ω)への収束列はω, ω^2, ω^ω^2, ω^ω^ω^2, …です。
おそらく、β≧ω^2ならば2^β=ω^βだと思います。

122 :132人目の素数さん:2007/01/09(火) 12:32:09
今年に入ってから久々に盛り上がってますね
自分は全くの門外漢なので応援しつつ
スレの成り行きを見守らせてもらいます

123 :132人目の素数さん:2007/01/09(火) 19:46:58
>>121
再度訂正。
F[3](ω)への収束列はω, ω^2, ω^ω, ω^ω^ω, …で、
β≧ω^ωならばたぶん2^β=ω^βです。

とりあえず、6-510の書き込みを元に、勝手にナゴヤ関数の2変数リスト以下の場合を再定義してみます。
 L[1](x) = f(x)
 L[n+1](x) = f(L[n](x))
 L[ω](x) = L[x](x)
はそのまま使いますが、f(x)に対しては「順序数に対してもきちんと定義されているもの」という条件をつけます。
(例えばf(x)=x+1とか)
そして、収束列α_nの定められた極限順序数αに対して、
 L[α](x) = L[α_x](x)
 L[α+n+1](x) = L[α](L[α+n](x))
とします。リストが2項のときは
 L[2 , 1](x) = L[ω](x)
 L[2 , n+1](x) = L[L[2 , n](ω)](x)
 L[m+1 , 1](x) = L[m , ω](x)
 L[m+1 , n+1](x) = L[m ,L[m+1 , n](ω)](x)
とします。ここまでは、元の定義とほぼ同じです。
リストの右の数が順序数のときの定義は見当たらないようなので、
 L[2 , α](x) = L[α_x](x)
 L[2 , α+n+1](x) = L[L[2 , α+n](ω)](x)
 L[m+1 , α](x) = L[m , α_x](x)
 L[m+1 , α+n+1](x) = L[m ,L[m+1 , α+n](ω)](x)
としておきます。

124 :132人目の素数さん:2007/01/09(火) 19:48:12
すべきことは、xがωのときの定義と、極限順序数に対する収束列の定義です。
まず、ωの収束列はω_n=nとします。そして、xがωのときは以下のように定義します。
 L[1](ω) = f(ω)
 L[n+1](ω) = f(L[n](ω))
 L[ω](ω) は収束列が L[n](ω) の極限順序数
 L[α](ω) は収束列が L[α_n](ω) の極限順序数
 L[α+n+1](ω) = L[α](L[α+n](ω))
 L[2 , 1](ω) = L[ω](ω)
 L[2 , n+1](ω) = L[L[2 , n](ω)](ω)
 L[m+1 , 1](ω) = L[m , ω](ω)
 L[m+1 , n+1](ω) = L[m ,L[m+1 , n](ω)](ω)
 L[2 , α](ω) は収束列が L[α_n](ω) の極限順序数
 L[2 , α+n+1](ω) = L[L[2 , α+n](ω)](ω)
 L[m+1 , α](ω) は収束列が L[m , α_n](ω) の極限順序数
 L[m+1 , α+n+1](ω) = L[m ,L[m+1 , α+n](ω)](ω)
こうすれば、関数がきちんと定義されないということは避けられるはずです。

125 :132人目の素数さん:2007/01/10(水) 07:48:27
Veblen関数を拡張したものを定義してみました。
定義が長いので、とりあえず定義だけを書いておきます。

φ([α,β],[γ,δ],…,[ε,ζ])という形で表記する。
ただしα>γ>…>εであり、φ(…,[α,0],…)=φ(…,…)とする。
φ([1,α],[0,β])=φ_α(β)、φ([2,1])=Γ_0である。
α=lim α_nと書いたとき、αはα_nを収束列とする極限順序数とする。

元のVeblen関数とΓ_0の定義。
 φ([0,0])=φ()=1
 φ([0,α+1])=lim φ([0,α])*n
 φ([0,α])=lim φ([0,α_n]) (φ([0,α])≠αのとき)
 φ([1,α+1],[0,0])=φ([1,α+1])=lim φ_n
  ただしφ_0=φ([1,α]),φ_(n+1)=φ([1,α],[0,φ_n])
 φ([1,α+1],[0,β+1])=lim φ_n
  ただしφ_0=φ([1,α+1],[0,β])+1,φ_(n+1)=φ([1,α],[0,φ_n])
 φ([1,α+1],[0,β])=lim φ([1,α+1],[0,β_n]) (φ([1,α+1],[0,β])≠βのとき)
 φ([1,α],[0,0])=φ([1,α])=lim φ([1,α_n]) (φ([1,α])≠αのとき)
 φ([1,α],[0,β+1])=lim φ([1,α_n],[0,φ([1,α],[0,β])+1])
 φ([1,α],[0,β])=lim φ([1,α],[0,β_n]) (φ([1,α],[0,β])≠βのとき)
 φ([2,1])=lim φ_n
  ただしφ_0=φ(),φ_(n+1)=φ([1,φ_n])

126 :132人目の素数さん:2007/01/10(水) 07:49:20
αが後続順序数のとき。
 φ(…,[α+1,1])=lim φ_n
  ただしφ_0=φ(),φ_(n+1)=φ([α,φ_n])
 φ(…,[α+1,1],[0,β+1])=lim φ_n
  ただしφ_0=φ(…,[α+1,1],[0,β])+1,φ_(n+1)=φ([α,φ_n])
 φ(…,[α+1,1],[0,β])=lim φ(…,[α+1,1],[0,β_n]) (φ(…,[α+1,1],[0,β])≠βのとき)
 φ(…,[α+1,β+1])=lim φ_n
  ただしφ_0=φ(…,[α+1,β])+1,φ_(n+1)=φ(…,[α+1,β],[α,φ_n])
 φ(…,[α+1,β+1],[0,γ+1])=lim φ_n
  ただしφ_0=φ(…,[α+1,β+1],[0,γ])+1,φ_(n+1)=φ(…,[α+1,β],[0,φ_n])
 φ(…,[α+1,β+1],[0,γ])=lim φ(…,[α+1,β+1],[0,γ_n]) (φ(…,[α+1,β+1],[0,γ])≠γのとき)
 φ(…,[α+1,β])=lim φ(…,[α+1,β_n]) (φ(…,[α+1,β])≠βのとき)
 φ(…,[α+1,β],[0,γ+1])=lim φ(…,[α+1,β_n],[0,φ(…,[α+1,β],[0,γ])+1])
 φ(…,[α+1,β],[0,γ])=lim φ(…,[α+1,β],[0,γ_n]) (φ(…,[α+1,β],[0,γ])≠γのとき)
αが極限順序数のとき。
 φ(…,[α,1])=lim φ(…,[α_n,1])
 φ(…,[α,1],[0,β+1])=lim φ(…,[α_n,1],[0,φ(…,[α,1],[0,β])+1])
 φ(…,[α,1],[0,β])=lim φ(…,[α,1],[0,β_n]) (φ(…,[α,1],[0,β])≠βのとき)
 φ(…,[α,β+1])=lim φ(…,[α_n,φ(…,[α,β])+1])
 φ(…,[α,β+1],[0,γ+1])=lim φ_n
  ただしφ_0=φ(…,[α,β+1],[0,γ])+1,φ_(n+1)=φ(…,[α,β],[0,φ_n])
 φ(…,[α,β+1],[0,γ])=lim φ(…,[α,β+1],[0,γ_n]) (φ(…,[α,β+1],[0,γ])≠γのとき)
 φ(…,[α,β])=lim φ(…,[α,β_n]) (φ(…,[α,β])≠βのとき)
 φ(…,[α,β],[0,γ+1])=lim φ(…,[α,β_n],[0,φ(…,[α,β],[0,γ])+1])
 φ(…,[α,β],[0,γ])=lim φ(…,[α,β],[0,γ_n]) (φ(…,[α,β],[0,γ])≠γのとき)

これで、lim φ_n (φ_0=φ(),φ_(n+1)=φ([φ_n,1]))を考えると非常に大きい順序数ができます。

57 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.02.02 2014/06/23 Mango Mangüé ★
FOX ★ DSO(Dynamic Shared Object)