07/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
07/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:１３２人目の素数さん
07/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:１３２人目の素数さん
07/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:１３２人目の素数さん
07/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:１３２人目の素数さん
07/01/09 07:37:32
訂正
F[3](ω)への収束列はω, ω^2, ω^ω^2, ω^ω^ω^2, …です。
おそらく、β≧ω＾2ならば2＾β=ω^βだと思います。
122:１３２人目の素数さん
07/01/09 12:32:09
今年に入ってから久々に盛り上がってますね
自分は全くの門外漢なので応援しつつ
スレの成り行きを見守らせてもらいます
123:１３２人目の素数さん
07/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:１３２人目の素数さん
07/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:１３２人目の素数さん
07/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:１３２人目の素数さん
07/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]))を考えると非常に大きい順序数ができます。
127:１３２人目の素数さん
07/01/10 20:07:02
式の展開を自動でやってくれるプログラム誰か作って。
128:菅_理人@kmath1107BBS ◆.ffFfff1uU
07/01/10 20:13:12
>>127
マスマティカ
129:１３２人目の素数さん
07/01/10 22:16:40
>>128
>>126の式なんかもOKなの？
あとフリーなのが良い…
130:１３２人目の素数さん
07/01/11 06:33:04
>>125-126についての説明。
どの定義式もφ(…,[α,β],[0,γ])=という形をしていますが、
α,β,γに対して0 or 1,後続,極限の3通りを考えなければならないので式が27種類もできてしまいます。
(Γ_0=φ([2,1])の定義式は数えない)
うまくまとめれば式を12種類にまで減らせますが、それだとどの式を適用するか多少分かりづらくなります。
「φ(…,[α,β])≠βのとき」とかいうのは、例えばω^ε_0=ε_0で
左辺と右辺に別々の収束列を定義してしまうのを避けるためです。
右辺では1, ω, ω^ω, ω^ω^ω, …となりますが、
左辺ではω, ω^ω, ω^ω^ω, ω^ω^ω^ω, …と一つずれてしまいます。
もっとも、順序数は巨大数の計算のための道具に過ぎないと考えて
ω^ε_0≠ε_0としてしまっても、巨大数の計算をすることは可能です。
つまり、ω^ε_0やε_0は単なる収束列を表す記号に過ぎないという考えをとるわけです。
すると、収束列の異なる順序数は「別のもの」であるとみなせるわけです。
ω^ε_0=ε_0という性質は、関数の増加度を見積もるときに使えば十分なわけです。
>>126の最後の順序数でH[α](2)の計算をしたとすると、順序数の減り方は
φ([φ([1,1]),1])=φ([ε_0,1])→φ([ω^ω,1])→φ([ω^2,1])→φ([ω*2,1])→φ([ω+2,1])→
φ([ω+1,φ([ω+1,1])])→φ([ω+1,φ([ω,φ([ω,1])])])→φ([ω+1,φ([ω,φ([2,1])])])→
φ([ω+1,φ([ω,φ([1,φ([1,1])])])])=φ([ω+1,φ([ω,φ([1,ε_0])])])→
φ([ω+1,φ([ω,φ([1,ω^ω])])])→φ([ω+1,φ([ω,φ([1,ω^2])])])→
φ([ω+1,φ([ω,φ([1,ω*2])])])→φ([ω+1,φ([ω,φ([1,ω+2])])])→
φ([ω+1,φ([ω,φ([1,ω+1],[0,φ([1,ω+1],[0,φ([1,ω+1])])])])])→
φ([ω+1,φ([ω,φ([1,ω+1],[0,φ([1,ω+1],[0,φ([1,ω],[0,φ([1,ω],[0,φ([1,ω])])])])])])])→
φ([ω+1,φ([ω,φ([1,ω+1],[0,φ([1,ω+1],[0,φ([1,ω],[0,φ([1,ω],[0,φ([1,2])])])])])])])
=φ([ω+1,φ([ω,φ([1,ω+1],[0,φ([1,ω+1],[0,φ([1,ω],[0,φ([1,ω],[0,η_0])])])])])])→
…となり、入れ子構造がすごいことになるのが分かります。
131:１３２人目の素数さん
07/01/11 08:10:44
ω^ε_0やε_0は単なる収束列を表す記号だという考え方について。
Hardy Functionに順序数を入れるときは、極限順序数は収束列のx番目の項に置き換えるわけです。
ならば、Hardy Functionを使う分には極限順序数と収束列は一対一に対応するものとみなせます。
では、1+ω=ω≠ω+1のような、順序数に対する等式は何を意味するのでしょうか。
これは、Hardy Functionに入れたときの関数の増加度を表しています。
F[1+ω](x)=F[1+x](x), F[ω](x)=F[x](x), F[ω+1](x)=F[ω]^x(x)という三つの関数を考えたとき、
F[ω](x)＜F[1+ω](x)＜F[ω](x+1)となるので、この二つの関数の増加度はほぼ同じです。
一方、F[ω](x)とF[ω+1](x)では明らかに増加度が違います。
なので、急激に増加する関数を作りたいときは、順序数の大きさをちゃんと考えなければいけません。
でも、順序数の大きさが分からなくても計算することだけならできます。
順序数を使った関数の計算法を理解したいだけなら、
「極限順序数と収束列が一対一に対応する」という不正確な理解でも十分です。
132:１３２人目の素数さん
07/01/12 00:31:42
以前の定義は間違っているところがあったので、書き直しました。
順序数を知らない人は「極限順序数」を「数列」と読み替え、
limは無視して「左辺の記号＝右辺の数列」だと思えば理解できると思います。
α=lim φ_nと書いたとき、αは極限順序数、α_n=φ_n
βが極限順序数のとき
α+β=lim α+β_n
φの定義(Veblen関数の拡張)
φ(…,[α,0],…)=φ(…,…)
φ()=1
φ([0,α+1])=lim φ_n
ただしφ_0=0,φ_(n+1)=φ_n+φ([0,α])
φ(…,[α+1,1],[0,β+1])=lim φ_n
ただしφ_0=φ(…,[α+1,1],[0,β])+1,φ_(n+1)=φ(…,[α,φ_n])
φ(…,[α+1,β+1])=lim φ_n
ただしφ_0=0,φ_(n+1)=φ(…,[α+1,β],[α,φ_n])
β≠0のとき
φ(…,[α,β+1],[0,γ+1])=lim φ_n
ただしφ_0=φ(…,[α,β+1],[0,γ])+1,φ_(n+1)=φ(…,[α,β],[0,φ_n])
αが極限順序数のとき
φ(…,[α,1],[0,β+1])=lim φ(…,[α_n,1],[0,φ(…,[α,1],[0,β])+1])
φ(…,[α,β+1])=lim φ(…,[α,β],[α_n,1])
βが極限順序数のとき
φ(…,[α,β])=lim φ(…,[α,β_n])
φ(…,[α,β],[0,γ+1])=lim φ(…,[α,β_n],[0,φ(…,[α,β],[0,γ])+1])
Fの定義(Hardy function)
F[0](x)=x+1
F[α+1](x)=F[α]^x(x)
αが極限順序数のとき
F[α](x)=F[α_x](x)
巨大関数の定義
f(x)=F[φ_x](x) ただしφ_0=0,φ_(n+1)=φ([φ_n,1]))
133:１３２人目の素数さん
07/01/12 09:17:41
>>132
小さい値について計算してみると、こうなります。
f(0)=F[0](0)=1
f(1)=F[φ([0,1])](1)=F[1](1)=F[0](1)=2
f(2)=F[φ([φ([0,1]),1])](2)=F[φ([φ([0,1]),0],[2,1])](2)=F[φ([2,1])](2)=F[φ([2,0],[1,φ([2,0],[1,0])])](2)
=F[φ([1,φ()])](2)=F[φ([1,1])](2)=F[φ([1,0],[0,φ([1,0],[0,0])])](2)=F[φ([0,φ()])](2)=F[φ([0,1])](2)
=F[2](2)=F[1]F[1](2)=F[1]F[0]F[0](2)=F[1](4)=F[0]F[0]F[0]F[0](4)=8
この関数はH[Γ_0]よりもずっと大きい関数なので、このスレで今まで出てきた関数の中では
ナゴヤ関数とBBを除くどの関数よりも急激に増加するはずです。
BBは計算可能などの関数よりも大きいので、当然この関数よりも大きいです。
ナゴヤ関数は、順序数にHardy functionを適用するとどの位大きくなるか見積もらないと比較できません。
リスト構造で比較してみると、ナゴヤ関数Ver.1は”自然数”個の変数を使っているのに対し、
この関数では[α,β]を「α番目の要素がβ」という意味で解釈しているので、
ある意味では”順序数”個の変数を使っていることになります。
見た目はただの2重リストですが、要素が順序数なので自然数を要素とする2重リストよりは
はるかに複雑な構造となります。
>>116では"Veblen関数を多変数に拡張してもF[ε0](ω)には足元にも及ばない"と書いてありますが、
F[ε0]はあくまでも「自然数のリスト構造」を変数とする関数より大きいだけで、
「順序数のリスト構造」となるとそうは言い切れないと思います。
134:１３２人目の素数さん
07/01/12 09:56:15
>>133
考察乙です
135:１３２人目の素数さん
07/01/12 23:28:37
Hardy functionを順序数に適用したらどうなるかを>>120の定義を用いて計算してみると、
どうやらF[α](β)≒φ_α(β)となりそうです。α＜ω*2の場合しか確かめてませんが。
少なくとも、F[ω+n](φ_[ω+n](α))=φ_[ω+n-1](φ_[ω+n](α)*2)という式が成り立ちます。
Veblen関数は、実はかなり巨大な順序数を作り出せる関数のようです。
この推測に基づいてナゴヤ関数と>>132の関数を比較すると、
L[α,β](ω)≒φ([2,1],[1,α],[0,β])ということになるようです。
(左辺はナゴヤ関数、右辺は>>132の拡張Veblen関数)
もし、L[a_n, …, a_0](ω)≒φ([n,a_n],…,[0,a_0])という関係が成り立つのなら、
ナゴヤ関数Ver.1より>>132の関数の方が大きいということになります。
でも、ナゴヤ関数Ver.2はずっと巨大なものになるそうなので、
>>132を上回るような関数になることを期待しています。
それと、上の記述はかなり推測が入っているので、間違いがあるかもしれません。
136:１３２人目の素数さん
07/01/13 13:20:48
>>132の定義式で、
β≠0のとき
φ(…,[α,β+1],[0,γ+1])=lim φ_n
ただしφ_0=φ(…,[α,β+1],[0,γ])+1,φ_(n+1)=φ(…,[α,β],[0,φ_n])
αが極限順序数のとき
φ(…,[α,1],[0,β+1])=lim φ(…,[α_n,1],[0,φ(…,[α,1],[0,β])+1])
の式を、
φ(…,[α+1,β+1],[0,γ+1])=lim φ_n
ただしφ_0=φ(…,[α+1,β+1],[0,γ])+1,φ_(n+1)=φ(…,[α+1,β],[α,φ_n])
αが極限順序数のとき
φ(…,[α,β+1],[0,γ+1])=lim φ(…,[α,β],[α_n,φ(…,[α,β+1],[0,γ])+1])
に訂正します。
137:１３２人目の素数さん
07/01/15 19:28:51
今のところ、BB以外の計算可能な巨大数については
ナゴヤ関数なるものが最強候補なわけですな
138:１３２人目の素数さん
07/01/16 09:38:57
>>137
そういうことですね。ただ、ナゴヤ関数は>>117のように定義が怪しいところもあるようです。
その点では、>>132、>>136の関数はちゃんと定義できていてナゴヤ関数Ver.1より大きいようなので
現時点では最強なのかもしれません。自分で言っても説得力はありませんが。
>>132、>>136の関数の定義がよく分からない人がいたら聞いてください。
139:１３２人目の素数さん
07/01/17 11:11:45
拡張Veblen関数による順序数の大小関係
α=φ(…,[β,γ],…)のとき、γをαのβ成分と呼ぶ。
γ=φ(…)のとき、α＜γ,β＜γならばα+β＜γ
β=φ(…)のとき、α＜βならばα+β=β、α≧βならばα+β＞α,β
α=φ(…),β=φ(…)のとき、αのγ成分＞βのγ成分 となるγが存在して、
δ＜γならばα＞βのδ成分 であり、ε＞γならば αのε成分=βのε成分 が成り立つとき、α＞β
α=φ(…,[β,γ]),γ=φ(…)のとき、δ＜βならば αのδ成分=0 であり、
ε＞βならば αのε成分≦γのε成分 であり、
ζ＞β、αのζ成分＜γのζ成分 となるζが存在するならばα=γ
上記のような大小関係が成り立つように、>>132、>>136で収束列を定めてあります。
ただし、上の式での=は順序数として等しいだけで、>>132、>>136で定義される収束列は異なるので、
>>132、>>136の関数の計算で=とすることはできません。
また、上の大小関係を見ると0以外の自然数が出てきていませんが、
0より大きくφ()よりも小さい数が存在しないとしても矛盾は生じないので
φ()を1とみなせることが分かります。
140:１３２人目の素数さん
07/01/18 04:54:26
巨大数と直接は関係ない話ですが、>>139の大小関係に以下の基本的な定義を加えれば、
0に+,φを次々に適用して得られる数の集合(仮にΦと呼ぶ)に対し順序関係がきちんと定まるはずです。
(α+β)+γ=α+(β+γ)
α+0=0+α=αをみたす元0が存在する
任意のα,βに対しα＞β,α=β,α＜βのうちいずれか一つのみが成り立つ
α＜β,β＜γならばα＜γ
また、厳密に+やφという演算を定義すれば、
+:Φ×Φ→Φ; (α,β)├→α+β
E={e:Φ→Φ; α├→e(α)|Ψ⊂Φ, α∈Ψでなければe(α)=0}として
φ:E→Φ; e├→φ(…,[α,e(α)],…,[β,e(β)],…) ただしα,β∈Ψ, α＞β
ただし、eはαに対しα成分を与える写像です。
こんな説明は理解しなくても>>132、>>136の関数は理解できるはずですが、
この関数について詳しく知りたい人がいたときのために書いておきます。
141:１３２人目の素数さん
07/01/18 09:40:19
>>140
一つ抜けてました。Ψは要素が有限個の集合です。
0＜φ()というのは、以下のように導けます。
0≧φ()とすると>>139の4行目より0+φ()＞0
ところが0+φ()=φ()であるからφ()＞0となり矛盾する よって0＜φ()
142:もやしっ子
07/01/19 05:31:56
どうも。のろのろと勉強しております。
F[λ](x)=F[Λ(x)](x) （λは極限順序数、Λ(x)はλに収束する基本列）
ここのくだりが長いことわからなかったのですが、要するに
例えばλ=ωの場合であれば Λ(x)=x なので
F[ω](x)=F[x](x) のようになるんでしょうか。
λ=ω*2の場合は Λ(x)=ω+x より
F[ω*2](x)=F[ω+x](x)
これはここからどう展開するのか分からんです。(そもそも合っているのか)
143:もやしっ子
07/01/19 20:20:30
ちなみに英語サイトに、ωは最小の極限順序数である、という
記述があったのでそういう理解をしております。荒っぽいでしょうか。
＞The first limit ordinal is ω.
144:１３２人目の素数さん
07/01/19 20:32:21
「最小の超限順序数」ではなくて？
145:１３２人目の素数さん
07/01/19 20:39:19
>>143
ただ、0を極限順序数とする人も多いよ
146:１３２人目の素数さん
07/01/19 20:40:05
limit ordinalってのはsuccessor ordinalじゃないというのが定義だったような。
だとしたらそれで良いはずですけど。
別にどういう用語を使っても良いだろうけど「超限」ってのは
transfiniteの訳語として使うことが一般的じゃないのかな。
しかし超限ってどういう意味ですか、と聞かれるとちょっと困りますね
147:もやしっ子
07/01/19 20:44:51
wikipediaに「極限順序数(limit ordinal)」という記載があったので
英語で検索したところ、
URLﾘﾝｸ(mathworld.wolfram.com)
ここにそういう記載がありました。
超限順序数を英語で何と呼ぶのかが見つかっておりません。
wikipediaではωは最小の超限順序数であるとも書いてありますね。
謎は置いておいて、目先の疑問に触れてみた、ということでひとつ。
148:もやしっ子
07/01/19 20:50:00
＞自然数でない序数を transfinite ordinal という。
との記述を発見。でも序数って「first」「second」みたいなもんですか？
むう…
149:もやしっ子
07/01/19 20:53:30
さらに怪しい翻訳。謎。
正の整数の超限順序数はωによって指定されます。
150:もやしっ子
07/01/19 21:07:50
性懲りもなく。
＞超限数は，超限順序数と超限基数に分かれる
ここでの運用を勝手に推測すると、ωは極限順序数であるし、また
超限順序数でもあるから混乱を避けるため呼称を統一した、とか？
あるいは、極限順序数の定義でいかないと基本列のカラクリが使えないとか。
妄想です。
151:１３２人目の素数さん
07/01/19 21:27:10
>>149
それは、「正の超限順序数をωと表すとする」って約すのが正解。
「傾きをvとおく」みたいなものだ。
152:１３２人目の素数さん
07/01/19 22:25:27
日本語版wikipediaには、
＞有限整列集合から定義される順序数を有限順序数といい、
＞そうでないものを超限順序数と呼ぶ。
という記述がありますが、超限というのはおそらく、
0,1,2,3,･･･として定義できる"限"界を"超"えた数という意味ではないでしょうか。
>>142
[ ]の中の数を一つ減らしてx回繰り返します。
xに具体的な数字を入れてやってみると、
F[ω*2](1)=F[ω+1](1)=F[ω](1)=…
F[ω*2](2)=F[ω+2](2)=F[ω+1](F[ω+1](2))=…
F[ω*2](3)=F[ω+3](3)=F[ω+2](F[ω+2](F[ω+2](3)))=…
F[ω*2](4)=F[ω+4](4)=F[ω+3](F[ω+3](F[ω+3](F[ω+3](4))))=…
ということになります。x=2の場合でもう少し先までやってみると、
F[ω+1](F[ω+1](2))=F[ω+1](F[ω](F[ω](2)))=F[ω+1](F[ω](F[2](2)))
=…=F[ω+1](F[ω](8))=F[ω+1](F[8](8))=…
となります。( )の中身が計算されてからωを置き換えるので、
F[ω]が入れ子になると外側ほど大きな数で置き換えられることになります。
153:１３２人目の素数さん
07/01/19 22:55:31
個人的なイメージとしては、
超限が先にあるものじゃなくて、
ω以上の順序数を「超限順序数」と呼ぶみたいな印象が
154:もやしっ子
07/01/20 00:06:57
>>151
訂正ありがとうございます。0を極限順序数とするというのは、
主張の問題であって算術的には問題ないのでしょうか。
＞0=α+1となるような順序数αは存在していませんので、0は極限順序数
こんなん拾いました。ということは0も順序数ということでいいですか。
>>152
とりあえず僕は「極限順序数」と呼んでおくことにします。
さて上の続きを書いてみますが、
F[ω*2](2)=F[ω+2](2)=F[ω+1](F[ω+1](2))=F[ω+1](F[ω+1](F[ω](2)))
=F[ω+1](F[ω+1](F[2](2)))
ここでF[2](2)としていいのか分かりませんが続けます。
F[2](2)=F[1]^2(2)
=F[F[1](2)](2)
=F[F[0]^2(2)](2)
=F[F[F[0](2)](2)](2)
=F[F[3](2)](2) …
元の式に戻ると、 F[ω+1](F[ω+1](F[F[3](2)](2)))
あれ、またヘマやったかな？
155:もやしっ子
07/01/20 01:17:13
研究室に巨大数スレ6のログを丸ごとぶち込みました。
暇潰しにどうぞ。
156:１３２人目の素数さん
07/01/20 01:58:59
>>154
0はもちろん順序数だよ。
というか、自然数は全部、順序数。
順序数は自然数の概念を無限の領域まで拡張したみたいな感じのもの
157:もやしっ子
07/01/20 02:05:18
>>156
解説ありがとうございます。0が自然数に含まれるのか分からなかったのです。
前スレをちんたら読んでおります。
魚スキー氏曰く、Hardy functionについて、
H[ω](x)=H[x](x)=2x+1
H[ω+n](x)=H[ω](x+n)=2x+2n+1
H[2ω](x)=H[ω+x](x)=4x+1
…… H[nω+ω](x)=H[nω+x](x)=H[nω](2x) なので
H[nω](x)=2^n*x+1
……ω^2の基本列は{ω, 2ω, 3ω, ...}
H[ω^2](x)=H[ωx](x)=2^x*x+1
H[ω^2+ω](x)=H[ω^2](2x)=2^(2x)*2x+1
H[ω^2+2ω](x)=H[ω^2+ω+x](x)=2^(4x)*4x+1
H[ω^2+nω](x)=2^(2^n*x)*2^n*x+1
H[2ω^2](x)=H[ω^2+ωx](x)=2^(2^x*x)*2^x*x+1
との結果を得ているようで、僕はヘボなのでプロセスが分かりません。
H[x](x)=2x+1 となる理由すら。うはは
158:もやしっ子
07/01/20 02:18:56
うーん、自分ナゴヤ関数の咀嚼に挑んでたのか…
全く記憶にない(笑)
159:１３２人目の素数さん
07/01/20 02:26:30
ω＝α+1になる順序数αは存在しないから極限順序数。
ってことでいいのだろうか。
160:１３２人目の素数さん
07/01/20 02:59:11
>>154
F[ω+1](F[ω+1](2))=F[ω+1](F[ω+1](F[ω](2)))ではなく、
F[ω+1](F[ω+1](2))=F[ω+1](F[ω](F[ω](2)))です。
それから、F[α+1](x)=F[α]^x(x)というのは[ ]の中に入れ子にするのではなく、
( )の中に入れ子にします。そうしないと[ ]の中の数が減らないので
永久に計算が終わりません。
F[2](2)=F[1](F[1](2))=F[1](F[0](F[0](2)))=F[1](F[0](3))=F[1](4)
=F[0](F[0](F[0](F[0](4))))=F[0](F[0](F[0](5)))=F[0](F[0](6))=F[0](7)=8
となります。
>>157
HとFでは定義が違うことに注意しなければいけませんが、6-303には、
H[0](x)=x+1
H[1](x)=H[0](x+1)=x+2
H[n](x)=H[0](x+n)=x+n+1
と書いてあります。一行目と二行目は定義に当てはめただけです。
H[a+1](x)=H[a](x+1)の式を見ると、[ ]の中の数を1減らして
( )の中の数を1増やしています。これをn回繰り返すと、
H[n](x)は[ ]の中の数がｎ減って( )の中の数がn増えるので、
H[n](x)=H[0](x+n)となります。H[0]の定義を使えばH[n](x)=x+n+1となります。
この式は、nがどんな自然数でも成り立つので、nをxに置き換えてもかまいません。
すると、H[x](x)=x+x+1=2x+1となります。
以下も同様で、「n回繰り返す」ということをやってnを含む式を導いてから、
「nをxに置き換える」ということをやっています。
161:もやしっ子
07/01/20 03:58:47
>>160
わざわざすみません。過去ログですっ飛ばしてるような初歩的なことばかりで。
F[ω+1](2)=F[ω](F[ω](2)) は了解しました。昔ながらの入れ子をやってしまいました。
＞一行目と二行目は定義に当てはめただけです
まんまですね。びびりすぎでした。
＞「n回繰り返す」ということをやってnを含む式を導いてから、
＞「nをxに置き換える」
H[n](x)=x+n+1 もガッテンです。ここから
H[x](x)=x+x+1=2x+1 や、それ以降が出てくる訳ですね。どれどれ。
H[ω+n](x)=H[ω](x+n)=H[x](x+n)=2x+n+1
H[2ω](x)=H[ω+x](x)=H[ω](2x)=H[x](2x)=3x+1
…なんか前述の解と違っておるのですが、まだ勘違いしているのでしょうか、僕は。
162:１３２人目の素数さん
07/01/20 05:05:21
>>161
＞H[ω](x+n)=H[x](x+n)
＞H[ω](2x)=H[x](2x)
の部分ではωをxではなく、( )の中身に置き換える必要があります。つまり、
H[ω](x+n)=H[x+n](x+n)=2(x+n)+1=2x+2n+1
H[ω](2x)=H[2x](2x)=4x+1
となります。
163:もやしっ子
07/01/20 06:23:52
>>162
なんとなく分かったような気がします。
H[ω](x+n) においては基本列がΛ(x+n)になるから、ということでしょうか。
基本列と呼ぶからには列なんだと考えてしまうのですが、ひとかたまりの
ものとして振舞いますよね。収束と対応しているから同値ということでしょうか。
そもそもなぜ列がΛ(x)として表現できるのかがいまいち…
164:１３２人目の素数さん
07/01/20 07:18:51
>>163
基本列は順序数の数列だと考えればいいです。
数列を{a_n}と書くように、基本列をΛ(x)と書いています。
数列でnの部分に相当するのが基本列でのxです。
ただ、数列でa_n(つまり一つの項)に相当するものもΛ(x)と書いています。
H[λ](x)=H[Λ(x)](x) (Λ(x)はλに収束する基本列)
と書いてあるとき、左のΛ(x)はa_nの意味で、右のΛ(x)は{a_n}の意味です。
これは、f(x)が「関数」そのものを表すこともあれば、
「関数にxを代入した値」を表すこともあるのと同じです。
165:もやしっ子
07/01/20 07:49:26
>>164
なるほど、数列の一般項が自然数の関数であるようなものですか。
また解読できるログが増えるといいなぁ…
166:もやしっ子
07/01/20 16:56:59
>>110のHardy functionの定義で
H[0](x)=x というのはH[0](x)=x+1の誤植でしょうか。
それと、F[ω+x](x)を展開する場合、ω+xは極限順序数ではないので
(xは自然数なのでω+(x-1)が存在してω+x=ω+(x-1)+1となる)、
F[ω+x](x)=F[ω+(x-1)]^x(x) とすべきでしょうか。
またやっちまった予感…
167:もやしっ子
07/01/20 17:11:10
自己レス。誤植ではありませんでした。
168:１３２人目の素数さん
07/01/21 00:42:18
>>166
x≠0のときはそれで合ってます。
x=0のときも考えるならば、F[ω+0](0)=F[ω](0)=F[0](0)=0+1=1となります。
169:もやしっ子
07/01/21 01:37:50
>>168
どうもありがとうございます。
ようやくHardy functionのビギナー(僕もですが)向け説明文を
一通り記述したので、研究室の方にupした際は添削して頂ければ
幸いです。推敲がまだなので後日…
170:１３２人目の素数さん
07/01/21 03:09:49
6-713を読んでみました。大体の流れとしては、
φ_α(β)≒ak(ω,β,α)
Γ_0はφ_{*}(0)にω回入れ子にすれば得られるはずだから
Γ_0≒ak^ω(ω,ω,*)
そして、>>116ではアッカーマン関数よりF[ε_0]の方が急激に増加するはずだから
F[ε_0](ω)＞Γ_0＞Veblen関数で定義される数
としているのだと思います。
一方、>>135での私の見積もりでは、
F[ε_0](ω)≒φ_ε_0(ω)＜Γ_0
ということになってしまいます。
こうなってしまう原因としては、「アッカーマン関数よりF[ε_0]の方が急激に増加する」というのは
変数が自然数のときのみ成り立つことで、変数が順序数だと成り立たないというのが考えられます。
例えば、2^xの方がx^2より急激に増加しますが、2^ω＜ω^2です。
これを見ると、順序数の関数の大小比較は簡単にはできないというのがわかります。
171:１３２人目の素数さん
07/01/21 04:02:47
>>132、>>136でのVeblen関数の拡張は、6-714での拡張とほぼ同じもののようです。
ただ、>>132、>>136では「順序数」個の変数を使っていることになりますが。
172:もやしっ子
07/01/21 04:10:24
関数と表記法のページにHardy functionを追加しました。
さてVeblen functionの入り口にやってきた、と思ったら…
>>170
無限順序数の演算は交換法則が成り立たないんですよね。
それだけ知ってます。手を出すとやばそうなので見守ります。
ところで、Veblen functionの
φ_1(0)=ε_0 を導いてみたんですが、左辺は
φ_(β'+1)(γ)の形をとっているので β'=0 γ=0 とおいて、
γ=0のとき、α(0)=φ_β'(0)、α(ｎ+1)=φ_β'(α(n))という漸化式を定義。
すると
α(0)=φ_0(0)=1
α(ｎ+1)=φ_0(α(n))=ω^α(n) を得る。この数列は
1,ω,ω^ω,ω^ω^ω,… となるので、収束先はε_0となる。
というのはいかがでしょう。
173:１３２人目の素数さん
07/01/21 10:24:45
>>172
それで合ってますね。Veblen関数については、以下のような見方もできます。
Veblen関数の定義は、φ_(α+1)(β)=「φ_α(γ)=γとなるβ番目の数」ということですが、
これは、「ある順序数γより小さい数に+,φ_0,φ_1,…,φ_αを何回適用してもやはりγより小さい」
という条件を満たすγのうちβ番目のものと見ることができます。
「 」の条件は、「γより小さい数は+,φ_0,φ_1,…,φ_αという演算について閉じている」
と言い換えることもできます。
もう少し具体的な例で考えてみると、φ_0(α)=ω^αより小さい数はいくら足し合わせても
φ_0(α)=ω^αより小さな数となります。
例えば、α=0のときはω^0=1より小さい数は0しか存在せず、
0をいくら足し合わせても1よりは小さいことから、
1が「その数より小さい数は+について閉じている」ような0番目の(最初の)数ということになります。
α=1のときは、ω^1=ωより小さい数(つまり自然数)をいくら足し合わせても
ωよりは小さいということになります。これを逆に考えると、自然数をいくら足し合わせても
到達できないような最小の数をφ_0(1)=ωとして定義していることになります。
この考え方でα=2としてみると、φ_0(2)は2番目の数であるため
1番目の数であるωよりは大きな数となります。なので、自然数やωをいくら足し合わせても
到達できないような最小の数を考えると、それはω*nの収束先であるω^2ということになります。
φ_1(0)=ε_0で考えると、ε_0より小さい数に+やφ_0を何回適用しても
ε_0より小さいということになります。逆に考えれば、0に+やφ_0を何回適用しても
到達できないような数のうち、最小のものをφ_1(0)=ε_0と定義していることになります。
φ_1(1)=ε_1は、ε_0以下の数(ε_0も含む)に+やφ_0を何回適用しても到達できない
最小の数ということになります。
このように、+だけでは到達できない数をφ_0で定義し、+とφ_0だけでは到達できない数をφ_1で定義し、
+とφ_0とφ_1だけでは到達できない数をφ_2で定義し、…とやっていって、
最終的にはVeblen関数を何回使っても到達できない最小の数をΓ_0と定義していることになります。
174:１３２人目の素数さん
07/01/23 21:15:20
すごく面白そうなんだが、いかんせん俺には難しすぎ…。
175:もやしっ子
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変換なんかは関数を大きくする変換だしね。
計算可能じゃない関数がズルだとかいっていたらそこで進歩は止まるよ。
虚数なんかは数じゃないといって否定するようなもの。
実際ビジービーバー関数よりずっと大きな関数も出てきてるし。