07/01/23 22:01:16
>>174
最近はかなり解説が咀嚼されていますので、研究室のHardyと合わせて
読んでみて下さい。ヘボの僕でもVeblenまで追い付くことができました。
些細な疑問でも書いて頂ければ、優しい人が丁寧に教えてくれます。
(他力本願…)
個人的な印象では、リスト関数の解読よりは物量的に楽だと思いました。
変な文字達とお友達になれれば、結構すぐですよ。
176:もやしっ子
07/01/24 00:11:51
言ったそばから質問でございます。Veblenの解説を書いているのですが、
＞βへの収束列がβ(n)のとき、α=φ_β(γ)とします。
＞γ=γ'+1のとき、
＞α(n)=φ_(β(n))(φ_(β)(γ')+1)とします。
ここのa(n)がこの形に展開される理屈が分かりませんでした。
値をうまく置き換えてやればφ_β(γ)=αに持っていけるのでしょうか。
177:もやしっ子
07/01/24 08:28:21
どうにもφ_nという式が顔を出してきます。この子ってば
どうやって飛ばせばいいですか。
α=φ_ω(1)=ε_1なのかなーと思ったり。
178:もやしっ子
07/01/24 14:24:04
βへの収束列がβ(n)の場合の具体例の様子を見てみました。
ここではβ=ωとおいて β(n)=n,γ'=0とする。 このとき、
α=φ_ω(1)
α(n)=φ_n(φ_ω(0)+1)
α(0)=φ_0(2)=0^2=1
ここで定義より α=φ_ω(1)=ε_1 なお、このαの収束列は、
1,ε_0,ω^(ε_0+1),ω^ω^(ε_0+1),ω^ω^ω^(ε_0+1),…と続き、
α(0)=1
α(1)=ε_0 そして最終的にnが十分大きいとき
α(n)=(ω↑↑(n-2))^(ε_0+1)となる。
これがα=(ω↑↑ω)^(ε_0+1)=ε_1 の収束列である。
話を α(n)=φ_n(φ_ω(0)+1) に戻すと、
φ_ω(0) = 「すべての ω'< ω に対し φ_ω'(δ)=δ となる δ」 のうち
0番目のもの。 ω'=0 とおくと(ωより小さい順序数は自然数しかない)
φ_0(δ)=ω^δ=δ が得られ、
定義より φ_ω(0)=ε_0 から α(n)=φ_n(ε_0+1) 以上より
φ_n(ε_0+1)=(ω↑↑(n-2))^(ε_0+1) (n<2) 謎のオチ。
179:もやしっ子
07/01/24 14:49:18
思いつきで喋っていますが。
文京区シビックセンターの良さげな部屋を借りるツテができたので
2月あたりに近隣の方はゼミごっこしませんか？
メンツが集まらない場合は、素人衆に巨大数をオルグする
イベントに変更となります。いかがでしょう。
僕が暇すぎるのかもしれません。
180:１３２人目の素数さん
07/01/24 14:58:46
うちの近くだｗ
181:１３２人目の素数さん
07/01/24 15:14:59
>>178
φ_ω(1)=ε_1というのは、もしかしてωを1に置き換えてますか？
Hardy functionと違ってφの添え字のωは1に置き換えられません。
φ_ω(0)というのは、φ_0(0), φ_1(0), φ_2(0), φ_3(0), …という収束列の収束先で、
φ_ω(1)というのは、φ_0(φ_ω(0)+1), φ_1(φ_ω(0)+1), φ_2(φ_ω(0)+1), …の収束先です。
182:もやしっ子
07/01/24 16:01:35
>>181
えーっと…
φ_ω(1)=「すべての ω'< ω に対し φ_ω'(δ)=δ となる δ」 のうち
1番目のもの …ここですな。
もろに文脈が混線していたようです。
さて、
α=φ_ω(1) のとき
α(n)=φ_n(φ_ω+1) などと性懲りもなくやってますが、
φ_β(γ)そのものが列の収束先そのものとは、全く気付きませんでした。
いやはや。
183:１３２人目の素数さん
07/01/24 19:59:20
数学板オフ？
都内ならkingも呼ぼうぜ。
184:もやしっ子
07/01/24 21:55:40
巨大数に関連した催しとして僕個人が突発的に企画しました。
いっぺんホワイトボード使ってワイワイやってみたかったのです。
情報や理解も共有することができるかもしれないですし。
往年の功労者諸氏はもう見てないかな…
あと、民間人に巨大数ロマンを植え付けるという企みもあります。
30人くらい入れる部屋とか用意できますが、そんなには来ないでしょう。
2/10を候補日としています。
185:もやしっ子
07/01/25 12:46:24
Cantor normal formの和訳みたいなことをしてみました。そしたら
「集合論入門 無限への誘い」の169,170ページにも「カントールの標準形」
の解説がありました。読み比べてみたところ、それぞれ少し異なる箇所が
あったりしたので適当にまぜて体裁を整えました。
やばかったら指摘してください。たぶん本読んだ方が早いですが。
0でない任意の順序数αは以下のような式に一意に展開することができる。
α=((ω^(β_1))・c_1)+((ω^(β_2))・c_2)+…+((ω^(β_k))・c_k) [kは自然数]
c_1,c_2,…,c_k は正の整数
β_1＞β_2＞…＞β_k はそれぞれ順序数 (β_k=0 でも可)
上式ではωを用いているが、これは「ωを底とした」場合である。
底には2以上の順序数を用いてよい。
このように展開された式を、αのCantor normal formと呼ぶ。
186:１３２人目の素数さん
07/01/25 15:06:57
任意なの？
非可算順序数でも大丈夫なんだ。
187:１３２人目の素数さん
07/01/25 20:48:18
任意でよかったはず
188:KingOfUniverse ◆667la1PjK2
07/01/25 23:04:05
talk:>>183 何やってんだよ？
189:１３２人目の素数さん
07/01/26 00:39:58
>>186
任意でおｋです。
190:１３２人目の素数さん
07/01/27 19:56:56
英語版Wikipediaに、Γ_0よりずっと大きい順序数を定義する方法がありました。
それを和訳すると下のようになります。
ψ(α)は、0とΩ(最小の非可算順序数)から始めて、それ以前に作られた順序数に対し
加法、Veblen関数、ψを繰り返し適用しても作ることのできない最小の順序数である。
ただし、ψはαより小さい順序数に対してのみ適用する。
定義には非可算順序数を用いていますが、定義される順序数は可算です。
これだけだとよく分からないし、具体例はほとんどなかったので、自分なりに解釈してみました。
もしかしたら、間違っているところがあるかもしれませんが。
まず、ψ(0)を考えます。この時点ではまだψは使えないので、加法とVeblen関数だけを使います。
0に対して加法とVeblen関数を使うと、Γ_0未満の順序数をすべて作り出すことができます。
Ωから作った順序数はどれも非加算なので、Γ_0を作り出すことはできません。
なので、ψ(0)=Γ_0ということになります。
次に、ψ(1)を考えます。これは、0とψ(0)とΩに対して加法とVeblen関数を使っても作れない
最小の順序数ですが、これはΓ_1です。同様にして、ψ(α)=Γ_α(ただし、α≦ψ(Ω))となります。
191:１３２人目の素数さん
07/01/27 19:57:32
この方法を繰り返していくと、Γ_Γ_Γ_…_0の収束先として定義される順序数
(>>132,>>136の表記を用いるとφ([2,1],[1,1])と書ける)よりも小さな数はすべて作ることができますが、
φ([2,1],[1,1])は作ることができません。そこで、初めてψ(Ω)を考えます。
ψ(Ω)は、0とΩに加法、Veblen関数、ψを適用しても作ることのできない最小の順序数です。
(ただしΩにはψを適用しない) つまり、ψ(Ω)=φ([2,1],[1,1])です。
ψ(ψ(Ω))を考えると、ψ(Ω)=φ([2,1],[1,1])より小さい順序数に
加法、Veblen関数、ψを適用しても作ることのできない最小の順序数なので、
ψ(ψ(Ω))=ψ(Ω)=φ([2,1],[1,1])となります。
ψ(Ω)≦α≦Ωとしてψ(α)を考えると、ψ(Ω)を使うことはできないので、ψ(α)=ψ(Ω)となります。
なので、次はψ(Ω+1)を考えればいいです。
あとは結果だけ書きますが、>>132,>>136の表記とψを用いた表記を比較すると、
ψ(Ω^Ω^α)=φ([α,1]) (α≧ω)となるようなので、
>>132,>>136の表記ではψ(Ω^Ω^Ω)未満の順序数しか表せないようです。
6-708で出てきたHoward ordinalというのはψ(ε_(Ω+1))だそうです。
ε_(Ω+1)はおそらくΩ^Ω^Ω^…^Ωの収束先です。
192:１３２人目の素数さん
07/01/28 06:42:53
Ω^Ω^ΩをVeblen関数で表すには、Ω=ω^Ωという性質を使って
Ω^Ω^Ω=(ω^Ω)^Ω^Ω=ω^(Ω*Ω^Ω)=ω^Ω^Ω=ω^(ω^Ω)^Ω
=ω^ω^(Ω*Ω)=ω^ω^(ω^Ω*ω^Ω)=ω^ω^ω^(Ω+Ω)として、
Ω^Ω^Ω=φ_0(φ_0(φ_0(Ω+Ω)))とすればいいと思います。
非可算順序数を可算順序数と同じように扱っていいのかは分かりませんが。
193:１３２人目の素数さん
07/01/28 15:07:45
(^ω^)よくわからないお
194:１３２人目の素数さん
07/01/28 16:08:57
本当に分かろうとする気があるのかと、
ただ(^ω^)を貼り付けたいだけちゃうんかと。
195:１３２人目の素数さん
07/01/28 17:47:27
ψで表された順序数への収束列は、おそらく以下のように定まるはずです。
α=ψ(0)のとき、α_0=φ_0(0), α_(n+1)=φ_(α_n)(0)
α=ψ(β+1)のとき、α_0=ψ(β)+1, α_(n+1)=φ_(α_n)(0)
α=ψ(β)(βは収束列の定義された順序数)のとき、α_n=ψ(β_n)
α=ψ(β)(βは収束列の定義されていない非可算順序数)のときは、
以下の手順で収束列を定める。
まず、βに注目する。
注目する順序数がΩになるまで、以下の手順を繰り返す。
注目する順序数が和のときは、一番右の項に注目する。
注目する順序数がφ_γ(δ)の形のときは、以下のようにする。
δ=0のときは、γに注目する。
δ=δ'+1のときは、δをφ_γ(δ')+1に置き換えてからγに注目する。
その他のときは、δに注目する。
ψ(β)の、注目するΩをxで置き換えた関数をf(x)とする。(f(x)は順序数の関数)
α_0=0, α_(n+1)=f(α_n)とする。
最後の手順を、具体例でやってみます。(かなり複雑な例ですが)
ψ(φ_(φ_(φ_Ω(Ω+Ω))(Ω+2))(0))でやってみると、
まずはφ_(φ_(φ_Ω(Ω+Ω))(Ω+2))(0)に注目します。
( )の中が0なので、添え字のφ_(φ_Ω(Ω+Ω))(Ω+2)に注目します。
( )の中が+1の形なので、Ω+2をφ_(φ_Ω(Ω+Ω))(Ω+1)+1に置き換えて、
添え字のφ_Ω(Ω+Ω)に注目します。
今度は( )の中が0でも+1の形でもないので、Ω+Ωに注目します。
Ω+Ωは和なので、右のΩに注目します。
注目したΩをxに変えると、
f(x)=ψ(φ_(φ_(φ_Ω(Ω+x))(φ_(φ_Ω(Ω+Ω))(Ω+1)+1))(0))
となります。 この関数を入れ子にしたものが収束列となります。
この収束列の定義でHardy functionも使ってF[ψ(Γ_(Ω+1))]という関数を作ると、
ものすごく大きな自然数の関数となるはずです。
ただし、Γ_(Ω+1)の収束列はα_0=Ω+1, α_(n+1)=φ_(α_n)(0)です。
196:１３２人目の素数さん
07/01/28 17:48:07
結局のところ、巨大な非可算順序数を作り、非可算順序数から巨大な可算順序数の関数を作り、
可算順序数の関数から巨大な可算順序数を作り、可算順序数から巨大な自然数の関数を作り、
自然数の関数から巨大な数を作るということになります。
Ωを可算順序数の変数で置き換えるのと、ωを自然数の変数で置き換えるのには共通点も見られます。
今やっていることがよく分からないという気持ちも分かります。
具体的に計算しようにも巨大すぎて、現実には計算できないような数を扱っているし、
主題は数→自然数の関数→順序数→可算順序数の関数と、どんどん普通の数から離れてきているので。
ただ、作られていく数はどんどん巨大になってきています。
一つ残念なのは、このスレの住人がこれまでにないような巨大な数を作り出したと思っても、
いつもそれを上回る巨大な数を作り出す方法が既に数学界に存在しているということです。
上で述べた関数も、Hardy functionと英語版Wikipediaのψ表記を組み合わせただけなのに、
このスレで作られた関数の中ではふぃっしゅ数ver.4を除くどの関数よりも大きいわけです。
(ふぃっしゅ数ver.4はBBを用いて作られた、定義可能だが計算不能な数なので別格ですが)
それでも、巨大な数の作り方を紹介していくというだけで十分意味のあることだと思いますが。
197:１３２人目の素数さん
07/01/29 23:15:55
>>179 >>184
ゼミは本当にやるのかな？はたして、このスレの
住人は何人くらい集まるか？
素人衆向けの企画ならば、素人衆として参加します。
実際に素人衆だし。
198:もやしっ子
07/01/30 03:18:41
>>197
部屋はすでに取ってあります。2/10午後、文京シビックセンター会議室です。
初心者と熟練者の議論のギャップをどう埋められるか、という。
とりあえずその日程オッケーみたいな方は、ここで点呼してみて下さい。
5人も集まれば、十分に時間が潰せると思います。たぶん。
199:１３２人目の素数さん
07/02/01 00:07:15
WikipediaにもHoward ordinalについて書かれていますね。
英語ならHoward ordinalの定義について書いてある論文は結構見つかるのですが、
分かりやすかったものは、Veblen関数の応用で、
φ_α[Ω](β):=φ_α[γ](0)=γとなるγのうちβ番目のもの
とします。例えば、φ_Ω(0)=Γ_0、φ_(Ω+1)(0)=Γ_Γ_Γ_……となります。
以降はCNFと同様に、
Ω^α_0*β_0+Ω^α_1*β_1+Ω^α_2*β_2+……
（ただしα_0>α_1>α_2>……, Ω>β_i）
とすれば、φ_α(β)の有限和でHoward ordinalより小さいすべての順序数を表記できます。
200:１３２人目の素数さん
07/02/01 00:27:09
また、１変数にすることもできますね。
A(α):=ω^α（Ω>α）
A(α[Ω]+β):=A(α[γ])=γとなるγのうちβ番目のもの
例えば、
A(Ω)=ε_0
A(Ω*α+β)=φ_α(β)
A(Ω^2)=Γ_0 です。
もちろんA(ε_(Ω+1))とかもできますがさらに上の基数を使って、
B(α):=Ω^α
B(α[ω_2]+β):=B(α[γ])=γとなるγのうちβ番目のもの
とすれば、A( B(ω_2) ) = A( ε_(Ω+1) ), A( B((ω_2)^2) ) = A( Γ_(Ω+1) )
となってHoward ordinalよりも大きい順序数を作ることができます。
しかし、この方法だとA(Ω),A(B(ω_2)),A(B(C(ω_3))),A(B(C(D(ω_4)))),………
という列の極限順序数が限界で、以降のうまい定義がなかなか難しいのですが・・・
201:１３２人目の素数さん
07/02/01 00:29:34
順序数の表記についてのサイト↓（英語）
URLﾘﾝｸ(web.mit.edu)
202:１３２人目の素数さん
07/02/01 02:23:36
英語版Wikipediaには、ψの拡張法の方針も載っていたので、それを定義してみました。
ψ_α(β)は、0に対して加法、Veblen関数、ψを繰り返し適用しても
作ることのできない、濃度がω_α(α番目の無限基数)の最小の順序数である。
ただし、ψの添字として用いる順序数を除いては、ψはβより小さい順序数にのみ適用する。
最後の行では、例えばψ_[ψ_0(1)](0)=ψ_[ψ_0(1)](1)＜ψ_[ψ_0(1)](2)のような
不自然なことを起こさないために、添字ではψを自由に使えるようにしてあります。
濃度に関しては、次の性質だけ理解しておけば十分だと思います。
ω以上の順序数には、濃度として一つの無限基数が対応する。
可算順序数の濃度は、ω(=ω_0)である。
α＜βならば、濃度ω_αの順序数＜濃度ω_βの順序数である。
濃度ω_α以下の順序数の収束列は、濃度ω_α以下の順序数に収束する。
最後の行は、「以下」であって「未満」ではありません。
例えば、ω_nはω_ω未満の順序数の収束列ですが、ω_ωに収束します。
添字付きψで定義される最大の非可算順序数はω_ω_…_0の極限です。
この順序数を仮にΨと書くことにすると、
添字付きψで定義される最大の可算順序数は、ψ_0(Ψ)となります。
203:１３２人目の素数さん
07/02/01 02:24:11
収束列の定義は、以下のようになるはずです。
α=ψ_0(0)のとき、α_0=φ_0(0), α_(n+1)=φ_(α_n)(0)
α=ψ_β(0)のとき、α=ω_βであり、
βに収束列があるときはα_n=ω_(β_n)となる。
α=ψ_β(γ+1)のとき、α_0=ψ_β(γ)+1, α_(n+1)=φ_(α_n)(0)
α=ψ_β(γ)(γは収束列の定義された順序数)のとき、α_n=ψ_β(γ_n)
α=ψ_β(γ)(γは収束列の定義されていない非可算順序数)のときは、
以下の手順で収束列を定める。
まず、γに注目する。
注目する順序数がψ_[δ+1](0)の形になるまで、以下の手順を繰り返す。
注目する順序数が和のときは、一番右の項に注目する。
注目する順序数がφ_ε(ζ)の形のときは、以下のようにする。
ζ=0のときは、εに注目する。
ζ=ζ'+1のときは、ζをφ_ε(ζ')+1に置き換えてからεに注目する。
その他のときは、ζに注目する。
注目する順序数がψ_ε(0)の形のときは、εに注目する。
γの、注目するψ_[δ+1](0)をxで置き換えた関数をf(x)とする。
α'_0=0, α'_(n+1)=ψ_δ(f(α'_n))とし、
収束列はα_0=0, α_(n+1)=ψ_β(f(α'_n))とする。
（つまり、最後だけはψ_βを適用し、それ以外はψ_δを適用する）
Ψ_0=0, Ψ_(n+1)=Ψ_[Ψ_n](0)
Hardy functionや、上記の順序数の計算のできるプログラムをRubyで作ってみました。
RubyはURLﾘﾝｸ(arton.hp.infoseek.co.jp)からインストールしてください。
URLﾘﾝｸ(www.uploda.net)
解凍するとLarge_number.rbというファイルがあるので、
これをメモ帳などで開くと初めの方に使い方が書いてあります。
204:１３２人目の素数さん
07/02/01 21:15:13
>>203
ＧＪ！ありがたく使わせていただきます。
205:１３２人目の素数さん
07/02/01 22:53:49
この前のプログラムはまだバグが残っていたので、修正しました。
URLﾘﾝｸ(www.uploda.net)
206:１３２人目の素数さん
07/02/02 20:17:08
プログラムは細かくみると、正確に計算してないところもあります。
たとえば、ω^φ_1(0)=ω^ε_0=ε_0=φ_1(0)ですが、
F[ω^φ_1(0)](2)とF[φ_1(0)](2)は違う結果になります。
また、>>190の定義からすればψ(ψ(Ω+2))=ψ(Ω)＜ψ(Ω+1)ですが、
F[ψ(ψ(Ω+2))](2)＞F[ψ(Ω+1)](2)となってしまうはずです。
ただ、普通に使う分には問題はないと思います。
207:１３２人目の素数さん
07/02/02 21:15:56
>206
>>130-131
208:１３２人目の素数さん
07/02/02 23:09:45
206も、130-131も、プログラムを書いたのも、全部私なので、
>>130-131みたいに収束列の異なる順序数は別物という見方をすれば
前者は問題ないのは分かってます。
後者に関しては、>>190での定義によるψと、
>>195の収束列から定義されるψが全く同じではないのが原因です。
数学的に厳密に言うのならば、Hardy functionに使っているものは
極限順序数ではなく、「収束列」です。ここでいう「収束列」は、
”自然数か「収束列」の列”として再帰的に定義できます。
ただ、「収束列」は列の収束先の極限順序数と対応づけることができ、
順序数の大小とHardy functionの増加度の大小には関連性があるので、
極限順序数と「収束列」を普段は同一視しているわけです。
でも、極限順序数と「収束列」は違うものであるため、>>206の前者のような問題が生じます。
>>131で「極限順序数と収束列は一対一に対応する」と言ってしまったのは不正確で、
極限順序数と「収束列」は一対多に対応します。
「収束列」と一対一に対応する（正確には「一対一対応させている」）のは、「極限順序数の表記」です。
>>205のプログラムが計算しているのは順序数ではなく、「収束列」です。
>>206で「プログラムが正確に計算してない」といったのも不正確ですね。
不正確だったのは定義の方であって、プログラムの計算が不正確なわけではありません。
209:１３２人目の素数さん
07/02/04 02:30:22
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
210:１３２人目の素数さん
07/02/04 02:40:11
この極めて小さい数に何か意味があるのだろうか。。。。。
211:１３２人目の素数さん
07/02/04 03:10:09
=(ω^Ω)^Ω^Ω=ω^(Ω*Ω^Ω)=(^o^)=ω^(ω^Ω)^Ω
=ω（=´ω`=）^ω^(Ω*Ω)=(^ω^)(^ω^)(^ω^)(o^Ω^o)=ω^ω^ω^ ^^ ^^
212:１３２人目の素数さん
07/02/05 18:39:05
073
213:１３２人目の素数さん
07/02/09 17:23:52
いよいよ明日ですね
214:１３２人目の素数さん
07/02/10 01:37:03
本当にやるの
215:もやしっ子
07/02/10 09:17:59
えーと、グレートに人が集まらないので次回に仕切り直そうかと思ってます。
ちゃんと準備して。
216:KingOfUniverse ◆667la1PjK2
07/02/10 20:05:54
人の脳を読む能力を悪用する奴を潰せ。
217:五劫の擦り切れ
07/02/11 02:56:43
ちょいと質問。
「グラハム数」のグラハム博士って、電話発明したグラハム・ベルと親戚？
ゼミ後に検索してみたら「秋山仁」やら「ベル研究所」がヒットしますが…
218:１３２人目の素数さん
07/02/11 08:03:49
ロナルド L. グレアムとアレクサンダー・グレアム・ベルか。
別にしんせきじゃねえんじゃね。
219:１３２人目の素数さん
07/02/12 07:05:12
Ronald Grahamはピーター・フランクルの友人で
AMSの会長をやってたこともある人。
秋山仁と日本語の離散数学の入門書も出してるね。
時代が全然違うからあまり「親戚」とは言わないんじゃないかなあ。
Ronald Lewis Graham (born October 31, 1935)
Alexander Graham Bell ( March 3, 1847 ? August 2, 1922 )
URLﾘﾝｸ(en.wikipedia.org)
URLﾘﾝｸ(en.wikipedia.org)
URLﾘﾝｸ(ja.wikipedia.org)
たぶん親戚関係は無いんじゃないの。日本の田中さんとかと同じで。
220:１３２人目の素数さん
07/02/16 16:58:37
ωやΩの固まりからどうやって自然数にするのかが気になるな....
221:１３２人目の素数さん
07/02/16 16:59:15
sage忘れスマソ
222:１３２人目の素数さん
07/02/23 15:22:03
オフと聞いてやってきました
223:１３２人目の素数さん
07/03/05 17:53:04
保守しておく
224:１３２人目の素数さん
07/03/11 18:19:18
age
225:１３２人目の素数さん
07/03/18 12:56:59
age
226:１３２人目の素数さん
07/03/28 23:37:18
ひさしぶりにのぞいてみたが、
大して進展はないのかな？
今のところチャンピオンは前スレの >>863 か。
227:１３２人目の素数さん
07/03/29 02:16:03
これかな？File not foundになるのが惜しいところ。
863 ：通りすがり：2006/08/29(火) 21:34:51
>>440-441 をちゃんと書いてみた。
チューリングマシンのままじゃ扱いにくいので、
今のコンピューター風命令にした。
ついでに拡張も。
URLﾘﾝｸ(free.gikoneko.net)
228:１３２人目の素数さん
07/03/29 02:31:01
ついでに440-441もコピー
440 ：通りすがり：2006/03/09(木) 18:27:05
●STEP0
比較的単純なマシンモデル（チューリングマシン）を定義することで、
どのような帰納的定義の関数よりも早く増大する関数、ビジービーバー関数が定義出来た。
ビジービーバー関数は「どのような帰納的定義の関数よりも早く増大する関数」の中ではほとんどＭＩＮの関数である。
BBに帰納的拡張をしていくことである程度大きくすることは可能。、
（BB^n(2)やBBのふぃっしゅ数的拡張など）
●STEP1
チューリングマシンにビジービーバーの値を返す動作を追加したマシンを考えてみる。
厳密にはたとえば、
各ステートの動作定義に１ビット加え、このビットが立っていたら
BB(テープ上のヘッド位置から右に続く１の数)個の１をヘッドの右側に書き込むという動作で良い。
このマシンｎステートでセット可能な１の数の最大をBB2(n)とすると、
この関数はビジービーバー関数に通常の多重帰納的定義を用いて拡張したどんな関数よりも早く増加する。
（BBのふぃっしゅ数的拡張もBB2に及ばない）
一般に、
『チューリングマシン＋関数f』のマシンｎステートで
セット可能な１の数の最大をBB｢f｣(n)とする。
BB｢f｣ は、fに通常の多重帰納的定義を用いて拡張したどんな関数よりも早く増加する。
BB｢恒等変換｣ = ビジービーバーであり、
BB｢ビジービーバー｣ が上の BB2 である。
BB｢f｣の｢｣の中に関数を入れることで新たな関数ができ、
帰納的定義の関数のように帰納的にBB｢f｣の定義が可能である。
229:１３２人目の素数さん
07/03/29 02:31:38
441 ：１３２人目の素数さん：2006/03/09(木) 18:28:15
●STEP2
STEP1の方法でマシンの帰納的定義を行っていけば大きい関数が作成できるが、
この方法にも限界がある。
この限界を超える為にはチューリングマシンに以下のような機能追加が必要である。
１．自然数から自然数への関数をテープに読み書きできる（可算無限のデータ量）
２．テープに関数の初期値（恒等関数で良い）をセット出来る
３．関数fからBB｢f｣をつくることが出来る
４．関数の値を返せる
といった感じであろうか。
（厳密な定義は他の人に任せる）
このようなマシンｎステートで表現できる最大の数をCC(n)とする。
これはいわば「STEP1の帰納的拡張をｎ文字以内で一番効率よく行った場合の数」
のようなものであり、CC(n)はBB｢｣のどんな帰納的拡張よりも早く増大する。
●STEP3
さらなる拡張はやはりマシン自体を定義できるようなマシンということになるだろう。
矛盾がおこらないような定義で最良のものはどんな感じになるのかな？
230:通りすがり
07/04/06 23:12:40
停止問題を解くことが出来るマシンを考えればずっと大きな数を作ることが出来る。
あるチューリング完全マシンをMachine[0],
Macihne[0]のn命令のプログラムで表現可能な最大の数をM[0](n)とすると、
M[0](n) ≒ BB(n)
Machine[0] の停止問題を解く命令をhalt[1],
Machine[0] に halt[1] の命令を追加したマシンを Machine[1],
Macihne[1]のn命令のプログラムで表現可能な最大の数をM[1](n)とすると、
M[1](n) は 前スレ >>863 の mm(n) を大きく超える。
Machine[a]のｎ命令のプログラムで表現可能な最大の数をM[a](n)
Machine[a] の停止問題を解く命令をhalt[a+1]
Machine[a] に halt[a+1] の命令を追加したマシンを M[a+1]
としてM[a]を定義することが出来る。
halt[a] を 「b<a となるすべてのマシン Machine[b] の停止問題を解く命令」としても同じであり、
この定義にすると、a を順序集合に拡張できるようになる。
M[ω](n), M[ω^ω](n), M[Γ_0](n) などが定義できる。
231:１３２人目の素数さん
07/04/08 14:42:10
>>230
> 前スレ >>863 の mm(n) を大きく超える
前スレ >>863 のプログラムが見えないので、どこかにアップしてもらえますか。
232:通りすがり
07/04/09 20:13:01
>>231
URLﾘﾝｸ(2ch-library.com)
>>230 は検証せずにイメージで書いちゃったけど、
> M[1](n) は 前スレ >>863 の mm(n) を大きく超える。
これは嘘でした。
233:１３２人目の素数さん
07/04/09 22:59:54
>>232
サンクス。念のため、魚拓で保存しておきました。
URLﾘﾝｸ(symy.jp)
234:１３２人目の素数さん
07/04/16 10:16:05
かなり改善された模様
235:１３２人目の素数さん
07/04/16 19:04:01
それって計算可能なの？
236:１３２人目の素数さん
07/04/16 20:12:35
チューリングマシンでは計算不可能なんじゃね
237:１３２人目の素数さん
07/04/16 21:43:33
Ackerman関数より急に増加するような関数は
たいてい計算不可能なんじゃないかな
238:１３２人目の素数さん
07/04/16 21:44:32
何言ってるんだ俺ｗ
239:１３２人目の素数さん
07/04/17 17:11:54
( ^ω^)
240:１３２人目の素数さん
07/04/23 22:12:22
数学は加減乗除くらいしか判らないんですが、物や人の歴史には非常に強い
興味があるので、このスレは10文字で云々って頃から見てました
プロジェクトX風ナレーションで、マジ泣きしたこともありました
で、ふと思ったんですが、現在20文字部門最強の
＞f(n):=nに階乗をn回
＞f^9!(9)
と、
グラハム数をグラハム数!回階乗
では、どちらが大きいんでしょうか？
表記のルールに反するので対象外だとは思いますが、私の知識だと「f(n)」
ってのが既に何なのか判らないので、比較ができません
どなたか教えて頂けませんでしょうか？
また、「グラハム数」の表記が認められた場合、どのような表記が最大になる
のでしょうか？
241:１３２人目の素数さん
07/04/24 05:02:59
２０文字部門最強よりグラハム数の方が大きいんじゃないか？
グラハム数！回階乗なんかしなくても。
242:１３２人目の素数さん
07/04/25 07:32:47
>>241
ありがとうございます
意外と小さいんですね
って、それだけグラハム数が大きいってことで、そんなのもミクロの世界に追いやる
ふぃっしゅ数が偉大だってことなんでしょうけど
243:１３２人目の素数さん
07/04/25 16:53:39
数に偉大も何も無いと思うけどなー。
あ、でも数を擬人化すればこそこんなバトル風になったのか。
244:１３２人目の素数さん
07/04/25 19:23:30
フィッシュ数たん( ;´Д`)ﾊｧﾊｧ
こうですか？ わかりません＞＜
245:１３２人目の素数さん
07/04/25 19:52:37
>>243
です
基本的な数学の概念自体判ってないので、自分なりに理解する為に
脳内で物語とかを展開しながらROMってます
何スレか前、RPG風にスレの流れを書きましたが、あんな感じです
ふぃっしゅ数は打たれても打たれても立ち上がってくる、ジャンプ系の
主人公って感じでしょうかね
戦隊組んだら、ふぃっしゅ数は間違いなく赤だと思います
246:１３２人目の素数さん
07/04/25 22:18:17
ふぃっしゅ数なんて力技で作った数なんかどうでも良い。
247:１３２人目の素数さん
07/04/26 07:57:00
いくら作ってもミクロなところを出られないてのが凄いな。
探索は限りないんだろうか。なんかの構造的なシフトでもどっかにあるんだろうか。
248:１３２人目の素数さん
07/04/27 21:00:38
誰か２０文字最強をチェーンとかタワーで評価して頂けないでしょうか。
249:１３２人目の素数さん
07/04/27 21:36:18
9999999999→999999999
か
9999→9999→9999→99999
か
999→999→999→999→9999
か
99→99→99→99→99→99→99
か
9→9→9→9→9→9→9→9→9→99
のどれかじゃないかと思うんですけど、>>240なので比較できません(;´Д`)
250:１３２人目の素数さん
07/04/27 21:43:26
→の定義が無いと自然数を定義したとは言えない
251:１３２人目の素数さん
07/04/27 22:51:41
>249
一番上以外は全部グラハム数より遥かにデカイ
当然のごとく一番下が最大だろう
252:１３２人目の素数さん
07/04/29 02:00:13
>>248
文字の規定はどうするんだ？
ある記号に意味をいくらこめても良いんじゃ意味ないし。
253:１３２人目の素数さん
07/04/29 06:35:28
チェーン表記の矢印を定義するには、タワー表記の矢印も定義しなきゃ
ならないんですね
数字2つなら「a→b=a^b」でいいけど、3つ以上になると定義の説明だけで
20文字超えそう
254:１３２人目の素数さん
07/05/02 22:33:26
>>248 の意味をだれも理解してないところが数学板クオリティー
255:１３２人目の素数さん
07/05/02 22:58:18
>>248
９↑↑↑(９！) ＜ 「２０文字最強」 ＜ ９↑↑↑(９！＋２) ＜ ２↑↑↑↑３ ＝ ２→３→４
256:１３２人目の素数さん
07/05/02 23:59:59
>>254
証明付けてやったろうかと思ったら思いのほかめんどかったし、
その間に別のレスがついたし。
まぁこの程度の比較してるだけなら証明なんて不要なんだろうと思ったし。
257:１３２人目の素数さん
07/05/03 07:38:11
URLﾘﾝｸ(www.geocities.co.jp)
20文字部門は f^9! と括弧なし
30文字部門は f^(99!) と括弧あり
な理由がわからん。
258:１３２人目の素数さん
07/05/03 20:08:43
F[ψ(Γ_(Ω+1))](グラハム数) < BB(120)
259:１３２人目の素数さん
07/05/04 23:20:50
>>254
理解してるだろう・・・。
260:１３２人目の素数さん
07/05/10 22:10:08
>>257
ただ単にn文字で大きな数では曖昧なため、
C++言語を使ったルールを考えてみました。
C++言語のnトークン(n語)で大きな数をつくるというものです。
int main();
がどれだけ大きな整数を返すか競います。
----------ルール-----------
int 型は無限長符号付整数とします。
数値（即値）は十進表記のみであらわしますが、
数値だけは例外として桁数をトークン数に数えます。
（コメントや空白はカウントしません）
以下のような、処理系に依存するコードはNGとします。
引数の評価順に依存するコード、
不定値参照、
sizeof 演算子、
ポインター <=> 0以外の整数値 のキャスト
など
プリプロセッサの使用、ライブラリの使用は不可
261:１３２人目の素数さん
07/05/10 22:12:08
// 10 word
int main(){
return 99;
}
// 20 word
int main(){
return 9<<(9<<(9<<99));
}
// 30 word
int main(){
int a = 99, b = a<<a;
while (b--)
a <<= a;
return a;
}
// 40 word
int main(){
int a = 9<<9, b, c = a;
while (b = a, c--)
while (b--)
a <<= a;
return a;
}
262:１３２人目の素数さん
07/05/10 22:12:53
// 50 word
int func(int a, int b){
return
a ?
b ? func( a-1, func(a, --b) )
: a
: ++b;
}
int main(){
return func(9,9);
}
263:１３２人目の素数さん
07/05/10 22:17:02
// 返す値: アッカーマン関数
// 定義域: a >= 0, b >= 0
// サイズ: 42
int Ackermann(int a, int b){
return
a ?
b ? Ackermann( a-1, Ackermann(a, --b) )
: Ackermann(--a, 1)
: ++b;
}
// 返す値: クヌースの矢印表記 a ^^...^^ b (^ がc個)
// 定義域: a >= 1, b >= 0, c >= 0
// サイズ: 44
int Knuth(int a, int b, int c){
return
c ?
b ? Knuth( a, Knuth(a, --b, c), c-1 )
: 1
: a * b;
}
264:１３２人目の素数さん
07/05/10 22:17:35
// 返す値: コンウェイのチェーン表記 p[0] → p[1] → ... → p[s-1]
// 定義域: s >= 1, p[i] >= 1
int Conway(int s, int *p){
int i = s, int *q = new int[s];
while (i--)
q[i] = p[i];
if (s == 1)
return p[0];
if (p[s-1] == 1)
return Conway(s-1, p);
if (s == 2){
q[1] --;
return b[0] * Conway(s, q);
}
if (p[s-2] == 1)
return Conway(s-2, p);
q[s-2] --;
q[s-2] = Conway(s, q);
q[s-1] --;
return Conway(s, q);
}
265:１３２人目の素数さん
07/05/11 22:48:13
H[Γ_0](99) のソース
URLﾘﾝｸ(2ch-library.com)
266:１３２人目の素数さん
07/05/16 20:59:14
>>190-203 を参考にして、
>>205 に定義されているΨ(ψの極限)を使って、
hardy[ψ(0, Ψ)](99) を返す関数を作ってみました。
URLﾘﾝｸ(2ch-library.com)
267:１３２人目の素数さん
07/05/16 21:08:19
>>266 のように、ある言語を用いて大きな可算順序数を作ることを考える。
n文字（またはn単語、nトークンなど） で表せる最大の可算順序数を
o(n) とした場合、この極限 lim o は可算なのだろうか？
可算だとすると、
帰納的定義では到達できないほど大きな可算順序数が存在することになる。
非可算（つまりΩ）になるとすると、
可算順序数の列で、極限が非加算になるものが存在することになる。
268:１３２人目の素数さん
07/05/16 21:28:35
ω_1のcofinalityはω_1だから、可算順序数の可算列ではω_1にはならないんじゃないか？
269:１３２人目の素数さん
07/05/16 22:08:40
cofinalityというのは知りませんが、
> 可算順序数の可算列ではω_1にはならないんじゃないか？
ということは、
帰納的定義では到達できない最小の順序数を☆_0とし、
☆_0と帰納的定義では到達できない最小の順序数を☆_1とし、
....
☆_n の極限を☆_ω とし、
....
☆_☆_...._☆_☆_0 を ★_0 とし、
....
とか定義できるのかな？
270:１３２人目の素数さん
07/05/17 09:11:32
cofinalityってのは共終数と言って、順序数論ではかなり
基本的な概念だから、順序数を使って急増加函数を作りたいなら
勉強したほうが良いよ。無理にとは言わないけどね。
n文字を用いて或る数を表す、とかいうときの文字数は
Peano算術なりZFCなりの論理式の文字数と考えれば良いだろう。
μxP(x)と表したときのPでも良いだろうし。
Pに量化記号が無制限に入っていいことにすると、
急増化函数の存在がZFCから独立、
なんてことが起こるから基礎論に詳しくないとどう考えていいか分からなくなるけど。
271:１３２人目の素数さん
07/05/17 23:48:47
>>270
わざわざどうも。
私は基礎論も順序数論も集合論も詳しくないので、先は長そう。
帰納的定義によりたどり着ける順序数は、
言語によらず同じで、
☆_0 も１個に定まると楽観的には思いますが、
いかがでしょうか。
H[☆_0](n) は計算不可能（アルゴリズム存在せず）なので、
結局BB(n)と実質同じになります。
●このスレで出た最大
順序数、基数、濃度: Ψ
可算順序数: ★_0
帰納的定義の可算順序数: ψ(Ψ)
関数: >>230
帰納的定義の関数: H[ψ(Ψ)](n)
272:１３２人目の素数さん
07/05/18 19:13:44
>>266
保存しておきました。
URLﾘﾝｸ(symy.jp)
273:１３２人目の素数さん
07/05/19 14:14:25
recursiveでない最小の順序数はω_1^CKという（Church-Kｌeene順序数）
274:１３２人目の素数さん
07/05/19 23:56:47
>>273
もう既に名前がついてるんですか。
>>202では、
ψ_α(0) を、濃度がω_αである最小の順序数としていますが、
ψ_α(0) = ☆_α としてもまったく同じように各順序数の収束列を定義でき、
>>203 や >>266 のプログラムもまったくかわらず、
H[ψ(Ψ)](n) の値もまったく同一になりますね。
（この場合、Ψ=★_0）
さらにψ_α(0)を小さく定義することもできそうです。
（つまり帰納的定義の範囲内）
こう考えると、
はじめは H[ψ(Ψ)](n) の定義には巨大な基数が現れるので、
H[Γ_0](n) に比べて革命的に大きくなっているように見えたんですが、
だんだんと普通の拡張に見えてきました。
プログラムも２倍程度に増えただけですし。
275:１３２人目の素数さん
07/06/17 15:05:45
あげ
276:１３２人目の素数さん
07/06/19 23:08:35
関数の大小の比べ方なんですが、以下のようなことを考えてみました。
任意の自然数cに対しある数nが存在しn<xならばf^c(x)<g(x)が成り立つならばgはfより本質的に大きい。
というアイディアはどうでしょうか。既出かもしれませんが。
277:１３２人目の素数さん
07/06/22 12:35:51
>>276
g = f^x(x) と定義すれば、gはfよりも本質的に大きくなるね。
通常の関数であれば十分に本質的に大きい、と言えるだろうけど、
たとえば>>230のような関数に対してこのような拡張をしたところで、
本質的に大きいとは言えないかも。
278:１３２人目の素数さん
07/06/25 22:27:46
URLﾘﾝｸ(web.mit.edu)
ここにある「C」は、「An Ordinal Notation」の段階で
>>202 の添字つきψと同じ順序数まで表せる模様。
さらに、
「A Stronger Ordinal Notation」
「Second Order Arithmetic」
「Beyond Second Order Arithmetic」
と続くので、相当巨大な順序数が作れそう。
279:276
07/06/26 22:59:19
>>277
２７６ですが、どうもこの方法は原始帰納関数？では上手く機能すると思うのですが、
それ以上となると駄目なような気がなんとなくしてきました。
280:１３２人目の素数さん
07/06/26 23:49:45
>>276
計算可能な関数に関しては、
Hardy Function を用いて、F[順序数](n) という形に近似して順序数の大小で比較。
Hardy Function を本質的に超える関数が出てくるまでは、
これで大小比較が可能。
（順序数が本質的に大きいかどうかという問題になる）
---例---
Knuthの上矢印 3(↑^n)3 ≒ F[ω](n)
n個のnからなるConwayのチェーン ≒ F[ω^2](n)
↑n (3,3,3) ≒ F[ω^3](n)
Ak(n, 3) = ≒ F[ω](n)
Ak を多変数に拡張、Ak(n個のn) ≒ F[ω^ω](n)
Ak を２重リストに拡張、Ak([n個のn], [n]) ≒ F[ω^ω^ω](n)
Ak を多重リストに拡張、Ak(n重リスト) ≒ F[ε_0](n)
ちなみに、g = f^x(x) とするのは、F[順序数](n) の順序数に1を加えるのと同じ効果。
----
計算不可能なものも含めた場合には、
ある程度小さなものは、
>>230 の形に近似して順序数の大小で比較すれば良いが、
順序数をマシンで生成させ、これを引数とするHALT[順序数] 命令にすると、
M[順序数](n) よりも大きくなるため、順序数での比較は不可になる。
281:たろう
07/06/27 23:00:18
>>260 のルールで作ってみました。
URLﾘﾝｸ(up.spawn.jp)
F[ω^3] までゆっくりで、一気に F[φ_ω(0)] まで飛んでます。
F[ω^4], F[ω^ω], F[ε_0] なども作ってみたけど、
F[φ_ω(0)] より大きくなってしまいました。
順序数を使う２個は >>278 の C を参考にしてます。
「An Ordinal Notation」より手前の段階のを多変数にしてます。
veblen関数を普通に多変数にしたものよりは効率がよさそうです。
（+ の定義まで含まれているのと、収束がちょっと簡単）
いずれは
「An Ordinal Notation」や「Beyond Second Order Arithmetic」、
「An Ordinal Notation」から「Beyond Second Order Arithmetic」を順序数回繰り返したもの
など、より大きなものを作る予定。
あと、>>280 にある、
アッカーマンの拡張で F[ε_0] やその先まで到達する方法をまとめました。
URLﾘﾝｸ(up.spawn.jp)
282:たろう
07/06/30 05:40:21
----BB以上の関数----
M[順序数](n) の関数を作るには、
>>233 の基本命令に
test ** という命令を加えればよい。
これは、ラベル ** へジャンプした場合に halt で停止する場合はポインタ位置を1にセット、
無限ループする場合はポインタ位置に0をセットする命令。
この命令は引数として順序数を取る。
ジャンプ先に、引数以上の test ** 命令が出現する場合には停止問題は解決できない為、
ジャンプ先で、halt より前に、引数以上の test ** 命令が出現する場合は halt と同じ動作をする。
引数の順序数の与え方は、
たとえばM[ω](n)を定義するマシンの場合には、
ポインタ位置から１が続く個数を数え、これを引数nとする。
M[C(a, b, c) の極限](n) を定義するマシンの場合は、 ...(Cは>>278のもの)
順序数を 0 , C ( ) の５個の文字で表し、
0 には 1 を、
, には 11 を、
C( には 111 を、
) には 1111 を、
割り振り、
文字の境目を 0 としてエンコードしたものを引数とすればよい。
たとえば、ポインタ位置から 111 0 1 0 11 0 1 0 11 0 1 0 1111 となっている場合は
引数は C(0,0,0) と解釈する。
※ C(a, b, c) は0とCのみでCの極限未満のすべての順序数を表現可能
283:１３２人目の素数さん
07/06/30 05:55:11
すべての帰納的順序数を引数に取れる test ** 命令は、
>>233 のようなマシンでは定義が非常に複雑になるが、
C++ のような高級言語なら出来そうである。
>>266 のように、ordinalを、0 から始めて再帰的に、
１個前の順序数を使って定義する
収束列を使って定義する
としていけばすべての帰納的順序数を表現できる。
これを引数にとるような test ** 命令を持つマシンでの
n命令での最大のステップ数が M[帰納的でない最小の順序数](n) である。
（>>269 でいう ☆_0）
さらに、☆_a をあらかじめ定義しておくことで、
M[★_0](n), M[☆_2](n) なども定義できる。
ただ、このようなルールはマシンを定義する段階で必要であるので、
すべての順序数を定義できるわけでなく、
いままで人間が到達出来ていない最小の順序数
のようなものに対してマシンを定義できない。
たとえば、M[Ω](n) なんかは、可算順序数がすべて表現可能な
方法が見つかってから始めて定義できる。...つまり定義できない。
284:１３２人目の素数さん
07/06/30 06:07:41
ということで、
>>280 の後半「順序数の比較は不可になる」というのは嘘で、
M[順序数](n) として大小比較が出来そう。
----
☆_0 の収束列を、
C++ n語で表現できる最大の帰納的順序数
とすれば、
F[☆_0](n) が定義できる。
「C++ n語で表現できる最大の帰納的順序数」を求めるアルゴリズムは存在しないため、
これは BB と同程度の大きさとなる。
F[帰納的順序数](n) はすべて計算可能であり、
すべての計算可能な関数は、F[ある帰納的順序数](n) で押さえられる。
M[0](n) ≒ F[☆_0](n) であり、
M[1](n) ≒ F[☆_1](n) であり、
おそらく、M[a](n) ≒ F[☆_a](n) といえる。
285:もやしっ子
07/07/05 03:42:16
こんにちは。見てます。何とか見てます。
さっぱりです。
何とかします。
286:１３２人目の素数さん
07/07/06 18:18:38
URLﾘﾝｸ(www.polytope.net)
ここに載ってるのとふぃっしゅ数だったらどっちがでかいのか？
表記法の説明（英語）
URLﾘﾝｸ(www.polytope.net)
287:たろう
07/07/06 21:49:47
ふぃっしゅ数の定義はこれ？
URLﾘﾝｸ(www.geocities.co.jp)
S変換がハーディー関数の順序数にωを足す位の変換。
つまり、F[a](n)にS変換を行うとF[a+ω](n)になる位。
SS変換はω^2を足すのと同等、
SSS変換はω^3を足すのと同等、
....
S^i変換はω^iを足すのと同等、
--------
(S^n変換)f(n) ≒ F[a+ω^ω](n)
最初の関数にアッカーマンを使っているが、
f(x) = x+1 としても大差なし。どちらもF[ω^ω](n)程度となる。
>>281の多変数＃と同程度。
288:たろう
07/07/06 21:53:01
>>286 のほうは、定義が複雑でよくわからないが、
Extended Operators の下の方の4変数の段階で F[ω^2](n) 程度。
289:たろう
07/07/06 22:14:29
URLﾘﾝｸ(www.geocities.co.jp)
こちらの >>10 にバージョン５の記述がありましたね。
m(2) がハーディー関数の順序数に1を加えるのと同等、
m(3)m(2) がハーディー関数の順序数にωを加えるのと同等、
m(4)m(3)m(2) がハーディー関数の順序数にω^2を加えるのと同等、
....
f5(n) ≒ F[ω^ω](n)
となり、古いバージョンとほぼ同じとなるようです。
290:１３２人目の素数さん
07/07/06 22:19:59
ふむう。だいぶ研究が進んでるようですね。
いよいよこのスレの終焉も近い？
291:たろう
07/07/06 22:41:10
あ、ちょっと解釈を間違ってたかもです。
>>289は取り消し。
292:たろう
07/07/06 22:49:37
ふぃっしゅ数バージョン５の大きさ（訂正）
m(2) がハーディー関数の順序数に1を加えるのと同等、
m(3)m(2) がハーディー関数の順序数にωを加えるのと同等、
m(4)m(3)m(2) がハーディー関数の順序数にω^ωを加えるのと同等、
m(5)m(4)m(3)m(2) がハーディー関数の順序数にω^ω^ωを加えるのと同等、
....
f5(n) ≒ F[ε_0](n)
293:１３２人目の素数さん
07/07/07 21:41:33
ﾌﾞｰﾝが沢山いるスレだな…
294:１３２人目の素数さん
07/07/10 09:20:52
てすと
295:１３２人目の素数さん
07/07/31 13:41:18
保守
296:１３２人目の素数さん
07/08/02 02:56:33
無限大が無限大にある、という言い方もできますが、この場合は
無限大を超えることになる。
無限大×∞
∞＾∞
∞＾∞＾∞ とかぎりなく増やせるということは、
さらに、上数があるということだろうか？
297:感覚的限界
07/08/02 16:38:09
>296
∞ = 1+1+1+…
として
2∞ = (1+1+1+…)+(1+1+1+…)
= 1+1+1+1+1+1+…
としてしまうと∞と変わらなくね？となるので
「1が無限個ある」はまだいいけど「1が2∞個ある」は禁止。
きちんと掛け算を定義しないといけなくてそれをやってるのが順序数。
で
「∞に＾∞を無限個つなげる」から先はどうすればいいんでしょうね。
298:１３２人目の素数さん
07/08/02 17:37:18
アレフ0とアレフ１じゃないのか？
299:１３２人目の素数さん
07/08/03 23:40:15
順序数のことじゃないのか？
∞ ==> ω
300:１３２人目の素数さん
07/08/04 17:29:01
とりあえず有志が整理しないとω?SS変換???てことになるぞ
301:１３２人目の素数さん
07/08/05 00:41:21
ωは「最小の超限順序数」だから
ω+1とか定義できるしなあ。
>>297の言いたいこととはちょっと噛み合ってないんじゃないかと思われ
302:１３２人目の素数さん
07/08/09 15:55:06
私のExploding Array Functionは私が数年前に開発した様々なアレイ記法の一般化された
フォームです、(直線的)のアレイ記法や、広げられて(次元)のアレイ記法や、いくつかの
変更があるtetrationalアレイ記法などのように。 元々、様々なアレイ記法には、いくつ
かの規則がありました--直線的のための5、広げる、私がtetrationalであっ、それでも、
今それを解決しようとして、3つの規則しかなくて、すべてのアレイの世話をするtetrati
onalアレイのずっとも先の7。
--------------------------------------------------------------------------------
どのように、それ、Started
数年間、私は数多く興味を持っています、数個のために名前を鋳造しさえするまで私の
「「不-ライオン」番号」ページを参照してください。 ある日(およそ20年前)、私は強国を
超えたオペレータ、tetrationなどのオペレータ、pentation、hexationなどについて議論し
たものを本(名前を覚えていない)に読み込みます。 これによって、私は次元スペース(私が
現在呼ぶ空間、最高の次元の、そして、trimensionalなquadramentionalなど)を超えた極端
な空間と同様により極端な数を調査したくなりました。 時間が経ったように、私はその本の
見られるオペレータにextentionを開発し始めました、私が拡張オペレータに言及するつもり
であるこれら。 その後、AckermannのFunctionやコンウェイのChained Arrow Notationなど
の知られている大きい数の機能を調べた後に、私はこれらのよく知られている機能と拡張オ
ペレータを比べることができました。 オペレータのはるかに凌がれたAckermannのFunctionを
広げて、実際にコンウェイのChained Arrowと比較することができました--詳細がないかどうか
M.ロブの大きい数のページでチェックしてください。 その後、私は拡張オペレータを広げる
タスクを引き受けました--私は、後で4つの番号、および次のextentionが5時までに拡張オペ
レータを定義することができると発見しました。 これは私のArray Notationの開発の始まり
です。
303:１３２人目の素数さん
07/08/09 19:59:48
機械翻訳かけるぐらいなら原文引用しろよ…
304:１３２人目の素数さん
07/08/11 22:17:30
>>302は自分じゃ日本語が話せないんじゃないの？
305:１３２人目の素数さん
07/08/12 00:40:16
なるほど。
>>302
You might wanna post it in English.
306:１３２人目の素数さん
07/08/23 20:28:14
俺用まとめ。
足し算a+bは1を足すのをb回繰り返す
掛け算a*bはaを足すのをb回繰り返す
階乗a^bはaかけるのをb回繰り返す
タワーa↑↑bはaをb乗するのをb回繰り返す
タワーa↑↑↑bはa↑↑bをb回繰り返す
タワーa↑^nbはa↑(n-1個)bをb回繰り返す
これを改良したのがコンウェイのチェーン表記
アッカーマン関数
原始帰納的でない帰納的関数
ack(0,n)=n+1
ack(1,n)=n+2
ack(2,n)=2*n+3
ack(k,n)はack(k-1,n)と階乗を使って表わせる。
以下、俺の理解
バード数
タワーと、グラハム数を使った関数を用いた数。
ふぃっしゅ数
バージョン1のS変換は↑^nのこと
その次のS変換(SS変換?)は↑の代わりにアッカーマン関数を使ったもの
それらの変換を使って定義した数
ビジービーバー関数
どんな計算可能な関数よりも増加率の大きい関数。
「じゃあ、俺今まで出た一番でかい関数+1ね。」っていうズルと一緒
ハーディ関数：ω(無限順序数のうち最小のもの)が計算可能でないのでズルに思える。
多分、S変換とバード数の回転だと、初期の値の振る舞いはバード数が勝つ(グラハム数を使っているため)が
基本的にタワーよりはアッカーマン関数のほうが増加率が大きいので
グラハム数を...回適用する程度の差は吸収されて、S変換を使った数のほうが大きくなるように感じる。
307:１３２人目の素数さん
07/08/23 22:33:19
あまたがわるそうなやつのまとめだな。
308:１３２人目の素数さん
07/08/23 23:29:33
とりあえずこのくらいの認識から初めて、ちょっとずつ改めまていけばおｋ
ぐらいには上手くまとまってる。
309:１３２人目の素数さん
07/08/24 01:01:07
>>306
おかしなところを指摘しておく。
＞タワーa↑↑bはaをb乗するのをb回繰り返す
この書き方だと、a↑↑b=((a^b)^b)^b…=a^(b^b)という意味にとれてしまう。
もしかしたら、「aの○乗というのをb回繰り返す」と言いたかったのかもしれないけど。
＞ack(k,n)はack(k-1,n)と階乗を使って表わせる。
ack(ｋ,n) = ack(ｋ-1,ack(ｋ,n-1))だから、階乗を使って表すことはできないだろう。
＞「じゃあ、俺今まで出た一番でかい関数+1ね。」っていうズルと一緒
ビジービーバー関数の値は他に依存せずに定義されているから、
そういう他に依存した定義をするズルとは違う。
ただ、「計算可能」でないと、他の「計算可能」でない関数と大小比較をするのも難しいし、
具体的な計算手順が分からなくて面白みに欠けるから、このスレではあまり深く扱われないのだと思う。
（ここでいう「計算可能」とは、簡単にいえば、与えられた引数から関数の値を計算するプログラムが書けるということ。）
＞ω(無限順序数のうち最小のもの)が計算可能でないのでズルに思える。
ここで”計算可能でない”と言ってるのは、単にωが「普通の数」ではないという意味だと思う。
ただ、そういう「普通でない数」を使っていても、各順序数に対して定まる関数は「計算可能」であるから、
（例えばH[ω](x)=2xだから、H[ω]は「計算可能」な関数）
ハーディ関数自体はズルではないと言える。
バード数とふぃっしゅ数についてはよく覚えてないので、指摘はしない。
310:たろう
07/08/24 07:18:44
バード数の定義はこれ？
URLﾘﾝｸ(www.geocities.co.jp)
X_1(n) ≒ F[ω^3+1](n)
X_a(n) ≒ F[ω^3+a](n)
X_n(n) ≒ F[ω^3+ω](n)
入れ子操作n回 ≒ [ω^3+ω+1](n)
n回回転チェーン↑n(3,3,3) ≒ F[ω^3](n) だから
ほとんど増えていないことに。
311:たろう
07/08/24 07:41:23
大きさのまとめ
Knuthの上矢印 3(↑^n)3 ≒ F[ω](n)
Ak(n, 3) ≒ F[ω](n)
n個のnからなるConwayのチェーン ≒ F[ω^2](n)
チェーンの回転 ↑n (3,3,3) ≒ F[ω^3](n)
バード数の定義の X_n(a) の入れ子操作n回 ≒ F[ω^3+ω+1](n)
5変数Ak ≒ F[ω^4](n)
多変数Ak Ak(n個のn) ≒ F[ω^ω](n)
Ak を２重リストに拡張、Ak([n個のn], [n]) ≒ F[ω^ω^ω](n)
ふぃっしゅ数バージョン５のf5(n) ≒ F[ε_0](n)
312:たろう
07/08/24 07:50:38
>>309
計算可能でない関数の比較も順序数を用いて出来る。
>>282 付近参照。
313:１３２人目の素数さん
07/08/24 22:17:39
>>309
>この書き方だと、a↑↑b=((a^b)^b)^b…=a^(b^b)という意味にとれてしまう
確かに。補足さんくす。
a^b^cはa^(b^c)だな。
^以降では、交換法則が不成立性なのはすぐわかるんだが、結合法則はどうやって示すんだろ
2+2+2=3+3が成り立つから2*3=3*2
2*2*2=3*3が成り立たないから2^3=3^2じゃない
ackについては、もう少し書くと
ack(3,n)=2^(n+3)-3
ack(4,n)=2^(2^n+3)-3
ack(5,n)=2^(2^(2^n+3))-3
↑細かくは間違っているかもしれんがふいんきをつかんでくれ
ack(k,n)とack(k-1,n)を再帰の定義の関係としてでなくて
ack(k,n)の一般項とack(k-1,n)の一般項の関係でみればいい。
つまり、ackは高階原始帰納的関数というわけ
hardy functionに関しては、n<ωの時はこうなるよな？
3(↑^n)3<ω
Ak(n,3)<ω
↑n(3,3,3)<ω
n>=ωの場合は、計算の仕方がわからん・・
>そういう他に依存した定義をするズルとは違う。
違わないと思う。
URLﾘﾝｸ(www.ice.nuie.nagoya-u.ac.jp)
314:１３２人目の素数さん
07/08/24 23:19:54
>>313
> ack(4,n)=2^(2^n+3)-3
> ack(5,n)=2^(2^(2^n+3))-3
これじゃ原始帰納だよ
315:１３２人目の素数さん
07/08/25 01:48:40
あまたがわるそうなやつがまたきた。
> ^以降では、交換法則が不成立性なのはすぐわかるんだが、結合法則はどうやって示すんだろ
(3^3)^3 ≠ 3^(3^3)
> ackについては、もう少し書くと
どこをたてよみ？
> hardy functionに関しては、n<ωの時はこうなるよな？
「hardy function に関しては」と書いているのに hardy function が出てこない不思議。
>> そういう他に依存した定義をするズルとは違う。
> 違わないと思う。
自分が理解できないからってズルか。
あたまがわるいふりをした釣り？
316:１３２人目の素数さん
07/08/25 04:16:19
>>313
ackとチェーン表記については、ack(m,n)=2→(n+3)→(m-2) - 3という関係式が成り立つようだ。
ただ、m=0を代入すると右辺の計算ができないからm>0とする。
（a→b→(-1) = a+b, a→b→0 = a*bとしておく）
どうやら、>>306では「階乗」という言葉を"！"以外の意味で使いたかったようだな。
hardy functionに対しては何を言いたいのか分からないので、
もう一度hardy functionのことを勉強してから書き直してほしい。
ビジービーバー関数みたいな定義をズルと感じるかどうかは、人によって違うかもしれない。
関数に対して具体的な計算手順を定めなければいけないと考えるなら、
ビジービーバーみたいな具体的な計算手順を与えない定義はズルだとも言える。
ただ、この場合は暗黙のうちに「計算可能」な関数のみを考えているということになる。
一方、関数というのはある引数に対してある値が定まりさえすればいいと考えるなら、
ビジービーバー関数もズルではないということになる。
いずれにしても、「今まで出た一番でかい関数+1」というのは状況によって異なる関数になってしまうから、
まともに定義しているとは言えず明らかなズルだと言える。
結局、客観的に見てズルかどうか判断するには、ルールや暗黙の了解が必要になる。
そういうものがあれば、それに反するものがズルだと客観的に判断できる。
現状では「計算可能」な関数に限るというルールも暗黙の了解もないから、
ビジービーバー関数がズルだと言っても単なる個人の意見でしかない。
ビジービーバー関数がズルだという主張も理解できなくはないけどな。
「今まで出た一番でかい関数+1」というのは他に依存した定義だから悪いというのなら、
他に依存しないように定義すればいい。他に依存しない定義をするためには、
あらゆる可能性をあらかじめ考えてその中で最大のものを選び出せばいい。
「あらゆる」といってしまうときりがないから、「ｎ文字以下のプログラム」とか制限をつければいい。
とやって行き着くところがビジービーバー関数だとも言えなくはないわけで。
317:１３２人目の素数さん
07/08/25 08:23:40
> いずれにしても、「今まで出た一番でかい関数+1」というのは状況によって異なる関数になってしまうから、
> まともに定義しているとは言えず明らかなズルだと言える。
単に+1するのに14文字も費やして非常に効率が悪いのでだれも見向きもしないけど、
14文字である関数を非常に大きく出来るならそれはそれで意味があると思う。
S変換なんかは関数を大きくする変換だしね。
計算可能じゃない関数がズルだとかいっていたらそこで進歩は止まるよ。
虚数なんかは数じゃないといって否定するようなもの。
実際ビジービーバー関数よりずっと大きな関数も出てきてるし。
318:１３２人目の素数さん
07/08/25 10:28:26
>>317
別に、計算可能じゃない関数がズルだと316で主張したいわけではない。
ビジービーバー関数に違和感を感じる人の気持ちも理解できなくはないというだけで。
個人的な考えとしては、計算可能な関数に限って大きいものを考えるのも、
計算不能な関数も含めて大きいものを考えるのも、どちらも意味あることだと思う。
実数の範囲のみで考えることも、複素数の範囲まで広げて考えることも、どちらも意味があるように。
319:１３２人目の素数さん
07/08/25 19:04:16
>>317 の下３行は >>316 宛じゃない。過剰反応。
320:１３２人目の素数さん
07/08/25 21:56:26
313は間違ってた。316さん補足どうも。
理解コストの高そうなのはスキップして前スレ一通り読んでみた。
俺の印象では計算不可能な巨大数だと、到達不能基数を除いてε数が強げ。
そんでωを表わすためのC言語の関数を考えてみた
big w(){return 1+w();} //bigは多倍長正数型(つか、値より停止性にしか意味ないような)
この関数の返す値(もちろん計算可能でない)をωとする
するとw()の多項式は、順序数ωの計算同様、右分配法則を満たさない
1+w()はw()に吸収されるからw()の値と同じ→1+ω=ωのアナロジー
n+w()はw()に吸収されるからw()の値と同じ→n+ω=ωのアナロジー
2*w()はw()に吸収されるからw()の値と同じ→2*ω=ωのアナロジー
n*w()はw()に吸収されるからw()の値と同じ→n*ω=ωのアナロジー
w()+1はw()で計算がとまる→ω+1≠1+ωのアナロジー。残りも同様
あと、ack3項版を作ってみた
1.ack(0,0,z)=z+1
2.ack(0,y,0)=ack(0,y-1,1)
3.ack(x,0,0)=ack(x-1,ack(x-1,1,0),0)
4.ack(x,0,z)=ack(x-1,z+1,0)
5.ack(0,y,z)=ack(0,y-1,ack(0,y,z-1))
6.ack(x,y,z)=ack(x-1,ack(x,y-1,z),ack(x-1,y,z))
☆ack(0,m,n)は2項のack(m,n)と一致する
停止性を満たしたまま1,2,5式を残せば☆を満たせる。
つまり、ackのn項化って色々やり方がある
多重帰納法の種類だけ、作れるんじゃなかろうか
321:１３２人目の素数さん
07/08/26 00:40:18
あまたがわるそうなやつがまたきた。
> 俺の印象では計算不可能な巨大数だと、到達不能基数を除いてε数が強げ。
計算可能という意味をまず理解したほうがいい。
> big w(){return 1+w();} //bigは多倍長正数型(つか、値より停止性にしか意味ないような)
> この関数の返す値(もちろん計算可能でない)をωとする
無限ループとなり値は返らない。
> あと、ack3項版を作ってみた
複雑なわりに大して大きくなってない。
3変数ならもっとずっと大きく出来る。
322:１３２人目の素数さん
07/08/28 12:09:42
>>320
ackやチェーン表記みたいな巨大関数の拡張案は過去に何度も出ているが、
その多くは元の関数にあった単純さを失ってる上にそれほど大きくないものになっている。
単純で巨大な計算可能関数としてはHardy関数があるし、
ただの拡張案で大きな関数を目指すことにはほとんど意味がないと思う。
あと、「ωはどんな自然数よりも大きい」とかの説明を聞くと、
順序数自体を巨大数として扱うのだと思ってしまう人がいるが、
順序数は単に巨大な自然数を作るための道具として使われてるだけのはず。
順序数から巨大関数を作るための手段の一つがHardy関数。
323:たろう
07/08/28 22:28:59
Hardy関数や >>282 のような関数は非常に強力であるが、
これだけだと、単に大きな順序数を考えることと同じになってしまう。
Hardy関数、順序数やチューリングマシンの概念を使わずに
シンプルに、もしくは新しい方法で巨大な関数を作ることは十分意味があると思う。
Hardy関数と比較することで大きさの評価も比較的簡単になったし。
今のところHardy関数やチューリングマシンを使わない最大は、
ふぃっしゅ数バージョン５ （F[ε_0] 相当の関数） であろうか。
----
ちなみに、
>>320 のack は F[ω+ω](n) 程度の大きさ。
以下のように定義すれば、よりシンプルで F[ω^2](n) 程度まで大きくなる。
（こんな簡単な定義でコンウェイのチェーンでn個のnを結んだものと同程度になってしまう）
1.ack(0,0,z)=z+1
2.ack(x+1,0,z)=ack(x,z,z)
3.ack(x,y+1,0)=ack(x,y,1)
4.ack(x,y+1,z+1)=ack(x,y,ack(x,y+1,z))
※x, y, z は非負整数
多変数や多重リストへの拡張は >>281 の up2950.txt 参照。
324:１３２人目の素数さん
07/08/28 22:32:01
数学板でこのスレが一番おもしろいな
325:１３２人目の素数さん
07/08/29 09:39:08
あげときます
326:１３２人目の素数さん
07/09/03 23:41:17
★１つ目の関数
A(n)では非負のnは1以下。パラメータの階層と、最上階層のパラメータの数はともに1。
A(0)=2 （初期値）
A(1)=A(0)^A(0)^A(0)=2^2=4
(=2↑↑2)
★２つ目の関数
この4が次のパラメータの階層と、最上階層のパラメータの数になる。すなわち、
A(n_1_1(n_1_2(n_1_3(n_1_4))),n_2_1(n_2_2(n_2_3(n_2_4))),n_3_1(n_3_2(n_3_3(n_3_4))),n_4_1(n_4_2(n_4_3(n_4_4))))
３つ目の関数に移行するためには、(5^(4*4)-1≒1.5^11)回の計算を経なければならない。
A(0(0(0(0))),0(0(0(0))),0(0(0(0))),0(0(0(0))))=A(1)=4
A(0(0(0(0))),0(0(0(0))),0(0(0(0))),0(0(0(1))))=4↑↑↑↑4=4→4→4
A(0(0(0(0))),0(0(0(0))),0(0(0(0))),0(0(0(2))))=(4→4→4)↑↑＜4→4→4個＞↑↑(4→4→4)
=(4→4→4)→(4→4→4)→(4→4→4)
A(0(0(0(0))),0(0(0(0))),0(0(0(0))),0(0(0(3))))=[(4→4→4)→(4→4→4)→(4→4→4)]→[(4→4→4)→(4→4→4)→(4→4→4)]→[(4→4→4)→(4→4→4)→(4→4→4)]=あ
A(0(0(0(0))),0(0(0(0))),0(0(0(0))),0(0(0(4))))=あ→あ→あ
A(0(0(0(0))),0(0(0(0))),0(0(0(0))),0(0(1(0))))=(あ→あ→あ)→(あ→あ→あ)→(あ→あ→あ)=い
A(0(0(0(0))),0(0(0(0))),0(0(0(0))),0(0(1(1))))=い→い→い
A(0(0(0(0))),0(0(0(0))),0(0(0(0))),0(0(1(2))))=(い→い→い)→(い→い→い)→(い→い→い)
★３つ目の関数
２つ目の関数の最後、
A(4(4(4(4))),4(4(4(4))),4(4(4(4))),4(4(4(4))))
はすでにグラハム数ですら無に等しいほどの巨大数となっている。仮にこれを「う」とする。
３つ目の関数は「う」の階層を持ち、最上階層の数が「う」のパラメータを持つことになる。
４つ目の関数に移行するには「(う+1)^(う*う)-1」回の計算を行わなければ成らない。
★64番目の関数
「ふぃっしゅ数」を軽く超えているものと予想される。
327:１３２人目の素数さん
07/09/04 02:32:05
>>326
どのくらい大きいのかはよく分からないけど、なんだか昔の
スレッドに戻ったみたいでほのぼのした。
328:326
07/09/04 04:14:04
とはいっても、基本形がすべて
○→○→○
だから、イマイチ増加率が大きくないことに気づく。
ただ、関数を１つ上げるために必要な項の増加率が膨大だから、どちらが大きくなるか。
語弊を招くことを承知で極論すれば、
「ある等差数列の1無量大数項目と、ある等比数列の百項目のどちらが大きいか」
と同じ話だ。
329:１３２人目の素数さん
07/09/04 10:01:57
>>326
定義を誤解しているかもしれないが、思ったことを書いておく。
パラメータの数が多い割には、その多さが活かされていないと思う。
f(x)=x→x→xとすると、「う」というのは、f^{5^(4*4)-1}(4)と表される。
（f^n(x)は、xにfをn回適用した数とする）
n番目の関数でパラメータに最大値を代入したときの値をg(n)と表すと、
g(1)=4, g(n+1)=f^{(g(n)+1)^(g(n)*g(n))-1}(g(n))という漸化式でg(n)を表すことができる。
g(n)の大きさを見積もるためにHardy関数を用いると、
f(x)≒F[ω], g(n+1)≒f^{g(n)}(g(n))なので、g(n)≒F[ω+2](n)程度の大きさということになる。
過去ログによると、ふぃっしゅ関数ver.1はF[ω^2*63]程度の大きさということなので、
残念ながら326の関数ではふぃっしゅ数ver.1にも及ばない。
定義を解釈するときに、A(0(0(0(0))),0(0(0(0))),0(0(0(0))),4(4(4(4))))=☆として、
A(0(0(0(0))),0(0(0(0))),0(0(0(1))),0(0(0(0))))=☆→☆→☆のように計算するのだと解釈したが、
この解釈がもし間違っていたら指摘してほしい。
330:326
07/09/04 14:24:56
>>329
はい、その通り。返す言葉もございません。
私も未明の書き込みの時点でふぃっしゅ数に遠く及ばないだろうと感じていた。
もともとこの式は、
・高校生でも理解できる関数（↑までは容易に理解できると思われるので）
・パラメータを爆発的に増やすことで「それなりに」大きな数を作ることを試みる
を満たそうと考えたのもので、これはその最も原始的なものという扱いです。
グラハム数やふぃっしゅ数とどちらが大きいかもまったく検証してなかった。ごめんなさい。
関数自体の増加率もパラメータの数もさらに増やすことは容易なので、
修正すればもう少し大きな数ができるかもしれない。
ふぃっしゅ数に勝てるかはわからんが、パラメータにも前項の式を代入できるようにすればあるいは…
331:331
07/09/04 18:44:15
3/3=1
332:１３２人目の素数さん
07/09/04 21:54:36
x→x→x→x よりも小さいんじゃ意味ねえ。
333:326
07/09/05 03:09:54
ある項は、その前の項Akを(((AkのAk回乗数繰り返し)回乗数繰り返し)…(AkのAk回乗数繰り返し)…)回乗数を繰り返す。
つまり、ある項A_k+1はその前の項までAkを用いて、
A_k+1 = Ak^Ak^…(Ak↑↑Ak…(Ak↑↑Ak 回)…Ak↑↑Ak 回)…^Ak^Ak
A_k+1 = Ak^Ak^…(Ak↑↑↑Ak 回)…^Ak^Ak = Ak↑↑↑↑Ak = Ak→Ak→4
ある関数のパラメータは、その前の関数の最後の項の数Ｃだけ最上階層パラメータをもつ。
各最上階層パラメータはそれぞれＣだけ２次パラメータを持ち、さらにその２次パラメータはそれぞれＣだけ３次パラメータを持つ。
パラメータの階層はＣある。
すべてのパラメータmはm(i1,i2,i3,…,in)(1≦n≦C)と表記される。ここでi1,i2…は最上階層、次の階層…の値。
各パラメータには順序があり、i1が小さいもの、その中でi2が小さいもの、その中でi3が小さいもの、…から計算される。
たとえばC=3のとき、
A(あ(い(う,え,お),か(き,く,け),こ(さ,し,す)),せ(そ(た,ち,つ),て(と,な,に),ぬ(ね,の,は)),ひ(ふ(へ,ほ,ま),み(む,め,も),や(ゆ,よ,ら)))
とパラメータがおかれ、「ら」が最大値となったとき「よ」が1つ加算され、
「ら～せ」がすべてそれぞれ最大値となった時「す」が1つ加算され、となる。
また、あ→ら にかけて上位→下位のパラメータと定義する。
すべてのパラメータがそれぞれ最大値をとったとき、次の関数に移行する。
各パラメータは1からB(l)の値をとる。
ここで、あるパラメータの値が1つ下位のパラメータの最大値B(l-1)に達した時の、項の値をB(l)とする。
このとき、1つ上位のパラメータに移行するには、
B(l+1) = A_(k+B(l))
A_(k+B(l+1)) = A_(k+A_(k+B(l))) = A_(k+(Ak→Ak→4)→B(l)→2)
A_(k+B(l+1)) = (Ak→Ak→4)→((Ak→Ak→4)→B(l)→2)→2 (B(l)<Ak)
次の関数に移行するには…
やめた。326よりは確実に大きくなっているが、これだけややこしい説明してもグラハム数には及ばない。
高校生にも簡単に理解できて、かつグラハム数を超える数は作れないのか…
ちなみに高校生っていうのは、理屈の上ではタワー表記を使わずに説明できること（便宜上使ったが）
334:１３２人目の素数さん
07/09/05 05:20:32
>>333
＞高校生にも簡単に理解できて、かつグラハム数を超える数
>>323の3変数アッカーマン関数で、ack(1,1,100)とするだけでグラハム数を超えると思う。
ack(1,0,x) = ack(x,x)=2→(x+3)→(x-2) - 3だから大雑把に見てack(1,0,x)≒3→3→xで、
ack(1,1,x)はack(1,0,x)をx回繰り返すのと大体同じくらいになるので、
3→3→xを4に64回適用したグラハム数よりack(1,1,100)の方が大きくなるはず。
左の方の引数を増やせば、もっと大きい数を作ることもできる。
そもそも、パラメータを増やすとごちゃごちゃしてくるのでかえって分かりにくくなってしまう。
あと、パラメータに最大値があるというのも、あまり大きくならない原因の一つだと思う。
それから、パラメータに階層構造があるのに、それが活かされていない。
たとえば、326の2つ目の関数では、括弧を取り除いて16個のパラメータを並べても同じ関数になる。
巨大数作りではよくあることだが、数を爆発的に大きくするための要点があって、
その要点をうまく抑えれば単純な定義でも非常に巨大な数が作れる。
逆に、その要点を外すとどんなに複雑な定義をしてもたいして大きくならない。
それがはっきり分かる一例としては、>>323の3変数アッカーマン関数がある。
たった3変数で、たった4つの定義式しかないのに、一番左の引数を大きくすれば
チェーン表記を伸ばすのと同程度の速さで増大していく。
335:326
07/09/05 06:09:38
>>334
詳しい解説サンクス。
私も326を書き込む前に3変数アッカーマン関数を見て驚いた。
これは単純ながら強力だなあと感心した。
（じゃあ複雑化しただけで使い道のない関数作ってないでそれ使えよという突っ込みはなしで）
変数に関数自体を格納してしまうのが賢いとは分かっていながら、同じ手法使っても面白くないし。
読む気も失せる333だが、これは326を改良したものである。
どちらも結局、増加率には乗数しか使っていない。
パラメータにもなんら関数は格納していないし（順番に1ずつ増えていくだけ）、
ひどく原始的な手法で巨大数を作ろうという試みだ。
恐れ多くもこれでグラハム数を超えようとは呆れたものだ。
いまさらだが結局、乗数だけに頼っていては限界があるという愚例になったと思う。
（さらにまどろっこしい説明を加え続ければｘ→ｘ→ｘ→ｘを説明できないこともないが、無益なのでやめ）
336:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/05 21:24:49
>>323
なるほど。ふぃっしゅ数バージョン５の意味付けをしていただき
ありがとうございます。
>>311
こうやって整然と比較できるのが、Hardy関数の威力ですね。
せっかくなので、これまでのふぃっしゅ数について
URLﾘﾝｸ(www.geocities.co.jp)
ここの531、544を参考にして大きさを評価すると、
ふぃっしゅ数バージョン1のSS変換n回：F[ω^2+1](n)
ふぃっしゅ数バージョン2のSS変換n回：F[ω^3](n)
ふぃっしゅ数バージョン3のs(n)：F[ω^ω](n)
といった感じになりましょうか。
ちなみに、
URLﾘﾝｸ(www.geocities.co.jp)
ここの115に出てくるSnakeは、どの程度の大きさになりますか？
>>323では、F[ω^2]程度の関数をシンプルに表記していますが、
F[ω^ω]程度、あるいはF[ε_0] 程度の関数を出来るだけシンプルに
表記するにはどうすればいいか？といった問題設定もできそうですね。
なにをもってシンプルとするかは主観ですが…。
337:たろう
07/09/05 22:39:13
>>336
Snake の定義の３つ目の式を、
Snake([a<1>,･･･,a<n>],x)
=Snake([a<1>,･･･,a<n>-1],Snake([a<1>,･･･,a<n-1>,1],x))
と解釈し、
Snake([1],x) = x+1
とした場合は、
Snake([1がn個], n) ≒ F[ω^ω](n)
338:たろう
07/09/05 23:06:50
「なにをもってシンプルか」という解のひとつが、
>>260 でしょう。
>>281 でアップしたものをもう一度アップしておきます。
URLﾘﾝｸ(1rg.org)
ついでに、定義自体に順序数を使わない大きな関数です。
概念的には順序数＋Hardy関数ですが、
順序数を知らなくても、頑張れば理解できるかも。
URLﾘﾝｸ(1rg.org)
339:１３２人目の素数さん
07/09/06 01:36:03
>>338
保存しておきます
URLﾘﾝｸ(symy.jp)
URLﾘﾝｸ(symy.jp)
340:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/06 23:12:12
>>338
難しいですね…。
「概念的には順序数＋Hardy関数」とのことなので、
Hardy で F[ω^2], F[ω^ω], F[ε_0] に相当する
大きさの H[A] を作ると、Aの値はどうなりますか？
341:たろう
07/09/07 20:42:22
>>340
H[((((0)))0)] ≒ F[ω^2](n)
H[(((0)0)0)] ≒ F[ω^ω](n)
H[((0)00)] ≒ F[ε_0](n)
H[(((0))00)] ≒ F[η_0](n)
H[((0)000)] ≒ F[Γ_0](n) = F[ψ(0)](n)
H[((0)(0)00)] ≒ F[Γ_Γ_...Γ_0](n) = F[ψ(Ω)](n)
H[(((0))000)] ≒ F[ψ(Ω^2)](n)
H[((0)0000)] ≒ F[ψ(Ω^3)](n)
H[((0)00000)] ≒ F[ψ(Ω^4)](n)
H[((0)00.....n個.....00)](n) ≒ F[ψ(Ω^ω)](n)
342:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/08 02:43:26
それでは、感覚をつかむために H[((((0)))0)] ≒ F[ω^2](n) から計算してみます。
まずは、>>338の定義をコピーします。
Ｎ:非負整数 とする (0, 1, 2, .....)
■集合Ｔ
○定義
0 ( ) の３つの文字からなる文字列の集合で、以下の２つの条件を満たす最小のもの
"0" はＴの元である
Ｔの元を１個以上有限個繋げて () でくくったものはＴの元である
演算子 + で文字列の連結を表す
"(0)" + "0" = "(0)0"
○意味
葉が0の多進木
0と多変数の関数funcで生成できる数 と対応する
"(000)" => (0,0,0) => func(0, 0, 0)
"((0)0(0)((0)0))" => ((0),0,(0),((0),0)) => func( func(0), 0, func(0), func( func(0), 0 ) )
343:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/08 02:44:25
■Seq : Ｔ×Ｎ => Ｔ
○定義
Seq は Ｔ×Ｎ から Ｔ への関数であり以下を満たす
s = "0" の時
Seq(s, i) は未定義
s = "(" + □ + a + ")" の形の時
Seq(s, i) = a
s = "(" + Ｘ + B + □ + a + ")" の形の時
Seq(s, 0) = "(" + a + ")"
Seq(s, i+1) = "(" + Ｘ + Seq(B, i+1) + Seq(s, i) + □ + ")"
ただし、
s, a, b, B ∈ Ｔ ただし、B ≠ 0
□ : 0個以上の0を有限個繋げたもの
Ｘ : 0個以上のＴの元を有限個繋げたもの
i ∈ Ｎ
344:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/08 02:45:00
■H[a] : Ｎ => Ｎ
○定義
a ∈ Ｔ とし、H[a] で Ｎ => Ｎ の関数を表し以下を満たす
H[0](n) = n+1
H[A](n) = H[Seq(A, n)](n+1)
ただし、
A ∈ Ｔ, A ≠ 0
345:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/08 02:45:37
【略号】
(1) = ((0))
(2) = (((0)))
(3) = ((((0))))
(i,j) = (i)(i)(i)…j+1個…(i)
0^i = 000...i個…0
【Seq の計算】
Seq((0), i) = 0
Seq((n), i) = (n-1)
Seq(((n+1,1)), i+1) = (Seq((n+1), i+1) + Seq(((n+1,1)), i))
= ((n) + Seq(((n+1,1)), i))
= ((n, i) + Seq(((n+1,1)), 0))
= ((n, i) + (n+1))
Seq(((n+1,m+2)), i+1) = ((n+1,m) + Seq((n+1), i+1) + Seq(((n+1,1)), i))
= ((n+1,m) + (n, i) + (n+1))
Seq(((n+1) + 0), i+1) = (Seq((n+1), i+1) + Seq(((n+1) + 0), i))
= ((n) + Seq(((n+1) + 0), i))
= ((n, i) + Seq(((n+1) + 0), 0))
= ((n, i) + 0)
Seq(((n+1, m+2) + 0), i+1) = ((n+1,m) + Seq((n+1), i+1) + Seq(((n+1) + 0), i))
= ((n+1,m) + (n, i) + 0)
Seq((0, m+2) + 0, i+1) = ((0,m) + Seq((0), i+1) + Seq(((0, m+2) + 0), i))
= ((0,m) + 0 + Seq(((0, m+2) + 0), i))
= ((0,m) + 0^(i+2))
346:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/08 02:47:25
【H[((((0)))0)] の計算】
H[((((0)))0)](n) = H[((2)0)](n) = H[Seq(((2)0), n)](n+1)
= H[((1, n-1) + 0)](n+1)
= H[Seq(((1, n-1) + 0), n+1)](n+2)
= H[((1, n-3) + (0, n) + 0)](n+2)
= H[Seq(((1, n-3) + (0, n) + 0), n+2)](n+3)
= H[((1, n-3) + (0, n-2) + 0^(n+3))](n+3)
= H[Seq(((1, n-3) + (0, n-2) + 0^(n+3)), n+3)](n+4)
Seq((X + (0, n-2) + 0^(n+3)), n+3)
= (X + (0, n-3) + Seq((0), n+3) + Seq((X + (0, n-2) + 0^(n+3)), n+2) + 0^(n+2))
= (X + (0, n-3) + 0 + Seq((X + (0, n-2) + 0^(n+3)), n+2) + 0^(n+2))
普通に計算したのでは、歯が立たないかな。
また、改めて出直してきます。
347:たろう
07/09/08 07:44:37
簡単に解説します。
URLﾘﾝｸ(web.mit.edu)
順序数の生成にはこれを参考にしたC0を使っています。
（Cの一番小さいものを多変数にしたもの）
veblen関数の多変数に比べて変数１個分小さいですが、
その分、加算の定義が不要となります。
-----------C0-----------
●定義
C0(□, a) = a+1
C0(Ｘ, b+1, a) = lim { 初項 a / ２項目以降 C0(Ｘ, b, １個前の項) }
C0(Ｘ, b+1, 0, □, a) = lim { 初項 a / ２項目以降 C0(Ｘ, b, １個前の項, □, a) }
C0(Ｘ, B, □, a) = lim C0(Ｘ, B_n, □, a)
ただし、
a, b : 順序数
A, B : 極限順序数 （A_n, B_n : 収束列）
□ : 0個以上の0
Ｘ : 0個以上の0以上の順序数
●大きさ
C0(a) = a+1
C0(a,0) = ω^a
C0(1,0,0) = ε_0
C0(2,0,0) = η_0
C0(1,0,0,0) = Γ_0
C0(1,0,0,0) = Γ_Γ_...Γ_0
C0(2,0,0,0) = ψ(Ω^2)
C0(1,0,0,0,0) = ψ(Ω^3)
lim C0(1,0,0,....n個.....,0,0) = ψ(Ω^ω)
348:たろう
07/09/08 07:53:24
集合ＴはC0で生成する順序数と対応しています。
"0" => 0
"(0)" => 1
"((0))" => 2
"(((0)))" => 3
"((0)0)" => C0(1,0) => ω
"(((0))0)" => C0(2,0) => ω^2
"((0)00)" => C0(C0(0),0,0) => ε_0
"((0)000)" => C0(C0(0),0,0,0,0) => Γ_0
Seq(s, i) は、順序数が極限の場合はその収束列を返し、
順序数がa+1の形の場合はaを返します。
H[a] はaが後続順序数と極限順序数の時の定義をくっつけた
ハーディー関数になります。
349:１３２人目の素数さん
07/09/08 07:59:56
>>341 間違ってました。訂正。
H[((((0))0)0)] = H[ω^ω^2] ≒ F[ω^2](n)
H[((((0)0)0)0)] = H[ω^ω^ω] ≒ F[ω^ω](n)
350:たろう
07/09/08 08:06:53
>>348
× "((0)000)" => C0(C0(0),0,0,0,0) => Γ_0
○ "((0)000)" => C0(C0(0),0,0,0) => Γ_0
ミスが多くてすいません。
Seq の定義は、定義式の数を減らすため、>>347 の定義と微妙に変えてあります。
351:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/09 01:17:49
>>350
> Seq の定義は、定義式の数を減らすため、>>347 の定義と微妙に変えてあります。
C0(Ｘ, B, □, a) = lim { 初項 a / 2項目以降 C0(X, B_n, 1個前の項, □) }
といった感じですか？
どうしてこれが順序数の収束列になるのかがまだよく分かりませんが、
もう少しよく考えてみます。
352:１３２人目の素数さん
07/09/09 22:45:32
>>336
F_ω^ω(x)はx重帰納的関数に相当するとたいていのHardy functionに
関する論文には書いてあるようです。x重帰納的関数は詳しくは知りませんが
たしか前スレにそれらしいものが載ってたと思います。
このようなこともあってF_ε_0(x)に相当する関数を順序数なしで定義するのは
不可能だと思っていたのですがふぃっしゅ数ver5がそれに到達している
というのは本当でしょうか？
Snakeやver5はまだ理解していないので理解できたらそれらとHardyの比較も
やりたいと思っています。
353:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/10 01:39:12
>>352
ふぃっしゅ数ver5がF[ε_0](n)に達しているかどうかは、
よく分かりません。>>292では、達しているとされていますが、
その計算内容が十分にまだ分かっていません。
「F[ω^ω](x)はx重帰納的関数に相当する」ということから
「F[ε_0](x)に相当する関数を順序数なしで定義するのは不可能」
という帰結になるのはなぜでしょうか？「x重帰納的関数よりも
大きな関数は順序数なしでは定義できない」というようなことでも
あるのでしょうか？
「定義できない」ということが、もしも「TMで構成できない」と
いうことになればF[ε_0](x)がBB級の大きさになる可能性もありますが、
そんなことはないですよね。Hardy関数が計算可能である、という
ことに関しては特に問題ないようですし。
逆に、F[ε_0](x)等のHardy関数をTMで構成できるのであれば、
それはつまり帰納的に定義できるという意味だと感じますが、
甘いでしょうか。
Provably recursive という言葉も出てきましたが、そのあたりの
言葉との関係でしょうか…。
354:１３２人目の素数さん
07/09/10 17:28:44
ふぃっしゅ氏キテター
>>352
よく考えたら順序数と対応付けられる集合とかリストとかを
しらみつぶしに禁止するつもりですか？
Peano Arithmeticの中では任意のm(x)を構成することが
不可能ってことになるんじゃないでしょうか。
355:ルート41
07/09/10 18:59:48
新参者です。最近このスレを知った物で。
僕が前から考えていた巨大数の表記方法を失礼ながら書かせてもらいます。
Ａ～・Ｂという表記をするんですが、（～・で一つの記号です）定義として
Ａ～・1＝Ａ
Ａ～・2＝Ａ＾Ａ
Ａ～・3＝Ａ↑↑Ａ
Ａ～・4＝Ａ→→Ａ
としています。つまり、～・の後の数字が一つ増えるごとに→→と同じこと
前の記号に行うという事です。
次にＡ～・～・Ｂ＝Ａ～・（Ａ～・Ｂ）と定義します。
次にａｂｃｄの自然数において
ｎ＝ａ～・ｂ＞（ａ＾ｂ）～・（ｃ＾ｄ）＞ｂ＞ｄ＞ｃ＞ａ
が成り立つ時のｎの最小数を◎と表示します。
～・だとふた文字に見えるので♪を代用します。
◎♪♪♪♪♪♪♪♪◎という表記は10文字以内では大きい表示になるんでしょうか？
356:１３２人目の素数さん
07/09/10 20:08:54
定義を含め10文字にしなきゃいかんがな。
357:ルート41
07/09/10 20:19:23
>>355一番大切な事書くの忘れてました。
Ａ～・Ｂの表記のＢは何種類目の記号が使われたかを表しています。
Ｂ＝100なら100種類目の記号という意味です。巨大数を表す場合、
なんらかの記号を使って標記すので、最終的にはその記号の数を数える
のが最も大きな数になるという考えから～・を考案したのです。
ただこのままだと、ほとんど反則なので＞＞355では一番解りやすい
→→の法則で次の記号を定義しました。（もともとＡ～・Ｂは絶対
に表記出来ない数がある事の証明で作ったので、Ｂ＝100なら100種類
の記号を必ず使います） 説明下手ですいません。
あと途中の式ですが、これは
ａｂｃｄの自然数において
ｎ＝ａ→→ｂ＞（ａ＾ｂ）→→（ｃ＾ｄ）＞ｂ＞ｄ＞ｃ＞ａ
が成り立つ時のｎは少なくとも3→→1025より大きい数のとき
であるの応用で作りました（ｎの最小値がいくらは、僕にわ
解らないです。誰か計算できるひといませんかね）
358:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/10 20:48:34
ちなみに、>>338 のプログラムでは、F[ε_0](n)を超える
F[φ_ω(0)](n)やF[ψ(Ω^(Ω+ω))](n)がいとも簡単にコーディング
されていますが、このプログラムを理解できる人はいますか？
おそらく、基本的には>>347のアイデアを使っているのだと
思います。私としては、順序数の収束列をこのように多重帰納
関数の様な形で定義できる、ということが驚きで、いまだ理解に
至っていないのですが…。
URLﾘﾝｸ(web.mit.edu)
こちらのページを見ても、C(Ｘ, B, □, a)を導く一般式、のような
ものは書かれていないように見えますし。やはり、なぜ>>347の
式で順序数の収束列を定義できるか、という点については解説
していただかないと、私だけではなく皆さん理解できないのでは
ないでしょうか？
359:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/10 20:59:32
ふぃっしゅ数の大きさについては、
URLﾘﾝｸ(www.geocities.co.jp)
ここの58で、m(3)がF(x,y,z)=F(x-1,F(x,y-1,z),F(x,y-1,z)) で
あらわされました。この関数が真の三重帰納か、それとも実は
二重帰納か、という議論があったとは思いますが、いずれにしても、
m(n)は良くて多重帰納、もしかすると二重帰納になる気がします。
F[ε_0](n)になるというのは、落ち着いて考えると過大評価しすぎ
なような…。
また、m(3)が三重帰納であれば、s(n)はm(3)で生成される程度の
関数ですから、それよりも小さく、二重帰納程度です。
360:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/10 21:00:03
そうすると、チェーンはs(2)程度、チェーン回転、バードはs(3)程度
であることが分かっているので、いずれも二重帰納で、
m(n)が多重帰納であるとすれば、
Knuthの上矢印 3(↑^n)3 ≒ F[ω](n)
Ak(n, 3) ≒ F[ω](n)
ふぃっしゅ数バージョン1のSS変換：F[ω^2](n)
n個のnからなるConwayのチェーン ≒ F[ω^2](n)
ふぃっしゅ数バージョン2のSS変換：F[ω^2](n)
チェーンの回転 ↑n (3,3,3) ≒ F[ω^2](n)
バード数の定義の X_n(a) の入れ子操作n回 ≒ F[ω^2](n)
ふぃっしゅ数バージョン3のs(n)変換：F[ω^2](n)
ふぃっしゅ数バージョン５のm(3) ≒ F[ω^3](n)
真の三重帰納関数 ≒ F[ω^3](n)
例: A(x+1,y+1,z+1) = A(x,A(x+1,y,A(x+1,y+1,z)),A(x+1,y+1,z)))
真の四重帰納関数 ≒ F[ω^4](n)
例: A(w+1,x+1,y+1,z+1)=
A(w,A(w+1,x,A(w+1,x+1,y,A(w+1,x+1,y+1,z)),A(w+1,x+1,y+1,z)),A(w+1,x+1,y,A(w+1,x+1,y+1,z)),A(w+1,x+1,y+1,z))
真のn重帰納関数 ≒ F[ω^ω](n)
ふぃっしゅ数バージョン５のf5(n) ≒ F[ω^ω](n)
こんな感じになるのではないでしょうか。
361:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/10 21:01:03
もし、m(n)が二重帰納だよ、ということになれば、>>360で
真の○重帰納関数以外は、すべてF[ω^2](n)でした、という話に
なると思います。
>>311が正しいのか、それとも本当は>>360のような感じなのか。
そして、それはHardy関数を正確に計算することではっきりする
ものなのか。
Hardy で関数の大きさが整理できるといっても、正確に計算
しようとするとけっこう大変ですね。
362:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/10 21:50:11
さてさて、順序数の議論は高度でなかなかついていけずにいますが、
議論の雰囲気を読むと、Hardy + 順序数による巨大数の定義は、
canonical sequence の取り方が１つに保証されないε_0以上の
世界は、関数が１つに定まるかどうか不明という点で、きっちりと
定義された関数、あるいは数の仲間入りをさせていいかどうかと
いう疑問がまだ残っています。
そんなこんなで色々と昔を思い出していると、やはり多重帰納は
強力なので、なんとかして多重帰納を本質的に強める方法はないか、
と考えてしまうわけですが…。
URLﾘﾝｸ(www.geocities.co.jp)
ここの184によって、n重帰納関数 A_n(a_n,...,a_1) を定義する。
ただし、A_1(x)=f(x)、g(x)=A_x(a_x,...,a_1)とすることで、
関数 f(x) から 関数 g(x) への写像が定義される。
この写像は、f(x)=x+1という関数をF[ω^ω]クラスに持って行く
だけの力を持った写像である。
この時に、生成された多重帰納関数に対してこの写像の適用を
繰り返すとどうなるか。
363:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/10 21:51:37
>>362
(1) F[ω^ω] のまま変わらない
(2) F[ω^(ω+1)], F[ω^(ω+2)], ... F[ω^(ω*2)]
(3) F[ω^(ω*2)], F[ω^(ω*3)], ... F[ω^(ω^2)]
(4) F[ω^(ω^2)], F[ω^(ω^3)], ... F[ω^ω^ω]
(5) F[ω^ω], F[ω^ω^ω)], ... F[ε_0]
良くて(3)あたりだと思うのですが…どうでしょう。
この写像をM2変換としたふぃっしゅ数V5を考えたところで、
F[ε_0] までは到底到達しない…のでしょうね。本質的に強める
ためには、更なる工夫が必要かな。
364:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/10 23:29:14
>>362
> ただし、A_1(x)=f(x)、g(x)=A_x(a_x,...,a_1)とすることで、
ただし、A_1(x)=f(x)、g(x)=A_x(x,x,...,x)とすることで、
でした。
365:１３２人目の素数さん
07/09/11 06:44:31
>>353
すいません、書き方がまずかったです。
Hardy Functionはもちろん計算可能ですのでもちろんF[ε_0](x)はBB以下になります。
単にPAではProvably recursiveでない最小のものということですね。
過去スレに（一般的な？）多重帰納関数の例がでてきたときに順序数なしでは
これが最強だと思っていたのでF[ε_0](x)レベルのものは無理なんじゃないかと
勝手に思っていたので、ふぃっしゅ関数ver5がこれに至っているということに懐疑的に
なっていました。
しかし、ふぃっしゅ関数ver5がF[ω^ω](x)（＝H[ω^ω^ω](x)）に至っているというだけ
でも個人的にはすごいことだと思います。
>>362
＞ε_0以上の世界は、関数が１つに定まるかどうか不明
URLﾘﾝｸ(www.geocities.co.jp)
ここの>>655に定義の例が書かれています。
366:366
07/09/11 19:36:39
√(36)=6
367:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/11 20:53:22
URLﾘﾝｸ(www.geocities.co.jp)
このスレッドを読み直しているところですが、ふぃっしゅ数バージョン５
(F5)は多重帰納関数以上、ということでどうやら良さそうです。
まず、58の式はm(3)1回で生成されるs(1)に相当するm(2)がアッカーマン
であることを示している式です。それは当たり前のことで、
>>359のようにm(n)が二重帰納ということにはならないわけですが、
そのあたりで本人が錯誤をしていました。
m(n)の威力はm(3)からではなくm(4)からはじまりますが、
m(4)の計算をした63を見ただけでは、まだ2重帰納か多重帰納かは
よく分からない。
368:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/11 20:54:41
そこでまず、3重帰納の定義は、76,155,182をまとめて
3重帰納関数
f(x+1,y+1,z+1) = f(x,f(x+1,y,f(x+1,y+1,z)),f(x+1,y+1,z)))
が3重帰納である所以は、
f(x+1,y+1,z+1) が 3-term でそのなかに現われる f は
f(x,*,*), f(x+1,y,*), f(x+1,y+1,z) という形であり、
ただし、f(0,y,z) はこの定義で 2-term の形で定義される。
ということです。ここで、f(x,*,*), f(x+1,y,*), f(x+1,y+1,z) とは
(1) f(x,*,*) の * に f(x+1,y,*) を入れる
→ f(x,f(x+1,y,*),f(x+1,y,*))
(2) この式の * に f(x+1,y+1,z) を入れる
→ f(x,f(x+1,y,f(x+1,y+1,z)),f(x+1,y+1,z)))
という意味です。
369:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/11 20:59:50
これがなぜ、どの2重帰納よりも大きい3重帰納となるか。
それは、157に書かれている通り、
f(x,*,*), f(x+1,y,*), f(x+1,y+1,z) からxを落とすと
f(y,*), f(y+1,z) 、すなわち f(y, f(y+1,z)) の2重帰納が出てくる。
つまり、f(x,y,z) は、xを1つ増加させる毎に、y,zに関する
2重帰納をしている。したがって、2重帰納を有限回(n回)施して
得られるどんな2重帰納関数よりも、x>nの時点で大きくなるが
ために、3重帰納関数はいかなる2重帰納関数よりも大きくなります。
これは、アッカーマン関数がいかなる原始帰納関数よりも大きい
ことの説明と同じで、アッカーマン関数が原始帰納関数を枚挙
するがごとく、3重帰納関数が2重帰納関数を「枚挙している」
ということです。
Hardy 関数では、2重帰納の操作 ω^2 を枚挙することで、
ω^2, ω^2+ω^2, ω^2+ω^2+ω^2, ..., ω^3
の収束列が得られる、ということに相当するのでしょう。
370:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/11 21:03:54
さて、ここで多重帰納の本質を理解する必要があります。
そこで、あらためて自分が書いた 146-147 を読み直してみると、
どうやらそんなに間違ったことを書いてないです。
s(2)が2重帰納である、というところまでは良しとして
(F5のs(n)はF3のs(n-1)に相当する)、この説明の中でキーと
なるのは、「s(3)が2重帰納の操作を荒い意味で枚挙する」
という表現です。
s(3)の定義は
s(3)f(x)=(s(2)^x)f(x)
となりますが、
s2(n,x)=(s(2)^n)f(x)
と書いた時に、s(2)は2重帰納の操作をあらわしているので、
2重帰帰納をm回施して得られるどんな2重帰納関数よりも、
n>mの時点で大きくなります。このように、s2(x,x)は
2重帰納を枚挙する3重帰納となります。
したがって、s(3)は3重帰納の操作となります。
そうすると、s(n)は同様にn重帰納となります。
いやはや、皆様（分かる人には）分かっていたことを、
ようやくもって本人が理解できた、というところでしょうか。
371:ふぃっしゅっしゅ ◆/T2GtW187g
07/09/11 21:06:02
>>367->>369の考察により、>>360は撤回します。
>>311の前半にふぃっしゅ数Fを加えて
Knuthの上矢印 3(↑^n)3 ≒ F[ω](n)
Ak(n, 3) ≒ F[ω](n)
n個のnからなるConwayのチェーン ≒ F[ω^2](n)
F5のm(2)n回 ≒ F5のs(1)n回 ≒ F[ω^2](n)
チェーンの回転 ↑n (3,3,3) ≒ F[ω^3](n)
F5のs(2)n回 ≒ F3のs(1)n回 ≒ F1,F2のS変換n回 ≒ F[ω^3](n)
バード数の定義の X_n(a) の入れ子操作n回 ≒ F[ω^3+ω+1](n)
F5のs(3)n回 ≒ F3のs(2)n回 ≒ F2のSS変換n回 ≒ F[ω^4](n)
5変数Ak ≒ F[ω^4](n)
多変数Ak Ak(n個のn) ≒ F[ω^ω](n)
F5のs(n) ≒ F3のs(n) ≒ F[ω^ω](n)
F5のm(4) = F5のm(3)n回 ≒ F[ω^ω](n)
ここまでは理解できました。