元のスレッド
巨大数探索スレッド５
- 682 名前：１３２人目の素数さん ：03/10/10 11:14
- 今まで過去ログずっと見てきたが、
やはり>>653のような関数ネスト法はかなりすごいと思う。
２重帰納とかも使わずにx+1からf=1_1(x)段階でAc関数までいけるし、
Ac関数から初めてかつネスト回数の変数をネスト関数化するなどの
工夫を加えればフィッシュ数と比較できるような感じがする。
とりあえず>>653の多重超ネスト漸化式を
自分で改造してみた。
f(a)=A(a,a)
A(a,b)=A(a-1,A(a,b-1))
A(a,0)=A(a-1,a)
N(f,x,1)=f(x)
N(f,x,2)=f(f(x))
N(f,x,n)=f^n(x)
関数fにはA(x,x)を入れる。
- 683 名前：１３２人目の素数さん ：03/10/10 11:19
- 続き。以下Ａ段階
(Nn^(Nn)(a,b,c)=Nn^(Nn(a,b,c))(a,b,c),n=1,2,...)
※ここで３項以上のA()関数は、
A(a,b,...,n)=A(a,A(a,b-1,...,n),...,A(a,b-1,...,n))
A(a,b,...f,0,h,...,n)=A(a-1,b,...f,a,h,...,n)
f[1](x)=N^(N)(f,x,x)=f^x(x)
f[n](x)=N^(N)(f[n-1],x,f[n]x)
２項以上はAc関数の要領で[]内を２重帰納で繰り返す。
f[1,1](x)=N1^(N1)(f[n],x,f[n])
f[1,n](x)=N1^(N1)(f[A[1,n-1]],x,f[A[1,n-1]])
f[2,1](x)=N2^(N2)(f[1,2],x,f[2,1])
f[2,n](x)=N2^(N2)(f[1,A[2,1]],x,f[1,A[2,1]])
N(n-1)^N(n-1)=Nn
f[n,1](x)=Nn^(Nn)(f[n-1,n],x,f[n-1,n])
f[n,m](x)=Nn^(Nn)(f[n-1,A[n,m-1]],x,f[n-1,A[nm-1]])
f[1,1,1](x)=Nn1^Nn1(f[n,n],x,f[n,n])
f[l,m,n](x)=
Nln^Nln(f[l-1,A[l,m-1,n],A[l,m-1,n]],x, f[l-1,A[l,m-1,n],A[l,m-1,n]])
f[l,0,n](x)=Nln^Nln(f[l-1,l,n],x,f[l-1,l,n])
f[l,n,0](x)=Nln^Nln(f[l-1,n,l],x,f[l-1,n,l])
Nk=f[a,..n-1個..,a]^(f)(x)
f[1,..n個..,1](x)=Nk^Nk(f[n,..n-1個..,n],x,f[n,..n-1個..,n])
f{1|a}(x)=f[a,..n個..,a](x)
Ａ段階ここまで
- 684 名前：１３２人目の素数さん ：03/10/10 11:21
- さらに続き
以後f{1|a}(x),f{2|a}(x),...でそれぞれＡ段階を繰り返し。
f{2|1}[1](x)=f{1|n}[]^f(x)
f{m|1}[1](x)=f{m-1|n}[]^f(x)
これをさらにn1×n2×...nm回繰り返す。({}内の項の数が増える)
f{1,1|1}[](x)=f{n|a}[]^f(x)
f{2,1|a}[](x)=f{1,n|a}[]^f(x)
f{n1,1|a}[](x)
...
f{nm,...,n2,n1|a}[](x)
次にＦ関数を定義する。
Ｆ(n,x)=f{nn,...n1|n}^(f)(x)
F^F(a,b)=F^(F(a,b))(a,b))
F[1](n,x)=F^F(F^F(n),F^F(x))
F[N](n,x)=F[N-1]^F(F[N-1]^F(n),F[N-1]^F(x))
- 685 名前：１３２人目の素数さん ：03/10/10 11:25
- 以下、Ａ段階と同様に２重帰納漸化式で繰り返す。(以下Ｂ段階)
F[1,1](n,x)=F[N]^F(F[N]^F(n),F[N]^F(x))
F[1,N](n,x)=F[1,N-1]^F(F[1,N-1]^F(n),F[1,N-1]^F(x))
F[N,1](n,x)=F[N-1,N]^F(F[N-1,N]^F(n),F[N-1,N]^F(x))
F[N,M](n,x)=F[N-1,F[N,M-1](n,x)]^F(F[N-1,F[N,M-1](n,x)]^F(n),F[N-1,F[N,M-1](n,x)]^F(x))
項の数を増やして同様に２重帰納で繰り返し。
F[N1,N2,...,NN](n,x)=F{N|b}(x) (N1=N2=...=NN=b)
さらにＡ段階と同様にM1×M2×...×MN回Ｂ段階を繰り返す。
F{2|1}[1](n,x)=F{1|N}[N1,...,NN]^F(n,x)
F{2|1}[1,1](n,x)=F{n|a}[]^F(x)
...
F{NN,...,N2,N1|a}[](x)=F{N|a}[](x)
ここまで来てできる関数をM(x)とおく。
M(0)=1,
M(x+1)=M^{M^(x)|M^(x)}[]M(x)
これでどのあたりまで増加できるのだろう？
- 686 名前：１３２人目の素数さん ：03/10/10 11:33
- 訂正スマン。
Ａ段階で
A(a,b,...,n)=A(a,A(a,b-1,...,n),...,A(a,b-1,...,n))
→A(a,b,...,n)=A(a-1,A(a,b-1,...,n),...,A(a,b-1,...,n))
最後のあたりで
M(x+1)=M^{M^(x)|M^(x)}[]M(x)
→M^{M^(M(x))(x)|M^(M(x))(x)}[]M(x)
- 687 名前：１３２人目の素数さん ：03/10/10 16:06
- やっぱり数学板は数式エディタを採用するべきだ。
もしくはTeXで書いてどこかにうｐしてくれ。
読む気にならん・・・
- 688 名前：１３２人目の素数さん ：03/10/10 16:25
- http://www.forkosh.com/cgi-bin/mimetex.cgi?formdata=4%24f%28x%29%3D%5CBigint_%7B-%5Cinfty%7D%5Ex%7Ee%5E%7B-t%5E2%7Ddt
- 689 名前：１３２人目の素数さん ：03/10/10 16:27
- http://www.forkosh.com/htdocs/mimetex.html
ここからクエリを送信して、出てきた数式を確認して、
URLを貼る。
- 690 名前：１３２人目の素数さん ：03/10/10 16:28
- １つずつの式ごとにURLがあってもうざいだけか。
- 691 名前：682 ：03/10/10 17:41
- 一応自分の考えでいくと、
最初のf[n]段階ですでにＳ変換完了して
次の２項目以降ではもうＳＳ変換段階に入っているのかと思うが。
自分でも計算して調べてみたいが素人だし時間がかかるなぁ…。
あとまた訂正失礼。
最初のA(a,b)関数の段階で、
A(0,a)=a+1を加える。
f{1|a}(x)=f[a,..n個..,a](x)→f{1|a}(x)=f[a,..a個..,a](x)
M^{M^(M(x))(x)|M^(M(x))(x)}[]M(x)→F^{M^(M(x))(x)|M^(M(x))(x)}[]F(x)
- 692 名前：１３２人目の素数さん ：03/10/11 08:42
- 乙カレ様でした 私もあまり良くわかってないので間違ってたらスマソ
>>683の７行目って
f[n](x)=N^(N)(f[n-1],x,f[n]x) → f[n](x)=N^(N)(f[n-1],x,f[n-1]x)
ではないでしょうか？
上記の記述で言うとf[n](x)では単純な関数ネストにしかならないので
Ｓ変換で例えれば一回目のg(x)の増加にはならないと思います
２項でＳ変換に相当という感じな気がします（間違ってたらスマソ）
全体的に見て上記の拡張方法は、
ふぃっしゅ数のVer2以降でやった関数の対角化の次元をあげていく手法によって
Ｓ変換１回目の関数ネストのスピードを上げてるように見えますが、
どうなんでしょう？
- 693 名前：682 ：03/10/16 20:05
- やはり前に挙げた単純なネスト方法は最初で
Ｓ変換よりかなり下がると思ったので、別の方法で考えてみた。
まず基盤として、ネストを使った次の漸化式を使う。
A(a)=a+1
以下An^(An(a))(a)=An^An(a)
A1(a+1)=A^A(A1(a)), A2(0)=A(a+1)
A2(a+1)=A1^A1(A2(a))), A2(0)=A1(a+1)
An(a+1)=A[n-1]^A[n-1](An(a)), An(0)=A[n-1](a+1)
これらの漸化式はそれぞれ初期値が代入した変数により動的に変化する。
つまり、A1(1)→A1(a)→A2(1)→A2(a)→...→An(1)→An(a)と
いうように２次元的に変化する。
>>692
ありがとうございます。
７行目はf[n](x)=N^(N)(f[n-1],x,f[n-1]x)ですね。
- 694 名前：682 ：03/10/16 20:06
- やはり前に挙げた単純なネスト方法は最初で
Ｓ変換よりかなり下がると思ったので、別の方法で考えてみた。
まず基盤として、ネストを使った次の漸化式を使う。
A(a)=a+1
以下An^(An(a))(a)=An^An(a)
A1(a+1)=A^A(A1(a)), A2(0)=A(a+1)
A2(a+1)=A1^A1(A2(a))), A2(0)=A1(a+1)
An(a+1)=A[n-1]^A[n-1](An(a)), An(0)=A[n-1](a+1)
これらの漸化式はそれぞれ初期値が代入した変数により動的に変化する。
つまり、A1(1)→A1(a)→A2(1)→A2(a)→...→An(1)→An(a)と
いうように２次元的に変化する。
>>692
ありがとうございます。
７行目はf[n](x)=N^(N)(f[n-1],x,f[n-1]x)ですね。
- 695 名前：682 ：03/10/17 15:17
- いつのまにか連続カキコシマタ。とりあえず続き。
まずf漸化式。これも前の漸化式のように２項を使って、
各式の初期値を変数で動的に決める。
初期関数f1に前の漸化式を代入して、繰り返し関数ネストを使って
全体として２重帰納になり、これでVer1のＳ変換に相当すると思う。
以下、f_n^(f_n(x))(x)=f_n^f_n(x)
f1(x)=A[x](x),
f2(x+1)=f_1^f_1(f_2(x)), f_1^2(x)=A[A[x](x)](A[x](x)), f_2(0)=f_1(x+1)
f3(x+1)=f_2^f_2(f_3(x)), f_3(0)=f_2(x+1)
fn(x+1)=f_[n-1]^f_[n-1](f_n(x)), f_n(0)=f_[n-1](x+1)
次にf2漸化式。これはf漸化式の添え字や変数に前の式を関数ネストしたものを
代入するもので、ＳＳ変換でいうＳ変換の回数の増加式にあたる。
またこの漸化式は同時に２種類の項と動的初期値を使っていて、増加率をさらに上げている。
f2_1(a)=f_[f_a^f_a(f2_1(a-1))](f_a^f_a(A2_1(a))), f2_1(0)=f_a+1(a+1)
f2_2(a)=f_[(f2_1^f2_1(f2_2(a))](f2_1^f2_1(f2_2(a))), f2_2(0)=f2_1(a+1)
f2_n(a)=f_[(f2_[n-1]^f2_[n-1](f2_2(a))](f2_[n-1]^f2_[n-1](f2_2(a))),
f2_n(0)=f2_[n-1](a)
以下、f3漸化式以降も同様にして計算する。
fm_1(a)=f[m-1]_[f[m-1]_a^f[n-1]_a(fm_1(a-1))](f_[m-1]^f_(fm_1(a-1))), fn_1(0)=f[n-1]_a(a)
fm_n(a)=f[m-1]_[fm_[n-1]^fm_[n-1](fm_n(a-1))](fm_[n-1]^fm_[n-1](fm_1(a-1))),
このあたりでＳＳ変換は行ってるかな？
- 696 名前：682 ：03/10/17 15:19
- さらに続き。
３項以上のf漸化式は、682以降であげた方法と同じようにする。
f[1,1,1](x)=f[x,x]^(f[x,x](x))(f[x,x](x))
f[l,m,n](x+1)=
f[l-1,f[l,m-1,n]^f[l,m-1,n](f[l,m,n](x))(x),(f[l,m-1,n]^f[l,m-1,n](f[l,m,n](x))(x)](f[l,m1,n](x))
f[l,1,n](x)=f[l-1,n,n](x)
それ以降は682以降と同じように上の方法を繰り返す。
以降同じようにして、M1(n,x)ではfの項の次元拡張関数にあたる。
さらにf[1](x)のときと同じように
M1(n+1,x+1)=f[nn,...,n2,n1](x), F(0,0)=1
とおくと、さらに次元数nなどが莫大に増加する。
以降Ｍ段階
次にM1(n,x)を最初に使ったBn(x,y)関数に対応させる。
B1(0)=M1(a,a)
B1(a+1)=M1^(B1(a,a))(a,a)
B1(a+1)=B1^B1(B2(a)), B2(0)=B1(a+1)
B1(a+1)=M1[n-1]^FM[n-1](FMn(a)), FMn(0)=FMn[n-1](a+1)
以降f[a,b...]漸化式と同じようにして、
m_1(x)=M[x](x)
m_n(x)=M[M_[n-1]](M_[n-1])
m[2,n](x)=m[n-1]_[m2_[n-1]^m2_[n-1](m2_n(a-1))](m2_[n-1]^m2_[n-1](m2_n(a-1)))
...以上Ｍ段階
次にM2関数,...,Mn関数を決めて、M1関数と同じようにＭ段階を繰り返す。
M2(x+1)=m2[n(M2(x)),...,n2,n1](M2(x)))(M2(x)),M2(0)=m[nx,...,n2,n1](x)
...
Mn(x+1)=m2[n(Mn(x)),...,n2,n1](Mn(x)))(Mn(x)),Mn(0)=m[nx,...,n2,n1](x)
フィッシュ数の対抗ネタ数→M[M100(100)](M100(100))
動的初期値とか２次元みたいな数列とかいろいろ考えたが
これならVer.1でS(n)変換はとっくに超えているか？
- 697 名前：682 ：03/10/17 15:30
- 訂正発見。
Ｍ段階で
B1(a+1)=B1^B1(B2(a))→B2(a+1)=B1^B1(B2(a))
B1(a+1)=M1[n-1]^FM[n-1](FMn(a)), FMn(0)=FMn[n-1](a+1)
→Bn(a+1)=B[n-1]^B[n-1](Bn(a)), Bn(0)=B[n-1](a+1)
M2(x+1)→M2(n+1,x+1),M2(x)→M2(n,x)
Mn(x+1)→Mn(n+1,x+1),Mn(x)→Mn(n,x)
- 698 名前：682 ：03/10/21 18:26
- 久しぶりにage
>>181のような３重帰納関数を試しに計算してみたら
とんでもないような結果になりました。
A(x,y,z)=A(A(x-1,A(x,y-1,z),z),A(x-1,A(x,y-1,z),z),z-1)
A(0,y,z)=A(y,y,z-1), A(x,0,z)=A(x,x,z-1), A(0,0,z)=A(1,0,z-1)
A(x,y,0)=A(A(x-1,y),y-1), A(0,y,0)=A(y,y-1,0), A(x,0,0)=f(x)
として、A(2,2,2)を求めると、
A(x,x,0)=g(x),g^a(x)=ga(x),@は次の項に等しい項
A(2,2,2)=A(@,A(1,A(@,A(1,A(2,0,2),2),1),2),1)=A(@,A(1,A(@,A(1,α,2),1),2),1)=X
A(2,0,2)=A(2,2,1)
A(2,2,1)=A(@,A(1,A(@,A(1,A(2,0,0),1),0),1),0)=A(@,A(1,A(@,A(1,3,1),0),1),0)
=A(@,A(1,A(g5(108),g5(108),0),1),0)=A(@,A(1,g6(108),1),0)
=>A(@,g[2^g6(108)](108),0)=α
A(1,3,1)=A(@,A(0,A(@,A(0,A(@,A(0,A(1,0,1),1),0),1),0),1),0)=A(@,A(0,A(@,A(0,A(@,A(0,3,1),0),1),0),1),0)
=A(@,A(0,A(@,A(0,A(@,A(3,3,0),0),1),0),1),0)=A(@,A(0,A(@,A(0,A(108,108,0),1),0),1),0)
=A(@,A(0,A(@,A(0,g(108),1),0),1),0)=A(@,A(0,A(g2(108),g2(108),0),1),0)
=A(@,A(0,g3(108),1),0)=A(g4(108),g4(108),0)=g5(108)
A(1,g7(108),1)=A(@,A(0,A(1,A(...g7(108)回...A(1,0,1)...),0),1),0)>=g(2^g7(108))(108)
A(β,β,1)=A(@,A(1,A(@,A(...β回...A(β,0,0)...),0),1),0)
>=g[2^g[...β(=Kn-1)回...g(2^g(2^g(2^β)(108))(108))(108)...β回...)(108)=Kn, K1→{β=g6(108)}
A(1,α,2)=A(@,A(0,A(@,A(...α回...A(1,0,2)...),1),2),1)=A(@,A(0,A(@,A(...α回...g(108)...),1),2),1)
>=g(2^g(...【g(108)*K1*K2*...*K[α]回】...g[2^g(108)](108)...)
A(1,0,2)=A(1,1,1)=A(@,A(0,A(1,0,1),1),0)=A(108,108,0)=g(108)
A(1,0,1)=A(1,1,0)=A(A(0,1),0)=3
A(1,1,2)=A(@,A(0,A(1,0,2),2),1)=A(@,A(0,g(108),2),1)=A(@,A(g2(108),g2(108),1),1)
A(x,x)=g(x),
変数値が２でもac関数とかでは書き表せないほどの大きな数になりました。
さらに項数を増やす変数を作ってn重帰納のnの数自体を増幅させるような
漸化式を使えば今までの方法よりもはるかに大きな数ができるだろうな・・・。
- 699 名前：１３２人目の素数さん ：03/10/21 19:14
- ふぃっしゅ数は、そのトリッキーさが人々の興味をひいていたんだけど、
そんな事せずとも実は「適当にでっち上げた」式で、
より巨大数が簡単に出来そうってんで、みんな醒めちゃったのよね。
第二次ブームを起こすためには、何か新しい視点が必要だろうな。
「2つの多重帰納法の大きさ比較」あたりは、
平凡でごく自然なテーマだけど、ブームは無理っぽいな。
- 700 名前：１３２人目の素数さん ：03/10/22 17:34
- ブームもいいけど、地道な検証も悪くない
なかなか自分で計算する力はないけど、楽しんでるよ
- 701 名前：１３２人目の素数さん ：03/10/23 13:50
- はじめて書き込みます。
色々検索しているとき偶然Part1（？）のログにたどりつき、ここまで半日かけて読みました。
といっても複雑な数式は飛ばしながら全体の流れをなんとなく読んだだけですが。
プログラム言語でグラハム数ふぃっしゅ数他の巨大数を記述するというのは
ここまで誰かやってみたのでしょうか？
もちろん結果を出すためには時間もメモリ容量も全然足りませんが、
記述というだけならなんとかできると思います。
自分はプログラマーで、数学の知識はこのスレの人達に比べると乏しいのですが、
計算に使うタワーやアッカーマンの漸化式はわりと簡単にプログラム上で
関数化できると思うので色々やってみようかなと。
- 702 名前：１３２人目の素数さん ：03/10/23 22:02
↑そっち方面の人は少なかったので、お願いします〜
>>682氏が頑張ってる以外は
新たな展開が少なくてちょっと停滞気味のスレになってます
- 703 名前：701 ：03/10/24 01:19
- >>702
期待せずに待っていてください
千里の道も一歩から。というわけでタワー演算子の計算関数を作ってみたんですが、
>>537 の 2↑^n 2 に関する記述って間違ってませんか？
タワー表記の定義に従って計算すると
2↑2 = 4
2↑↑2 = 2^4 = 16
2↑↑↑2 = 2^2^2^2^2^2^2^2^2^2^2^2^2^2^16
のようになると思いますがあっていますかね？
- 704 名前： ◆KIs/plq/Ws ：03/10/24 11:17
- >>703
ならないよ。
2↑↑↑2
= 2↑↑2 (2個の2の間に↑↑)
= 2↑2 (2個の2の間に↑)
= 4
- 705 名前：701 ：03/10/24 12:23
- >>704
わかったかも。
タワーの計算がなぜか合わないと思っていたら、どうもサイトの情報が間違っていたみたいですね。
ここ http://www.geocities.co.jp/Technopolis/9946/function.html
元を正せばここ http://www.nn.iij4u.or.jp/~hsat/misc/math/grahamnum.html
の表記、
＞ x↑y = x^y,
＞ x↑↑1 = x↑x, x↑↑y = x↑(x↑↑(y - 1)),
＞ x↑↑↑1 = x↑↑x, x↑↑↑y = x↑↑(x↑↑↑(y - 1)),
＞ x↑↑↑↑1 = x↑↑↑x, x↑↑↑↑y = x↑↑↑(x↑↑↑↑(y - 1))
が間違えていたようです。
これだと、x↑↑2 を展開したときに x↑(x↑↑1) = x↑(x↑x) になってしまう。
http://mathworld.wolfram.com/ArrowNotation.html
http://mathworld.wolfram.com/PowerTower.html
が正しいようですね。
以上を踏まえてタワー表記を定義するなら、
x↑y = x^y
x↑↑2 = x↑x
x↑↑y = x↑(x↑↑(y - 1))
x↑↑↑2 = x↑↑x
x↑↑↑y = x↑↑(x↑↑↑(y - 1))
x↑↑↑↑2 = x↑↑↑x
x↑↑↑↑y = x↑↑↑(x↑↑↑↑(y - 1))
となるわけですね。
さらに、
x↑^n 1 = x
x↑^n 0 = 1
だと思います
- 706 名前：701 ：03/10/24 12:24
- ・・という勘違いもありましたが、とりあえずグラハム数までの巨大数を
計算するプログラムのソースです。
http://okei-super.hp.infoseek.co.jp/src_large_number.txt
グラハム数以外の小さい（？）数は指数関数Power()を数回呼ぶ程度の処理ですが、
グラハム数だけは再帰関数Tower()を使っています。
もちろんコンパイルは通りますが、実行してもまず結果がオーバーフローになるか、
処理が半永久的に終わらないか、スタックオーバーフローで止まるかのいずれかだと思います。
次はどうしようかな、ふぃっしゅ数にとりかかる前にチェーン表記を関数化してみるかな。
- 707 名前：682 ：03/10/24 15:47
- ふぃっしゅ氏がいないのなら代わりに頑張ってみようかな。
ここで一つネタ。
数の代わりに関数をタワー表記にしてみるのはどうだろう？
関数の場合はネスト回数でいいかな。
とりあえずひととおりまとめてみた。ただし記号は↑でなく＾だが。
f^f(x)(x)=f(^2)2(x)
f^(...g(x)回...f^(x)...)(x)=f(^2)g(x)(x)
f(^2)(f(^2)...g(x)回...(x)...)(x)=f(^3)g(x)(x)
f(^n)(f(^n)...g(x)回...(x)...)(x)=f(^n+1)g(x)(x)=M1
f(^m)(f(^m)...[f(^m-1)(...[f(^m-2)(...[...[f(^1)(...f(x)回...(x)...)]回...]...(x)...)]回...(x)...]回...(x)...)
f(^f(x))f(x)=f(^2,1)2(x), f(^(f(^f(x))f(x)))f(x)=f(^2,1)3(x)
f(^(f(^...g(x)回...f(^f(x))f(x)...)(x)=f(^2,1)g(x)(x)
f(^2,1)(f(^2,1)(...g(x)回...(f(^2,1)f(x))...)(x)=f(^2,2)g(x)(x)
f(^2,n)(f(^2,n)(...g(x)回...(f(^2,n)f(x))...)(x)=f(^2,n+1)g(x)(x)
f(^n,f(^n,...g(x)回...f(^n,f(x))f(x)...)(x)=f(^n+1,1)g(x)(x)
f(^(f(^...g(x)回...(^f(^f(x),f(x))f(x),f(^f(x),f(x))f(x))...)(x)=f(^2,1,1)g(x)(x)
f(^a_1,a_2,...,a_g(x))f(x)=f(2^1)g(x)(x), (a_n=f(x))
f(2^2)g(x)=f(2^1)(f(2^1)(...g(x)回...(f(2^1)f(x))...)(x)
・・・
f(m^f(x),f(x),...g(x)個...,f(x))f(x)=f(m+1^1)g(x)(x)
いわゆるチェーン表記の関数ネスト版ですね。
g(x)=f(x^1)f(x)(x)とかおけば変換にかなり使えるかも。
- 708 名前：もやしっ子 ：03/10/25 01:56
- ちわヽ(´ー｀)ノ
最近はネタが高度なのと本業多忙につき、語り部をやるべき
自分がなんにもできない状況が続いており、申し訳ないです。
また新たな展開が出てきているようで楽しみです。
- 709 名前： ◆KIs/plq/Ws ：03/10/25 12:14
- >>707
早くも一行目から解読不能です＿|￣|○
- 710 名前：１３２人目の素数さん ：03/10/25 17:01
- ＞数の代わりに関数をタワー表記にしてみるのはどうだろう？
それ随分前ににみんなでやってなかったっけ？
- 711 名前：１３２人目の素数さん ：03/10/25 17:01
- ＞数の代わりに関数をタワー表記にしてみるのはどうだろう？
それ随分前ににみんなでやってなかったっけ？
- 712 名前：１３２人目の素数さん ：03/10/25 17:02
- >>707
＞数の代わりに関数をタワー表記にしてみるのはどうだろう？
それ随分前ににみんなでやってなかったっけ？
- 713 名前：１３２人目の素数さん ：03/10/25 17:04
- 調子が悪くて３連になってしまいましたスマソ
- 714 名前：１３２人目の素数さん ：03/10/25 20:03
- 関数をタワーにするのと関数の肩に数のタワーをつけるのは違うのでせうか
- 715 名前：682 ：03/10/27 12:24
- >>710>>714
正しく言うと、今までのタワー表記で言うa(↑c)bのaの部分を関数にして、
ｃが１のときはbを関数aのネスト回数にするところから始まります。
つまり714では後者にあたると思います。
例えばf(^2)2(x)=f^(f(x))(x)、f(^2)3(x)=f^(f^(f(x))(x))(x)となり、
以降(^2)の右の数を増やすごとに、ネスト回数部分の入れ子を増やしていき、
f(^2)(f(x))(x)までいったときにはf(^3)2(x)となります。
(^3)以降は(^2)と同様に、f(^3)3(x)=f(^2)(f(^2)(f(x))(x))(x)となり
f(^2)b(x)のｂの部分を多重入れ子にしていきます。
そして(^4),(^5),...と続けていきます。
こうしていくことで、関数f(x)のネスト回数をak関数化していくことができます。
f(^2,1)b(x)では、f(^(f(^...b回...f(^f(x))(f(x))(x)...)(x)))f(x)(x)というように
f(^c)a(x)のｃの部分にf(^c)a(x)をｂ回ネストして、ｃの値がどんどん増えます。
(^2,n)以降ではf(^n)と同じようにしていき、(^a,...,n)と変数が増えていくと
f(x)→b→c→dといったチェーン表記のようになり、(a^b)になると
今度は回転チェーンのような効果が得られます。
全体として関数のネスト回数が回転チェーンで示すような増大率が得られます。
あと707の９,１０行目の
f(^n)(f(^n)...g(x)回...(x)...)(x)=f(^n+1)g(x)(x)=M1
f(^m)(f(^m)...[f(^m-1)(...[f(^m-2)(...[...[f(^1)(...f(x)回...(x)...)]回...]...(x)...)]回...(x)...]回...(x)...)
は無視ね。失礼。
- 716 名前：682 ：03/10/27 14:02
- 例の３重帰納関数A(x,y,z)の増大率について分析してみた。
A(1,1,1)=g(108), g(a)=A(a,a,0)
A(n,1,1)=g[2*n](108)となる。
まずA(1,n,1)について調べる。
A(1,2,1)=g[2*g4(108)-1](108)=X2
A(1,3,1)=A(A(@,A(0,3,1),0),2,1)=A(A(@,A(3,2,1),0),2,1)=A(A(g[2*g(X1)](1),g[2*g(X1)](1),0),2,1)
=A(g[2*g(X1)+1](1),2,1)=A(A(@,A(g[2*g(X1)+1](1)-1,2,1),0),1,1)=A(A(@,A(...g[2*g(X1)+1](1)回...A(A(@,A(0,2,1),0),1,1)...),0),1,1)
=A(A(@,A(...g[2*g(X1)+1](1)回...A(A(@,A(1,1,1),0),1,1)...),0),1,1)=A(A(@,A(...X2回...A(g2(108),1,1)...),0),1,1)
=g[2*g[...X2回...2*g[g2(108)](108)]...](108)=X3, X2=g[2*g(X1)+1](1)
A(n,2,1)=A(A(@,A(...n回...A(A(@,A(1,1,1),0),1,1)...),0),1,1)=g[2*g[...n回...2*g[g2(108)](108)]...](108)
このようにｎが２から３に上がると一気に増大する。n=4では
A(1,4,1)=A(A(@,A(0,4,1),0),3,1)=A(A(@,A(4,3,1),0),3,1)>A(X3_4,3,1)
=A(A(@,A(...X3_4回...A(3,2,1),0),2,1)...),0),2,1)
>=g[2*g[...【X3*X3_2*...*X3_[X3_4]回】...2*g[g2(108)](108)]...](108)
A(n,3,1)=A(A(@,A(n-1,3,1),0),2,1)=A(A(@,A(...n回...A(3,2,1),0),2,1)...)),0),2,1)
g[2*g[...X3_k回...2*g[g2(108)](108)...](108)=X3_k+1, X3_1=X3
A(4,3,1)=X3_4
というようにn=3よりはるかに増大率が大きくなる。
このように全体としてみていくと、
A(1,n,1)→Ｓ変換に相当すると思われる。
- 717 名前：682 ：03/10/27 14:03
- 続き。次にＳ(２)変換以降で調べていくと、
A(n,1,2)=A(A(@,A(A(@,A(n,n-1,2),1),0,2),1),0,2)
と、A(a,1,2)が繰り返されていき、これはＳ(２)変換の対角化と見られる。
以下同様にして、
A(n,2,2)=A(A(@,A(n-1,2,2),1),1,2)=A(A(@,A(...n回...A(2,1,2)...),1),1,2)→Ｓ(３)変換対角化
A(n,n,2)→Ｓ(ｎ)変換対角化
となることが推定できる。A(a,b,3)以降は、
A(n,1,3)=A(A(@,A(n-1,1,3),2),0,3)=A(@,A(@,A(...n回...A(1,1,2)...),2),2)→ss(1)変換
A(n,2,3)=A(A(@,A(n-1,2,3),2),1,3)=A(@,A(@,A(...n回...A(2,1,3)...),2)1,3)→ss(2)変換
A(1,n,3)=A(A(@,A(0,n-1,3),2),n-1,3)=A(@,A(0,A(...n回...A(1,0,3),2),1,3)...),2),n-1,3)→ss(n)変換
A(n,1,4)=A(A(@,A(n-1,1,4),3),0,4)=A(@,A(@,A(...n回...A(1,1,3)...),3),3)→sss(1)変換
A(1,n,4)→sss(n)変換＞Ver3ふいっしゅ数
となり、A(1,1,4)段階ですでにVer3ふぃっしゅ数を超えることになる。
このままいくと、A(1,n,m)→s(m-1,n)変換までいくと考えられる。
これ以上次元を上げるには項数を増やすか４重帰納にしていく必要があるだろう。
- 718 名前：701 ：03/10/27 22:29
- >>708
＞もやしっ子さん
http://www.geocities.co.jp/Technopolis/9946/
のページ作っている方ですよね？非常にお忙しいようで
このレスを見ているかどうかわかりませんが、とりあえず
http://www.geocities.co.jp/Technopolis/9946/function.html#tower
のタワー表記のところを正しい記述に直したほうがいいと思いますよ。
今のままだと自分のように勘違いたまま計算してあれれ？って人が
後を断たないと思うので、暇な時間ができたときにでもどうかひとつ更新を。
確かにネタは高度ですよね。682さんのやっているようなこと、
いまいち理解が追いつかない。自分もわかるところから順に
踏みしめていこうかなと思ってます。
- 719 名前：701 ：03/10/27 22:30
- 話はかわって、モーサー数(Moser's number)を計算するプログラムができました。
http://okei-super.hp.infoseek.co.jp/src_large_number2.txt
例によって実行しても結果が出るまでに宇宙が終わるくらいの時間がかかりますが。
ここ２、３日ずっとモーサー数を調べていて、今更ながら色々わかりました。
モーサー数はかなり大きい数ですが、グラハム数に比べると限りなく小さく、
ふぃっしゅ数からすれば無に等しいほどのレベルです。
ちなみに、前スレ407のふぃっしゅ氏のモーサー数のチェーンによる近似、間違ってます。
恐らくモーサー数を算出する前段階のMEGAという数と勘違いしているのではないかと。
モーサー数＜グラハム数 の証明というのは
http://www-users.cs.york.ac.uk/~susan/cyc/b/gmproof.htm
このページに出ているのですが、ちょっと荒っぽい近似を使っていますね。
もう少し精密に計算すると、
3→3→(2[5]-3) ＜ 2[ MEGA ]=2[ 2[5] ] (Moser's number) ＜ 3→3→(2[5]-2)
ただし、 2→259→2 ＜ 2[5] (Steinhaus's MEGA) ＜ 2→260→2
のようになります。
- 720 名前：701 ：03/10/27 22:35
- ここまで色々計算したものをまとめて、モーサー数を含めてチェーンによる大小比較を
改めて書いてみました。
10→2→2=10↑↑2 ＝ 10^10
3→3→2=3↑↑3 ≒ 10^12
無量大数 ＝ 10^68
エディントン数. ≒ 10^79
グーゴル. ＝ 10^100
センティリオン.. ＝ 10^600
現在の最大素数 ≒ 10^10^6
10→3→2=10↑↑3 ＝ 10^10^10
3→4→2=3↑↑4 ≒ 10^10^12
不可説不可説転 ≒ 10^10^37
グーゴルプレックス.. ＝ 10^10^10^2
10→4→2=10↑↑4 ＝ 10^10^10^10
3→5→2=3↑↑5 ≒ 10^10^10^12
第1スキューズ数 ＝ 10^10^10^34
第2スキューズ数 ≒ 10^10^10^10^3
10→5→2=10↑↑5 ＝ 10^10^10^10^10
3→6→2=3↑↑6 ≒ 10^10^10^10^12
10→2→3=10↑↑10 .＝ 10^10^10^10^10^10^10^10^10^10
＝ 10→10→2
＜ 2→259→2 ＜ 2[5] (Steinhaus's MEGA) ＜ 2→260→2
＜ 3→3→3 ＜ 3→3→4
＜ 3→3→2→2 ＜ 2[ 2[5] ] (Moser's number) ＜ 3→3→3→2
＜ 3→3→64→2 ＜ グラハム数 ＜ 3→3→65→2
＜ 3→3→3→3
「おいおい、今更そんな小さい数かよ。ふぃっしゅ数がバージョン５まであって
さらに三重帰納法がどうたらってときにこんな話題出すなｺﾞﾙｧ!!!」
とお怒りの方もいるでしょうが、適当にｽﾙｰしてください。
- 721 名前：１３２人目の素数さん ：03/10/27 22:41
- どの時点で宇宙の電子の数を超えるの？
宇宙の電子の数に一つ一つ(ry はいつ超えるの？
- 722 名前：714 ：03/10/27 23:15
- >>715
確かに違うかなという雰囲気はしてきたんですけど
f(^2,1)以降の定義がよくわかりません。
とりあえずf(^m)nは↓で合ってますか？
f(^2)2 (x) = f^f(x) (x)
f(^m)(n+1) (x) = f(^m)(f(^m)n(x)) (x)
f(^m+1)n (x) = f(^m)(f(x)) (x)
- 723 名前：714 ：03/10/27 23:19
- 二行目がちがうかな。
これじゃwell-definednessすら怪しいし。
- 724 名前：714 ：03/10/27 23:36
- f(^m)1 (x) = f(x)
f(^1)n (x) = f^n (x)
f(^m+1)n+1 (x) = f(^m)(f(^m+1)n (x)) (x)
これでうまくいくかな。
Ackermann関数の定義に似てる。
- 725 名前：１３２人目の素数さん ：03/10/28 00:10
- 定義する際は入れ子にせず、多変数関数として漸化式を書く方が分かり易いよ。例えば
f(^a)b(x)はf(a,b,x):=f(a-1,f(a,b-1,x),x)？
- 726 名前：682 ：03/10/28 12:53
- >>714
確かにふぃっしゅ関数とかもかなり理解が難しいし、
自分がやっているのもそれ以上に高度なネタだからね。
あとネスト関数の記号では>>724で正しいです。
まさにak関数と似てますね。
ちなみに２変数以上については
f(^n,1)b(x)=f(^n-1,f(^n,1)b-1(x))f(x)(x), f(^n,1)1(x)=f(x)
と言った感じか。これは
f(n→1→b)(x)=f(n-1→f(n→1→b-1)(x)→f(x))(x)のようにすればわかりやすいか？
>>725
わかりやすい表記法どうも。まさにアッカーマンそのものの感じですね。
- 727 名前：714 ：03/10/28 17:04
- >>726
そうなるんですか。
漸化式の形はチェーンと同じですね。
f(x)=axとすると
f(^d,c)b (1) = a→b→c→d
かな？
- 728 名前：714 ：03/10/28 18:24
- 今まで出てきた爆発的な関数を作る手続きの共通点について、
前から思ってたことがちょっとまとまってきたんで書いてみます。
もっと一般化できるかもしれない。
ふぃっしゅ数がこれでうまく表現できるかどうかも未検証だし。
f：N→N
W：Nと同型な部分集合を持つ整列集合（以下その部分集合とNを同一視する）
として、fをWからNへの部分関数とみなして超限帰納的に
φ：W-N → W s.t. φ(a)＜a (∀a∈W-N)
f(a)=f(φ(a))
（b＜aのときφの定義にf(b)の値を使ってもよい）
を定義すると、fをWからNへの関数に拡張できる。
Wは一般の整列集合としましたが、気持ちとしては
N^nに辞書式順序を入れたようなものを考えてます。
f(b)の値を使うってところはちゃんと書くと、
「W-NからWへの写像の族{ψ_λ}を
ψ_λ(a)＜aをみたす任意のものとするとき、
φ(a)の定義はf(ψ_λ(a))に依存してよい」
こんな感じですかね。。。
わざわざ分かりにくく書いてるようで嫌ですが。
- 729 名前：714 ：03/10/28 18:26
- 例えば・・・
f(x)=x+1、W=N^2(辞書式順序で整列)として{(0,n)|n∈N}をNとみなし、
φ(m,n)
|(m-1,1) (if n=0, m>0)
|(m-1,f(m,n-1)) (if n>0, m>0)
によってfを拡張して得られるのがakです。
ちなみにψ_λ((m,n))=(m,n-1)です。
- 730 名前：１３２人目の素数さん ：03/10/28 19:41
- アッカーマンって結局タワーより増加小さいんじゃなかったっけ？
- 731 名前：１３２人目の素数さん ：03/10/28 22:33
- >>717
だとすると、
s(n)変換から
ss…ｎ…ss(ｎ)変換
の過程で二重帰納からｎ重帰納になっていくってこと？
確か、根っ子の計算が二重帰納なら二重帰納の域を出ないという
意見はどうなるんでしょうか？
さらに
ss…ｎ…ss(ｎ)変換から
記号化が追いつかないｎ次元の変換
というように続いていくVer5はどうなるんだ？
>>730
たしかアッカーマンの方が大きいんじゃない
- 732 名前：701 ：03/10/29 00:28
- >>730
アッカーマンは
A(x+2,0)+3 = 2→3→x = 2↑↑…（↑がx個）…↑↑3
で表せるからxが1増えるごとにタワーが1増えるということで
タワーと同じ発散力だと思います。
ちなみにモーサー表記も同じでn[x]からn[x+1]になるとタワー1個ぶんの増加です。
- 733 名前：１３２人目の素数さん ：03/10/29 09:49
- >>716-717
ようやく３重帰納関数の威力が垣間見えて来たような…
乙です
- 734 名前： ◆KIs/plq/Ws ：03/10/29 12:10
- たびたびすいません。728の文章を理解するには、どこを参照すればよいのでしょうか？
特に「超限帰納的」と言う単語が初耳でして・・・
- 735 名前：714 ：03/10/29 13:00
- >>734
超限帰納的な定義というのは、
aより下での値を使ってaにおける値を定義すると
すべてのaで定義できるというような話です。
その理屈が成立するために必要なのが整列集合であるという条件です。
詳細は集合論の本に載ってると思います。
- 736 名前：682 ：03/10/29 17:26
- >>731
ふぃっしゅ関数のように何重も２重帰納を重ねて次元を上げれば
ここで取り上げた３項の３重帰納関数を超えられると思います。
ただ関数一つの範囲ではどの
２重帰納関数も３重帰納関数の増大率を
超えることはないようです。
ここで多重帰納を重ねた巨大関数を思いつきましたが、
その前に４重帰納の威力も少し説明。
A(w,x,y,z)
=A(A(w-1,x,A(A(w,x-1,y,z),@,@,z-1),z),A(w-1,x,A(A(w,x-1,y,z),@,@,z),z-1),z),y-1,z)
A(0,x,y,z)=A(0,x-1,y,z)
A(w,0,y,z)=A(w-1,0,A(w-1,0,A(A(w,0,y-1,z),A(w,0,y-1,z),A(w,0,y-1,z),z-1),z),z)
A(w,x,0,z)=A(w,x-1,w,z)A(w,x,y,0)=A(A(A(w-1,x,y),x,y-1)x-1,y)
として、
A(1,1,1,1)=A(A(0,1,A(A(1,0,1,1),@,@,0),1),@,0,1)
=A(A(0,1,A(gg(1),gg(1),gg(1),0),1),@,0,1)
=A(A(0,1,gg(g(108)),1),@,1)=A(A(gg(g(108)),1,gg(g(108)),0),0,A(gg(g(108)),1,gg(g(108)),0),1)
<=A(gg2(g(108)),0,gg2(g(108)),1)=A(gg2(g(108)),0,A(gg2(g(108))-1,0,A(...gg2(g(108))回...A(0,0,α,0)...),0),0)
>=A(...gg2(g(108))-1回...A(1,gg2(g(108)),gg2(g(108))-1)...)<=gg[gg2(g(108))-1](gg2(108))>=gg[gg2(g(107))](107)
α=A(0,0,A(A(1,0,0,1),A(1,0,0,1),A(1,0,0,1),0),1)=A(0,0,A(g(108),g(108),g(108),0),1)=gg2(g(108))
gg(a)=A(a,a,a)とおく。
- 737 名前：682 ：03/10/29 17:40
- 続いてA(1,1,1,2)では、
A(1,1,1,2)=A(A(0,1,A(A(1,0,1,2),@,@,1),2),@,0,2)
=A(A(0,1,A(A(1,1,1,1),@,@,1),2),@,0,2), Y=A(1,1,1,1)
=A(A(0,1,A(Y,Y,Y,1),2),@,0,2)
=A(A(A(Y,Y,Y,1),A(Y,Y,Y,1),A(Y,Y,Y,1),1),@,@,1), Y2=A(A(Y,Y,Y,1),A(Y,Y,Y,1),A(Y,Y,Y,1),1)
>=A(Y2,Y2,Y2,1)
というように、A(1,1,1,1)でもA^2(g(108),g(108),g(108))となり、
ss...A(g(108),@,@)...s(n)変換にもなり、
さらに右端が２になるとさらに次元を超えた増大率になる。
こうして、ｎ重帰納のｎを上げていくごとにどんどん次元が上がっていく。
- 738 名前：682 ：03/10/29 18:19
- ではn重帰納の威力を説明した所で本題に入っていこう。
従来のふいっしゅ関数が２重帰納関数を重ねて増大していくのに対し、
これはn重帰納のnの値を関数化して、増大していくことで
さらなる増大の次元を上げていくことになる。(いわゆるf(x)重帰納)
まず次のような多重(f(x)重)帰納関数を定義する。
A(a_1,a_2,...,a_n)=A(a_1,a_2-1,B_n-2,...,B_n-2)
B_[k+1]=A(a_1,...,a_[n-k+1],B_k,...,B_k)
B_2=A(a_1,...,a_[n-1],B_1), B_1=A(a_1-1,A(a_1,a_2,...,a_n-1),...,A(a_1,a_2,...,a_n-1))
A(a,b,...,f,0,h,...,n)=A(a,...,f-1,n,h,...,n)
A(0,b,...,n)=A(0,b,c-1,B_[n-2],...,B_[n-2])
A(0,...,m,n)=A(0,...,m-1,A(m,n-1)),A(0,...,m,0)=A(0,...,m-1,m)
A(0,...,n)=f_k(n)
A(a1,a2,...,an)=A[n](a), f_k+1(x)=a[x](x) (a1=a2=...=an=a)
a[x](x)の[x]は関数の変数の数である。
初期値f_0(x)にはx+1を入れる。項の数を変数とすることで、
変換を１回繰り返すごとにx重帰納のxの変数値が増加して対角化する。
次にf_1_k(x)をこのＡ関数で漸化式にして変換する。
f_1_1(x)=[f2]_[k-1](x), [f2]_1=x+1
A(0,...,x)=f_2_k(x), f_2_1=f_x(x)
f_2_[k+1](x)=A2(x_1,...,x_x)(x)=A2[x](x)
その次にf_2_1(x)=f_1_x(x)として、f_2_k(x)も同じように何回か変換する。
以降f_3_k(x),f_4_k(x),...と繰り返す。
f_n_1=f_[n-1]_x(x)
A(0,...,x)=f_n_k(x)
fn_k+1=An(x_1,...,x_x)=An[x](x)
- 739 名前：682 ：03/10/29 18:27
- 続き。
fn_k(x)まできたら、次は項を漸化式fの項を３つにしてf_2_1_1(x)=f_x_x(x)として、
以降f_2_1_2(x),...へとＡ関数の変換を繰り返す。
さらに項の数を増やして何回も変換を繰り返す。
f_1(x)=[fn+1]_x1_x2_..._ax(x)=[f(n+1)]{x}(x), (1<=n<k) [fk]_1=x+1
f_a_1_1(x)=[fn](a-1)_x_x(x)
...
f_2_1_...k個..._1(x)=[fn]_x_...k-1個..._x(x)
f_a_b_..._k_1_..._1(x)=f_a_b_..._k-1_x_..._x(x)
f_a_b_..._k(x)=A(0,...,x)
f_a_b_..._k+1(x)=A(x_1,...,x_x)=A[x](x)
f_x1_x2_..._xx(x)=f{x}(x)として、{x}は漸化式fの変数の個数。
[f2]_k(x)=f{x}(x)とおく。このとき[f2]_[k-1]をf_1(x)とおく。
つまり、[f2]漸化式は上のような過程を繰り返すものになる。
ここで[f2]_1(x)=x+1とおく。
こうして、ふぃっしゅ数のs(m,n)変換にあたる所を何回もＡ関数の変換を繰り返して
f漸化式の添え字の値を増やして次元を上げていく。
次はさらに[f2]漸化式の変数も増やして新たに[f3]漸化式を決めて
さらに[f4],[f5],...と次元を上げていくと増大の次元が急激に増大する。
- 740 名前：１３２人目の素数さん ：03/10/30 01:16
- これで、本当に二重帰納突破しｎ重帰納への道に入ったんでせうか？
だとしたら、久々の、驚異的に大きな展開
ぜひ頑張ってください！
当方は能力が低いので時間をかけてじっくり学ばさせてもらいます。
レギュラー陣にも又帰ってきて欲しいが‥‥‥‥。
- 741 名前：１３２人目の素数さん ：03/10/30 11:57
- >>717
A(1,n,m)で、すでにs(m-1,n)変換までいくというのは
たしかに驚異的。
一般にどんな二重帰納関数よりも大きいことを示すには、>>51の
たとえば、３重帰納法で定義される３変数関数 f(x,y,z)できれいな形
のものをつくってどの２重帰納法で定義されるyに関する関数よりも f(x_0,y,y)が
大きくなる、あるいはある y からさき大きくなるというようにつくれば、f(x,x,x)
がどの２重帰納法で定義される x に関する関数よりあるところからさき大きくなる
わけです。
といったところをうまく説明できればいいのだけれど、たしかに
>>716-717 の説明を見るとなんとなく分かったような気もするの
だけど、どうもまだすっきりしないなぁ。
- 742 名前：682 ：03/10/30 18:11
- 自分がf(x)重帰納で挑戦するとすれば他はどんな方法でやるのか楽しみだﾅ。
>>741
ただ従来のak関数とかに比べて違うところは、
A(0,y)=A(1,y-1)だったのが、A(0,y)=A(y,y-1)だというような所で、
これによってA(1,1,1)からかなり大きな数になったのだと思います。
あと２、３重帰納については、例えば原始帰納関数
A(a,b)=A(A(a,b-1),0), A(a,0)=fn(x) として、
f1(x)=a+1, f[n+1](x)=A(x,x) とすると、
fn(x)はak関数のような二重帰納関数になります。
つまり、このようにn重帰納関数を何重にも変換させると
いつかはn+1重帰納関数化にありえますが、
単一のn重帰納関数のそれ自体ではどれもn+1多重帰納関数を超えることはないことです。
あと訂正
738の下から６行目
A2(x_1,...,x_x)(x)=A2[x](x)→A(x_1,...,x_x)(x)=A[x](x)
739の５、６、８行目
f_1(x)=[fn+1]_x1_x2_..._ax(x)=[f(n+1)]{x}(x), (1<=n<k) [fk]_1=x+1
→f_1(x)=[f2]_x1_x2_..._ax(x)=[f2]{x}(x)
f_a_1_1(x)=f_(a-1)_x_x(x)
f_2_1_...k個..._1(x)=f_x_...k-1個..._x(x)
[fn]についてはもう少し後で説明ね。
- 743 名前： ◆KIs/plq/Ws ：03/10/30 19:50
- >>742
> ただ従来のak関数とかに比べて違うところは、
> A(0,y)=A(1,y-1)だったのが、A(0,y)=A(y,y-1)だというような所で、
ほう、アッカーマン的部分にも手を付けたんですね。
それならいっそA(0,y)=A(fn(y),y-1)みたいに
fn(x)を定義中に混ぜるときっと恐ろしい事になりましょう。
- 744 名前：714 ：03/10/30 23:16
- >>742
>A(0,y)=A(1,y-1)だったのが、A(0,y)=A(y,y-1)だというような所で
その違いは一見重要でないように見えるんですが。
というのも、例えばAをこんな風に定義します。
A(0,y) = y+1
A(x+1,0) = A(x,x+1) (akの場合ak(x,1))
A(x+1,y+1) = A(x,A(x+1,y))
これをakと比べてみます。
まず簡単な計算でA(0,y)=y+1<ak(1,y)=y+2となります。
つぎに、A(x-1,y)＜ak(x,y)と仮定すると
A(x,0)=A(x-1,x)＜ak(x,x)＜ak(x,ak(x,0))=ak(x,1)=ak(x+1,0)
で、あとはyに関する帰納法でA(x,y)＜ak(x+1,y)
となってしまうのですよ。
つまり第1引数を1増やすぐらいの違いすらないと。
むしろ項数を増やしたことの寄与のほうが
絶大な威力を持ってるということなんじゃないでしょうか。
- 745 名前：714 ：03/10/30 23:24
- う、なんか違う。
ak(x,ak(x,0))=ak(x+1,1)=ak(x+2,0)
ですか。じゃあA(x,y)＜ak(2x,y)ぐらいしかいえないか。
まあ、それにしてもそんなに寄与はしてなさそうな感じ。
- 746 名前：714 ：03/10/30 23:33
- まだ一箇所違ってた。
もうちょっと丁寧に検証しないといけませんね。
ak(x,ak(x,0))＜ak(x,ak(x+1,0))=ak(x+1,1)=ak(x+2,0)
です。
- 747 名前：714 ：03/10/31 00:12
- そうすると帰納法の仮定が変でした。
ダメですね。。。すいません。
また修正して、A(x,y)＜ak(x+1,y+1)にします。
A(x-1,y-1)＜ak(x,y)を仮定すると、
A(x,0)=A(x-1,x)＜ak(x,x+1)＜ak(x,ak(x+1,0))=ak(x+1,1)
y>0では漸化式の形が同じなので簡単な帰納法。
- 748 名前：１３２人目の素数さん ：03/11/01 00:32
- 携帯からカキコ。
昨日は忙しかったけど大学からしかネットできないので
次の火曜日まで出られなくてスマン。
ではまた。
- 749 名前：714 ：03/11/02 22:52
- >>744よりももうすこし大きい
A(0,y) = y+1
A(x+1,0) = A(x,x+1)
A(x+1,y+1) = A(x,A(x+1,y))
を計算してみたら、
A(x,y)≦ak(x^2,y)
となることがわかりました。
粗いといえば粗い評価かもしれない。
- 750 名前：682 ：03/11/04 17:57
- >>744-749
検証どうもお疲れです。
ちなみに748は自分のね。
確かにxとx^2との差は大きいようですね。
ちなみに３重帰納関数で
A(0,y,z)=A(1,y-1,z), A(x,0,z)=A(x,1,z-1), A(x,y,0)=ak(x,y)とおくと、
A(1,1,1)=A(A(A(0,1,1),@,0),0,1)=A(A(A(1,1,0),@,0),0,1)
=A(A(3,3,0),0,1)=A(61,0,1)=A(61,1,0)=A(A(60,1),0)=63
A(1,1,2)=A(A(A(0,1,2),@,1),0,2)
=A(A(A(1,1,1),@,1),0,2)=A(A(63,63,1),1,1)
A(63,63,1)=A(A(A(62,63,1),@,0),0,1)
=A(A(A(...63回...A(A(A(0,63,1),@,0),0,1)...),@,0),0,1)
=A(A(A(...63回...A(A(A(1,62,1),@,0),0,1)...),@,0),0,1)
=A(A(A(...125回...A(A(A(1,0,1),@,0),0,1)...),@,0),0,1)
=A(A(A(...125回...A(A(3,3,0),0,1)...),@,0),0,1)
=A(A(A(...124回...A(A(63,63,0),0,1)...),@,0),0,1)=g124(63)
となり、どちらも前のよりグンと小さくなります。
- 751 名前：682 ：03/11/04 18:16
- とりあえずn重帰納関数の次元増大について検証してみるか。
まず３重帰納関数がs(m,n)変換で表されるとして、その変換の回数をpとして、
s(m,n,p)=s(m,n-1,s(m,n,p-1))
s(m,1,p)=s(m-1,s(m,1,p-1),s(m,1,p-1))
s(m,n,1)=s(m,n-1,x)
s(m,1,1)=s(m-1,x,x)
s(n,p)=s(n-1,s(n,p-1))
と表される。つまり、s(1)変換p回をs_pとすると、s(n,p)(s(n)^p)変換は
B(0,p)=s_pのときのs(1)変換１回にあたる。(仮にs'(1)変換とおく)
そしてs(m,n)変換はそのs'(1)変換をm回していることになる。
つまりs(1)変換を２重にしているとみることができ、
これが３項３重帰納関数の正体になる。
- 752 名前：682 ：03/11/04 18:36
- 次に４重帰納関数では、
A(1,n,1,1)=A(A(A(A(n,n-1,1,1),@,@,0),@,0,1),n-1,1,1)
→A(a,a,a)変換(B(a,a)変換を３重帰納にしたもの。仮にs3(1)変換とおく。)
A(1,n,2,1)=A(A(A(A(0,n,2,1),@,@,0),@,0,1),n-1,2,1)→s3(n)変換
A(1,n,m,1)→s3(m-1,n)変換
となる。A(1,1,1,2)以降では
A(1,n,1,2)=A(A(A(A(n,n-1,1,2),@,@,1),@,0,2),n-1,1,2)
→A(a,a,a,1)変換(s3'(1)変換とおく)
A(1,m,n,2)→s3'(m,n)変換
A(1,n,m,x)→A(a,a,a,x-1)変換(s3''...x個...'(m,n)=s3(x,m,n)変換)
となり、３重帰納変換がx回重ねられる。
ちなみに５重帰納では４重帰納がx回重ねられたs4'(x)(l,m,n)変換になると思う。
こうしてn重帰納のnの値が増えると増加の次元も大幅に大きくなり、
ふぃっしゅ関数Ver5のm(n)変換もこれにつれて増加しているかもしれない。
もっともVer5のはほとんど理解できていませんが。
- 753 名前：714 ：03/11/04 20:15
- >>749
うわぁー間違ってる
これじゃ前のと同じじゃん・・・
誤 A(x+1,0) = A(x,x+1)
正 A(x+1,0) = A(x,A(x,x))
度々ｽﾐﾏｾﾝ・・・
- 754 名前：１３２人目の素数さん ：03/11/04 22:31
- >>752
もしもふぃっしゅ関数Ver5のm(n)がn重帰納的に増加すると
すれば、>>10 で f5(x) はx重帰納となってn重帰納を
超えてしまうわけか。
Ver5の理解をしないとはじまらないけど、そもそもVer5は
まだ作りかけだったような…>>10-11でいいのかな？
- 755 名前：682 ：03/11/05 17:09
- 先ほどの４重以上の帰納関数ですが
４重帰納は2*x段階の３重帰納、５重帰納は2*x*x段階の４重帰納を重ねて、
n重帰納では2*x^(n-3)段階のn-1重帰納を重ねていると思われます。
A(a1,a2,...,an)においてn重帰納変換をf(n)とおいて、
f(3)=(f(2)^xf)^xf(x)
f(4)=(f(3)^xf)^xf)...2*x回...)^xf(x)
f(n)=(f(n-1)^xf)^xf)...2*x^(n-3)回...)^xf(x)
となる感じです。
もちろんn多重帰納関数の変数がnより多いときにはこれより複雑になります。
- 756 名前：682 ：03/11/05 17:29
- 多重帰納関数をさらに改良してみた。まず３項関数においてA(x,y,z)=A(A(A(x-1,y,z),y-1,z), A(A(x-1,y,z),y-1,z),z-1)=A(A(A(x-1,y,z),y-1,z),0,z)＜A(A(A(x-1,y,z),y-1,z),y-1,z)
であり、これを発展させてネスト回数を利用して、
A(x,y,z)=A(A(B[B1],y-1,z),y-1,z)
Bn=A(A(B[n-1],y-1,z),y-1,z), B1=A(x-1,y,z)
A(0,y,z)=A(B[B1],y-1,z), B1=A(f(y),y-1,z)
A(x,0,z)=A(B[B1],B[B1],z-1),Bn=A(B[n-1],B[n-1],z-1),B1=A(f(x),f(x),z-1)
とする。ネスト回数までＡ関数なので従来のより爆発的に増大する。
これで多重帰納に多重帰納を重ねて同様の形で変数を増やしていけば
さらなる次元の高い変換も作れるかもしれない。
- 757 名前：682 ：03/11/05 17:46
- さらにもう一つ提案。
>>653での改良みたいだがNest変換をf(x)重帰納関数の変換に変えると
絶大な効果が得られるかもしれない。
>>738の手順の改良版かもしれないが。
とりあえず、多重帰納関数をA{m}(x1,...,xx)として、
{m}はその関数をm回変換することを意味するとする。
A{1}(0,...,x)=f(x)
A[f,x]=A{x}(x1,...,xx)
f_1(x)=A[f,x]
f_n(x)=A[f_[n-1],f_[n-1](x)]
f_1_1(x)=A[f_x,f_x(x)]
というようにして、
f_x_x_...x個..._x(x)まで来たらこれまでの手順をまとめて
[f2]_1(x)=A2[f,x]=f{x}_x_..._x(x), f_1(x)=f(x) ({x}は変換回数)
[f2]_2(x)=A2[f_1,f_1(x)]
とし、以降繰り返してAn[f,x]までいく。
A[f,x]に>>756の関数の多変数版を使ったらどうなるか。
- 758 名前： ◆KIs/plq/Ws ：03/11/05 18:03
- むー、どうしても式が見づらいなあ。
テキストでも入れ子関係がわかりやすい表記法を開発した方が良いかもなあ。
A(x,y,z)=
A( )=
A( ),A( ),z-1
A(x-1,y,z),y-1,z A(x-1,y,z),y-1,z
A( )＜
A( ),0,z
A(x-1,y,z),y-1,z
A( )
A( ),y-1,z
A(x-1,y,z),y-1,z
例えばこんな感じ？
- 759 名前：714 ：03/11/06 09:54
- A(x,y,z)=
A(
A(
A(x-1,y,z),
y-1,
z
),
A(
A(x-1,y,z),
y-1,
z
),
z-1
)
こんなんとか？行数多すぎるかも。
- 760 名前：682 ：03/11/06 16:47
- >>758
やはりそれだと行数が多くなるのが痛いですね。なら(),{},[],...と括弧の種類を増やすのがいいかな？
Ver5はまだ意味不明というほどの理解度だな・・・。
なら次元拡張も独自に作ってみよう。
次元拡張の一つに変換関数の変数を増やすのが最も単純だが、
その変数の集合をリストとして、さらにそのリストを増やして
別のリストにまとめるというのを繰り返す方法をとる。
例えば関数f[a](x)はaを変換(漸化式など)Ａを繰り返す回数とし、
f[a,b](x),f[a,b,c](x),...,f[a,...,n](x)と変数を増やして
>>653>>757と同じ要領でＡ変換を何度も繰り返す。
f[a,...,n](x)=f[L1,n](x)とおく。(nはリストの変数の数)
次にそのリストの外に別の変数を作り、f[a,[L1,n]](x)とし、
これをf[b,...,n](x)をa回繰り返す。(この手順をL1変換とおく。)
さらにリスト外の変数を増やしてL1変換を繰り返してf[[L1,n][L1,n]](x)となる。
さらにその[L1]を増やしてf[[L1]...n個...[L1]]でf[L2]とまとめる。
ここまでをL2変換とし、f[a,...,n,[L2]]で同様にL2変換を繰り返し、
f[L1][L2],f[[L1]...[L1]][L2]=f[L2][L2],...とさらにリストを増やして
f[L3]とまとめて、さらにf[L3]...[L3]=f[L4],...とリストの次元を上げて、
f[Ln-1]...[Ln-1]=f[Ln]とおく。
ここまで来たらものすごいと思うが、さらにその[Ln]のnの値の関数f(n)を
もとに上のリスト次元変換をしてさらにそれを繰り返していくと
次元がどんどん拡張される。
- 761 名前：682 ：03/11/06 17:15
- 多重帰納変換の増大率について改めて考察。
A(a,b,c)はs(1)変換を２重帰納変換にしたときのs(m,n)変換相当
A(a,b,c,d)はs(1)変換が３重帰納のときの
s'(m,n),s''(m,n),...,s'...n個...'(m,n)=s(l,m,n)変換相当
A(a1,a2,...,an)はs(1)変換がn-1重帰納のときのs(b1,b2,...,bn)変換相当
になるのかな。
- 762 名前：１３２人目の素数さん ：03/11/06 19:37
- >>58-59 >>63 にて Ver.5 の M(n) と
F(w1,x1,w2,x2,...,wi,xi;z)=F(w1-1,F(w1,x1-1,w2,x2,...,wi,xi,y,z),w1,x1-1,w2,x2,...,wi,xi;z) (w1,x1>0)
といった感じの多項漸化式が比較されているので、Ver.5 については
この漸化式との比較で考えると分かりやすくならないかな？
- 763 名前： ◆KIs/plq/Ws ：03/11/06 23:21
- こんなのはどうでしょうか
A(x,y,z)=A┬A┬A(x-1,y,z)
│ ├y-1
│ └ｚ
├＠
└z-1
書きづらいように見えるけどAAEを使えばかなり楽。
- 764 名前： ◆KIs/plq/Ws ：03/11/06 23:28
- なんとなく良さ気なので、いろいろ書いてみる。
とりあえず698に手を加えてみました。
A(x,0,0)=f(x)
A(0,y,z)=A(y,y-1,z) [z=0含む]
A(x,y,0)=A┬A(x-1,y,0)
├y-1
└0
A(0,0,z)=A(z,z,z-1)
A(x,0,z)=A┬A(x-1,0,z)
├@
└z-1
A(x,y,z)=A┬A┬A(x-1,y,z)
│ ├y-1
│ └z
├@
└z-1
こっちの方が698より大きく、かつ自然な拡張かと思いますがどうでしょう？
- 765 名前：682 ：03/11/07 17:46
- >>762
その漸化式は１回ごとに変数が増えていくのかな？
だとしたら本当に帰納的になるのかはわからないですね。普通に
F(w1,x1,w2,x2,...,wi,xi;z)=F(w1-1,F(w1,x1-1,w2,x2,...,wi,xi,y,z),w2,x2,...,wi,xi;z)
とかだったらわかる気もしますが。
そういえばプログラミングの配列表記にしてみると先ほどの
リスト構造はL[a][b]...[n]で表せますね。
１次元L[n]はf(a1,...,an)、２次元L[m][n]はf((a1,...,an),...,(m1,...,mn))
といった感じで。つまり各要素とリストの数を表しているだろうか。
これをさらに拡張してL[n]...[n]のリスト構造をL2[n][n]と表して
さらにL2[n]...[n]→L3[n][n]というような次元拡張もいいですね。
>>763
A(x,y,z)=A┬──A┬A(x-1,y,z)
└y-1,z└y-1,z
A(0,y,z)=┬──A(y,y-1,z)
└y-1,z
これならあまり行数とかも使わずにすむけどね。
こっちがさらに大きいです。同じ繰り返しになりますが。
- 766 名前：682 ：03/11/07 17:49
- あ、上のAAずれてしまった。欝だ・・・。
- 767 名前：１３２人目の素数さん ：03/11/07 20:52
- ほれ
http://aaesp.at.infoseek.co.jp/
- 768 名前：１３２人目の素数さん ：03/11/10 23:04
- >>765
引数として、多重にネストした list を許すならば、次のような関数が定義できます。
[ と ] をバランスよく並べた列を考えます。
例) [[[ ]]] とか [[[ ][ ]][ ]][[ ]][ ]
_list_ を上のような列としたとき、
A{_list_}(n) という関数を次のように定義します。
A{ε}(n)=n
A{_list_[ ]}(n)=A{_list_}(n+1)
A{_list1_[...[_list2_[ ]]...]}(n)=A{_list1_[...[_list2_]*(n+1)...]}(n+1)
(ただし、]...] の部分は ] だけの列)
ただし、εは空列、[_list_]*n は [_list_] を n 個並べた列です。
f(x)=A{[[...[ ]...]]}(x) ({} 内の列は x 重のネスト)
とおけば、f(x) は猛烈な速さで増加する関数であることが知られています。
hydra game とか Goodstein sequence で検索してみてください。
- 769 名前：682 ：03/11/11 19:43
- >>768
hydra game とかについては一応見ました。
いわゆるリスト階層を木で表して枝の数を１、２、・・・と増やして
いくもので、ここでは特定のリストを変数xでどんどん増やしていく関数ね。
さらにこの関数から同じリスト階層引数を使って同じように繰り返して
いく方法をとれば次元もどんどん上がるでしょう。
でも、A{_list_}(0)とかはどう定義すればいいのかな？
あといろいろ検索してみたら同じ巨大数で語っている面白いサイト発見！
ttp://www.bekkoame.ne.jp/ha/hc17910/short8.htm
これはak関数に極限順序数を用いたもので、>>60のHardy Functionの応用
だと思われるがこれだと今までここで出たどの関数よりも大きいようだ。
もちろんBB関数とかよりは小さいようだが。
ちなみに極限順序数とかはやっとだいたい理解できたところです。
- 770 名前： ◆KIs/plq/Ws ：03/11/12 01:31
- >>769
てゃんｋｓ！
・・・でも極限順序数についての説明はそこには無いのね。
ちょいと自力で調べてみましょう。時間はかかりますが。
- 771 名前：714 ：03/11/12 10:07
- 実はあんまりよく分かってなかったのでふぃっしゅ数Ver.1計算してみました。
http://briefcase.yahoo.co.jp/ring_hom
とりあえず適当に作ったプログラムと計算過程を記したdviファイルを置いときました。
プログラミングに関しては素人に近いので変なとこがあるかもしれませんが。
数日前からアクセス規制のため書き込めなくなってしまってます。
今はダイヤルアップで繋いで書いてますが、
解除されないようならここへのレスなども上のフォルダに置いとくかもしれません。
>>769
そりゃ、超限順序数使えばできるでしょ・・・と思いながら見てみましたが、
よく読んだら斬新なことをやってますね。
関数値まで超限数にしてしまうとは。
でもちゃんと定義できてるんでしょうか？
一番微妙なところが「対角化」の一言で済まされてしまってるようですが。
- 772 名前：714 ：03/11/13 10:05
- 解除されたようです。
こっちに書いときます。
>>769のリンク先にある関数ですが、何の定義もなしにAk(ω，ω，n)と書いてしまってますね。
Ak(ω, ω, 0)=2ω
Ak(ω, ω, 1)=ω^2
Ak(ω, ω, 2)=ω^ω
Ak(ω, ω, 3)=ε=ω^ω^ω^...
ということなのでしょうけど。
まあそれは筆者自身も不自然だとしているし、あんまりつつかないことにして、
P(k, 1, 1) = 2k,
P(k, n+1, 1) = 2P(k, n, 1),
P(k，1，z)= k,
P(m，n＋1，z) = P(P(m，n，z), P(m，n，z)，z−1) (z≦2)
ですが。
やっぱりzが極限数になるところでの定義がわかりません。
要は任意の極限数に対してそれに収束する順序数の列を取って
>>60と同じことをやるんだとは思いますが。
それが任意の順序数について取れるのかというと・・・よくわからない。
計算不可能云々の話が出ているので一般には取れないのかもしれません。
読んだ感じでは、
「一般には取れないけど具体的に極限数がひとつ与えられたら作れる」
というような感じを受けましたが。
しかもまた定義なしでP(ω, ω, n)なんて書いてあるし・・・
もしかして、P(k, m, n)のk, mに無理矢理ωを代入してしまうのか？
それならAkの時と変わらないような。
- 773 名前：714 ：03/11/13 10:29
- プログラム間違ってました
SS変換後の関数の計算のところでtmpは和ではなく積になります。
こんな感じで
tmp=1;
for(j=0;j<=i;++j){
tmp*=snd_component(j,fst_component(j));
}
- 774 名前：682 ：03/11/19 17:01
- 久しぶりにあげ。
>>772
確かにあそこのページの定義は説明不足でしょう。
でもやはり極限数での定義はそのとおりでいいと思いますね。
それにしても極限数とか使うのは何かと抽象的っぽいので
まずは見た目が単純なリスト拡張法で行きますか。
そろそろふぃっしゅ関数対抗の公式Ver.1発表していきます。
まず>>653のように
f(x)=x+1, [1]f(x)=N[f,x]=f^x(x)とおいて、
[n]f(x)=N[[n-1]f,x]
[n,x]f(x)=N[[n-1,x]f,x]
...
リスト２階層以上は次のように多重括弧で定義して
[[1],[1]]f(x)=N[[x1,...,xx]f,x]=N[[[x]]f,x]
[[[x1]],[[x2]],...,[[x]]]f(x)=[[[1],[1]]]f(x)
...
{[[...n回...[[x1]]...]],...,[[...n回...[xx]...]]}f(x)=[[...n+1回...[x]...]]f(x)
までいく。ここで初期値f(x)=x+1のとき[[...x回括弧...[x]...]]f(x)=L1[x+1,x]とおいて、
以降[2]f(x)=L1[[1]f,x],...と上の手順を繰り返して
[[...x+1...[1]...]]f(x)=L2[[[...x...[x]...]]f,x]までいったら
次はL3[x+1,x]で、以降繰り返しでLn[f'(x),x]まで次元を上げる。
ここでL63[x+1,3]を682の居住地の静岡県をとって
Ver.1の静岡数とでも名づけてみる(ｗ
- 775 名前：714 ：03/11/20 11:59
- >>774
[n]f(x)がだいたいak(n,x)ですね。
それ以降はよくわからないので順番に質問していきます。
>[n,x]f(x)=N[[n-1,x]f,x]
まずここから。
左辺の二つのxは同じxですか？それとも
[n,y]f(x)=N[[n-1,y]f,x]
と思っていいんでしょうか？
それからもうひとつ、n=0のときはどうするんでしょう。
[0,y]f(x)=[y]f(x)？
- 776 名前：714 ：03/11/20 12:04
- >>769のサイトに新たな記述が加わってましたが、
前からそんなようなことは何となく感じてました。
その辺がちょっと考えれば見えてしまうから
「巨大数をつくる」ということに関心を持つ人があまりいないのかな。
- 777 名前：682 ：03/11/20 12:39
- >>775
どうも失礼。
正しくは[n,x]f(x)=N[[n-1,x]f,x]ではなくて
[n,1]f(x)=N[[n-1,x]f,x], [n,y]f(x)=N[[n,y-1]f,x]でした。
あと[0,y]f(x)=[y]f(x), [0,x]f(x)=[1,1]f(x)でいいです。
それから２階層以上については
([x1,...,xx][x1,...,xx]...x...[x1,...,xx])f=([[x1]],...,[[xx]])f
→([1][[[1]]])f=[1][[0][0]...[0,...,1]]f(x)→[1][[0][0]...[0,...,2]]f(x)
というような感じで進んでいきます。
つまり上位階層リストの一つの要素を変えたりのリストを一つ増やしたりするだけで
想像以上の手間がかかるということです。
ちなみに[1,1][1]f(x)の段階ですでにx重帰納が対角化されていると思います。
- 778 名前：714 ：03/11/20 18:47
- >>777
>あと[0,y]f(x)=[y]f(x), [0,x]f(x)=[1,1]f(x)でいいです。
ここの二つ目の式は・・・？
今分かってるところをまとめると
[0]f(x)=f(x)
[n+1]f(x)=N[[n]f,x]
[0,n]f(x)=[n]f(x)
[m,0]f(x)=??
[m,n+1]f(x)=N[[m,n]f,x]
こんなところです。
- 779 名前：682 ：03/11/20 19:00
- >>778
おっと、正しくは[1,1]f(x)=N[[0,x]f,x]でしたね。またスマソ。
それから[m,0]f(x)は一応ありませぬ・・・。
あるとしたら[m,0]f(x)=[m-1,x]f(x)でしょうか。
- 780 名前：714 ：03/11/20 20:06
- >>779
じゃあこういうことですか
[0]f(x)=f(x)
[n+1]f(x)=N[[n]f,x]
[0,n]f(x)=[n]f(x)
[m,0]f(x)=[m-1,x]f(x)
[m,n+1]f(x)=N[[m,n]f,x]
nをどんどん減らしていって0になったときどうするか決めておかないと
定義できたことににならないので一応[m-1,x]f(x)と書いておきました。
まあ[m+1,1]f(x)=N[[m,x]f,x]でも同じです。
一般の場合も含めるとこんな感じですか？
[0]f(x)=f(x)
[x_1,...,x_n]f(x) = N[ [x_1,...,x_{n-1},x_n-1] f, x] (x_n>0)
[x_1,...,x_n,0,...,0]f(x) = N[ [x_1,...,x_{n-1},x_n-1,x,...,x] f, x] (x_n>0)
[0,x_1,...,x_n]f(x) = [x_1,...,x_{n-1},x_n-1]f(x)
- 781 名前：682 ：03/11/21 12:50
- >>780
>[x_1,...,x_n,0,...,0]f(x) = N[ [x_1,...,x_{n-1},x_n-1,x,...,x] f, x] (x_n>0)
>[0,x_1,...,x_n]f(x) = [x_1,...,x_{n-1},x_n-1]f(x)
正しくは
[x_1,...,x_n,0,...,1]f(x) = N[ [x_1,...,x_{n-1},x_n-1,x,...,x] f, x]
[0,x_1,...,x_n]f(x) = [x_1,...,x_{n-1},x_n]f(x)
です。
ちなみに一つ目のリストでの関数の増大率についての検証してみました。
[n]f(x)→原始帰納関数
[1,1]f(x)→２重帰納
[1,1,1]f(x)→３重帰納（たぶんs(1)変換の対角化だと思う）
[1,...n...,1]f(x)→n重帰納
二つ目のリストの一つ目の変数では
[[1][1]]f(x)→x重帰納
[[n][1]]f(x)→x重帰納変換n回
というような感じで増えていきます。
それ以降のもできたら調べてみます。
それから先ほどの３重帰納関数ですが、実は
s(1)変換の対角化にしかすぎないらしいです。
A(a,b,1)のはs(1)変換の２、３回目あたりだと思います。
もっともどっちにしてもn多重帰納関数は
s(a1,b2,...,an)変換に収まるものですが。
- 782 名前：１３２人目の素数さん ：03/11/21 19:32
- 素人にゃわけわからんな
- 783 名前：１３２人目の素数さん ：03/11/21 21:17
- >>781
じゃあ
ｓ(2)を対角化したs(3)変換が四重帰納法？
それとも
ｓ(n)を対角化したss(1)変換が四重帰納法？
だとすると
ss…(ｎ)…ss(ｎ)変換がｎ重帰納法？
- 784 名前：714 ：03/11/21 22:30
- >>781
そうですね、書き間違いでした。
[0]f(x)=f(x)
[x_1,...,x_n]f(x) = N[ [x_1,...,x_{n-1},x_n-1] f, x] (x_n>0)
[x_1,...,x_n,0,...,0]f(x) = [x_1,...,x_{n-1},x_n-1,x,...,x](x) (x_n>0)
[0,x_1,...,x_n]f(x) = [x_1,...,x_{n-1},x_n]f(x)
こんな風に理解しときます。
2階層以降はまだ全く理解できておりません。
まず>>774の
>[[1],[1]]f(x)=N[[x1,...,xx]f,x]=N[[[x]]f,x]
ここでいきなり出てきているx1,...,xnは何者ですか？
- 785 名前：714 ：03/11/21 22:32
- >>781
それから一応確認。
[n]f(x)が原始帰納だというのは、nを定数と見ているからですよね？
- 786 名前：682 ：03/11/21 23:30
- >>783
Ver1でいくとss...n...ss(n)(=s(n,n))変換を一回して、
h(x)=s(x,x)^xとおいて、さらにs(n,n)変換をx回繰り返した
ときが４重帰納法になると思います。
ちなみにVer2の場合はs(3)変換あたりで４重帰納法になり、
s(n)変換でn重帰納法になると思います。
(２回目からのs(2)変換での元の関数がg(x)=s(1)^xとなり、そこから
s(1)変換を繰り返す、というような変換だと思う)
>>784
x1とかxnはそのリストの変数の順序を示していて、n個変数があるという意味です。
[n]f(x)などのnは定数で、xは変数です。
あと２階層以上については大リストの外側別リストの変数が増えていくに
つれて、その大リストの中の小リストの数が増えていくという仕組みです。
外側リストの変数が１増えるのに大リスト内の変数増加の変換を繰り返す
という多大な手間をかけていく形です。
まあリスト階層はベクトルから行列、さらにそれを次元拡張した
テンソルというのを想像すればいいかもしれません。
- 787 名前：714 ：03/11/22 15:22
- 聞き方が悪かったのかな？
>>774の
>[[1],[1]]f(x)=N[[x1,...,xx]f,x]=N[[[x]]f,x]
この式は、何をどのように定義するといっているのですか？
- 788 名前：714 ：03/11/22 16:51
- 後で読み返したらなぜか偉そうな口調になっていることに気付く。
失礼しました。
- 789 名前：682 ：03/11/25 18:51
- >>787
忙しくて遅れてスマソ。
[x1,...,xx]=[[x]]ですが、
[[x]]は第１リストの変数の数と値がxだということを示して、
続いて[[[x]]]=[[x]][[x]]...x...[[x]]と第２リストx個を示し、
以降続いて[[...x...[x]...]]まで続くという意味になります。
- 790 名前：714 ：03/11/25 20:04
- つまり、まず
[^(n+1) x ]^(n+1) :=[^n x ]^n をx個並べたリスト
として帰納的に定義し
[ [^(n+1) 1 ]^(n+1), [^(n+1) 1 ]^(n+1) ] f(x):=N[ [^n x ]^n f,x]
と定義するのですか。
じゃあ一般に自然数x_1,x_2,...,x_nに対して、
[ [x_1],[x_2],...,[x_n] ]f(x),
[ [[x_1]],[[x_2]],...,[[x_n]] ]f(x), etc
も定義しなければならないわけですが、
これはどう定義されているのですか？
- 791 名前：682 ：03/11/26 10:43
- >>790
[ [^(n+1) 1 ]^(n+1), [^(n+1) 1 ]^(n+1) ] f(x):=N[ [^n x ]^n f,x]
だいたいその通りですね。
ちなみにここでの１は各階層のリストが一つで元の変数値も１という意味になります。
その次には
[ [^(n+1) 1 ]^(n+1), [^1 2 ]^1 ] f(x),
[ [^(n+1) 1 ]^(n+1), [^1 3 ]^1 ] f(x),...
[ [^(n+1) 1 ]^(n+1), [^1 1, 1 ]^1 ] f(x),...
[ [^(n+1) 1 ]^(n+1), [^2 1 ]^2, [^2 1 ]^2 ] f(x),...
[ [^(n+1) 1 ]^(n+1), [^n x ]^n ] f(x),
[ [^(n+1) 2 ]^(n+1), [^1 1 ]^1, [^1 1 ]^1 ] f(x),...
[ [^(n+1) 2 ]^(n+1), [^1 1 ]^1, [^n x ]^n ] f(x),
[ [^(n+1) 2 ]^(n+1), [^1 2 ]^1, [^1 1 ]^1 ] f(x),
[ [^(n+1) 2 ]^(n+1), [^n x ]^n, [^n x ]^n ] f(x),
[ [^(n+1) 3 ]^(n+1), [^1 1 ]^1, [^1 1 ]^1, [^1 1 ]^1 ] f(x),...
といった感じで増えていくのかな。
- 792 名前：714 ：03/11/27 11:29
- >>791
もしかして2階層以降の定義についてはまだ考案中ということですか。
>ちなみにここでの１は各階層のリストが一つで元の変数値も１という意味になります。
各階層のリストがひとつってどういう意味ですか？
それとこの表記だと、たとえば
[[2]]=[[2],[2]]
ですが、それでは[2]ひとつだけからなるリストはどう表せばよいのでしょう。
- 793 名前：714 ：03/11/27 11:42
- [[2]]=[2,2]ですね。
どっちにしても[2]ひとつのリストの表し方が･･･
- 794 名前：682 ：03/11/27 18:34
- >>793
[n]は[n]のままでいいです。
- 795 名前：１３２人目の素数さん ：03/11/30 00:04
- age
- 796 名前：682 ：03/12/02 16:49
- やはり[[x]]とかはわかりづらいですね。なら
[x1,x2,...,xx]f(x)=[L1]f(x), {[L1][L1]...x...[L1]}f(x)=[L2]f(x), ...
とでもしましょうか。これならなんとかわかると思いますが。
- 797 名前： ◆KIs/plq/Ws ：03/12/03 20:12
- OK、では具体的にいってみよう。
まず>>774から
f(x)=x+1
[1]f(x) = N[f,x] = f^x(x) （= f(f(f(…f(x)…))) （ｆがx回）でいいんですよね？）
[2]f(x) = N[[1]f,x] = [1]f^x(x) ( = [1]f([1]f(…[1]f(x)…)) [1]f がx回？）
[3]f(x) = N[[2]f,x] = [2]f^x(x)
……
次に>>777>>779から
[0,y]f(x)=[y]f(x)
[1,1]f(x) = N[[0,x]f,x] = [x]f^x(x)
[1,2]f(x) = N[[1,1]f,x] = [1,1]f^x(x)
[1,3]f(x) = N[[1,2]f,x] = [1,2]f^x(x)
……
[2,1]f(x) = N[[1,x]f,x] = [1,x]f^x(x)
[2,2]f(x) = N[[2,1]f,x] = [2,1]f^x(x)
……
そして>>780-781から
[0,x,y]f(x) = [x,y]f(x)
[1,0,1]f(x) = N[ [0,x,x]f,x ] = N[ [x,x]f,x ] = [x,x]f^x(x)
[1,0,2]f(x) = N[ [1,0,1]f,x ] = [1,0,1]f^x(x)
……
[1,1,1]f(x) = N[ [1,0,x]f,x ] = [1,0,x]f^x(x)
確認のため（四行目）一旦中止。
- 798 名前：１３２人目の素数さん ：03/12/07 00:11
- age
- 799 名前：１３２人目の素数さん ：03/12/07 02:04
- ところで巨大数探索スレッドも
５スレ目まできてるんですけど
今までで最も大きい数は結局何なんでしょうね？
- 800 名前：１３２人目の素数さん ：03/12/07 20:16
- >>1のルールを無視すれば後だしジャンケンを幾らでも出来る。
それよりはジャンケンに役立つ武器について考えた方がいい気が。
- 801 名前：１３２人目の素数さん ：03/12/12 23:15
- age
最近話題少ないなぁ･･･
- 802 名前：１３２人目の素数さん ：03/12/18 20:22
- age
長い間書き込みせずにスマソ。
例の静岡数のですがいろいろ検証とかしていくにはやはり
今までのよりかなり時間とかかかりそうです。
もしできたらまた書き込みます。
>>799
ふぃっしゅ数Ver5と自分で考えた静岡数と
どっちが大きいか気になるところです。
- 803 名前： ◆KIs/plq/Ws ：03/12/19 19:07
- >>802
お久しぶりです。
ところで>>797ですが、この段階でまだ間違いはないですかね？
ちなみに正しい場合、
[1]f(x) = (…((x+1)+1)…)+1 = x+x = 2x
[2]f(x) = 2(…(2(2x)…) = (2^x)x
[3]f(x) = ( 2^(…(2^(2^(2^x)x)(2^x)x)(2^(2^x)x)(2^x)x…) )(…(2^(2^(2^x)x)(2^x)x)(2^(2^x)x)(2^x)x…)
となります。
- 804 名前：１３２人目の素数さん ：03/12/21 17:50
- ところで禁じ手のBB(N)を使うとどのくらい大きくなるのだろうか？
誰も予想できないのは確実だが
BB(3)＝6なのでBB(BB(BB(3)))でふぃっしゅ数VER1を軽く抜いてしまうだろう
（ふぃっしゅ数がBB(10000〜10000000)程度という予想に基ついたもの）
今まで出てきたような増加方法でBB((…((の入れ子回数をs(1)変換の回数に例えてみたとして
わかりやすくしないと自分が理解できないので簡単な図にしてみる
ss(1)を（2.1） sss(1)を(3.1) sss(n)を(3.n)
sss…(n回)…sss(n)が(n.n）とする
さらに上位のｓ変換を位置付けて
s(1.1)が(1.1.1）で s(1.1.1）が(1.1.1.1）
以下表にすると
(1.1)→(1.n)↓ (1.1.1)→(1.n.n)↓・・・（1.1…(n回)…1.1)→(1.n.n…(n回)…n.n)↓
(2.1)→(2.n)↓ (2.1.1)→(2.n.n)↓・・・（2.1…(n回)…1.1)→(2.n.n…(n回)…n.n)↓
(3.1)→(3.n)↓ （3.1.1)→(3.n.n)↓・・・（3.1…(n回)…1.1)→(3.n.n…(n回)…n.n)↓
‥‥ ↓ ‥‥ ↓ ↓
(n.1)→(n.n) ↑ (n.1.1)→(n.n.n) ↑ （n.1…(n回)…1.1)→(n.n.n…(n回)…n.n）
- 805 名前：１３２人目の素数さん ：03/12/21 17:51
- 上記の流れを【1】として【1】の項数の増加を次の(1.1)→(1.n)で関数化すると同時に
上記の関数の流れをそのまま（1.1)→(1.n)のｎの増加にあてはめ、((1.1))→((1.ｎ))で表す
(1.1)→(1.n)↓ (1.1.1)→(1.n.n)↓・・・（1.1…(n回)…1.1)→(1.n.n…(n回)…n.n)↓
(2.1)→(2.n)↓ (2.1.1)→(2.n.n)↓・・・（2.1…(n回)…1.1)→(2.n.n…(n回)…n.n)↓
(3.1)→(3.n)↓ （3.1.1)→(3.n.n)↓・・・（3.1…(n回)…1.1)→(3.n.n…(n回)…n.n)↓
‥ ↓ ‥‥ ↓ ↓
(n.1)→(n.n) ↑ (n.1.1)→(n.n.n) ↑ （n.1…(n回)…1.1)→(n.n.n…(n回)…n.n）
の流れををｎ回(【1】終了時のｎの値)繰り返して((1.1))→((1.n))が終了
以下同様に
((1.1))→((1.n))↓ ((1.1.1))→((1.n.n))↓・・・((1.1…(n回)…1.1))→((1.n.n…(n回)…n.n))↓
((2.1))→((2.n))↓ ((2.1.1))→((2.n.n))↓・・・((2.1…(n回)…1.1))→((2.n.n…(n回)…n.n))↓
((3.1))→((3.n))↓ （(3.1.1))→((3.n.n))↓・・・((3.1…(n回)…1.1))→((3.n.n…(n回)…n.n))↓
‥‥ ↓ ‥‥ ↓ ↓
((n.1))→((n.n)) ↑ ((n.1.1))→((n.n.n)) ↑ ((n.1…(n回)…1.1))→((n.n.n…(n回)…n.n))
で【2】が終了 以下は【1】→【2】の関数の次元upと写像を【2】→【3】 【3】→【4】にも適用する
ただし【2】は想像を絶する巨大関数になっているので表記は不可能
【2】→【3】の流れは((((…((と括弧の数を増やしていく流れを【2】の巨大関数の流れに組み込んだもの
【ｎ】まで行って（ｎは【1】終了時の値）その値を【 】に入れるという繰り返しを
【ｎ】の値の回数だけ行う。これでどれくらいの数になるんだろう？
- 806 名前：１３２人目の素数さん ：03/12/21 18:33
- 【1】を((1.1))つまりs(1)にかけるとこがちょっと間違った
Ver2.3では
1 2
s(1)＾1 s(1)＾1(1) s(1)＾1(2)
s(1)＾2 s(1)＾2(1） s(1)＾2(2)
s(1)＾3 s(1)＾3(1） s(1)＾3(2)
…
s(1)＾n s(1)＾n(1） s(1)＾1(2)
なので、それに【1】をs(1)の変換回数にそのままあてはめて
1 2 ………………… n
((1.1))^1 【1】^1(1) 【1】^1(2)
((1.1))^2 【1】^2(1） 【1】^2(2)
((1.1))^3 【1】^3(1) 【1】^3(2)
…
((1.1))^n 【1】^n(1) 【1】^n(2) 【1】^n(n)＝((1.2))^1
というように【2】の内部で【1】は延々と連なり、
ひとつ前の段階の(n.n…［ｎ回］…n.n)の［ ］の項数を
増やしていくという構造です。
なので
- 807 名前：１３２人目の素数さん ：03/12/21 23:13
- BBは禁じ手ではないが、評価できないから、扱っても無駄
- 808 名前：１３２人目の素数さん ：03/12/21 23:17
- >>768がヒドラゲームの関数なら、どんな多重帰納関数をも上回っているな。
- 809 名前：１３２人目の素数さん ：03/12/29 15:15
- 2003年最後のageとなるか!?
- 810 名前：１３２人目の素数さん ：03/12/29 16:02
- 「巨大数」を定義教えてください。
- 811 名前：１３２人目の素数さん ：03/12/29 16:32
- 誰一人定義を分からずに適当な関数を作り上げていくｽﾚはここでつか？
- 812 名前： ◆KIs/plq/Ws ：03/12/29 17:57
- >>811
レスが欲しけりゃ３日待て。
有意義なレスなら３週間はかかる。
- 813 名前：１３２人目の素数さん ：03/12/29 18:07
- >>812
＞レスが欲しけりゃ３日待て。
＞有意義なレスなら３週間はかかる。
でも３重帰納法の定義は３年かかっても出てこない（ｗ
- 814 名前：１３２人目の素数さん ：04/01/05 18:14
- 仕事始めage(w
- 815 名前：１３２人目の素数さん ：04/01/10 01:08
- 0から積み上げるから遅いんじゃないの
無限大側から作ったらどうよ
- 816 名前： ◆KIs/plq/Ws ：04/01/10 16:34
- あけおめっす。
>>813
だね。そもそもｎ重帰納という言葉は数学用語としては使われていない様子。
巨大数スレで最初に２重帰納とか３重帰納とか言い出したのは確か・・・昔のスレの２６４氏
（１に書いてある「本日からこのスレでは〜」でおなじみの人)じゃなかったっけ？
まあでもみんな、変数が３つだとか、３重括弧を使ったとか言う意味で使ってるんじゃない？
>>815
いったいどうやるんだそれわ
- 817 名前： ◆KIs/plq/Ws ：04/01/10 17:36
- さて、よろっと７９７の続きをば。６８２さんからのご返事がありませんが、とりあえず勝手に肯定と解釈しまつ。
ここからは多重リストの世界。
[ [1],[1] ]f(x)=N[ [x1,...,xx]f,x ]=N[ [[x]]f,x ] (>>774)
これは789を参考にすると例えばx＝5のとき
[ [1],[1] ]f(5)=N[ [5,5,5,5,5]f,x ]=N[ [[5]]f,x ]
( [x1,...,xx]=[[x]]はむしろ[[x]]の定義とみるべきか？)
で、ここから[ [1],[2] ]f(x) , [ [1],[3] ]f(x) という風に進んでいくのでしょうか？ 例えば・・・
[ [1],[2] ]f(x) = N[ [ [1],[1] ]f,x ] = [ [1],[1] ]f^x(x) こんな感じ？
- 818 名前：１３２人目の素数さん ：04/01/12 11:36
- >>816
＞そもそもｎ重帰納という言葉は数学用語としては使われていない様子。
君が知らないだけ。
＞巨大数スレで最初に２重帰納とか３重帰納とか言い出したのは確か・・・昔のスレの２６４氏
＞（１に書いてある「本日からこのスレでは〜」でおなじみの人)じゃなかったっけ？
「本日からこのスレでは〜」といったのは、昔のスレの２６４氏とは別人というのは常識
それを認めないのはいった当人だけ。
- 819 名前：１３２人目の素数さん ：04/01/12 14:10
- >>818
そうだっけ？ 昔264に散々荒らされてた記憶が・・・まあいいか。
それよりも〜重帰納の定義を教えてもらえる？俺もはっきりとは知らないし。
- 820 名前：１３２人目の素数さん ：04/01/12 16:54
- >>819
＞〜重帰納の定義を教えてもらえる？俺もはっきりとは知らないし。
漏れも知らん（爆
ただ、アッカーマン関数が二重帰納的関数だというのは知られてるから
３重、４重、・・・とその上があるのは確か。
個人的には
(a1,b1)＜(a2,b2) （a1＜a2の場合）
(a1,b1)＜(a1,b2) （b1＜b2の場合）
というのは二重帰納法で、これを３つ、４つと増やせば
三重、四重になると思ってるが。
- 821 名前：682 ：04/01/13 12:36
- 今更ながらあけましておめ。
冬休みはいろいろ忙しくてカキコできずにスマン。
>>817
797のはあってます。
[x]f(x)段階でak関数レベル、[x,x]f(x)でs(1)レベルですね。
多重リストのもそういう解釈でいいでしょう。
ちなみに[[[x]]]=[[x]],[[x]],...,[[x]]といったような感じで。
というか[x1,...,xx]=[L1,x]、[L1,x],...x...,[L1,x]=[L2,x]
という表記ほうがわかりやすいですね。
＞n重帰納法
個人的にはA(a1,a2,...,an)=A(a1,...,a[n-1]-1,A(a1,...,an-1))
のようにak関数をn個に拡張したものがn重帰納関数だと思ってます。
つまりak関数A(a,a)を根にしたs1変換b回をA1(a,b)が３重帰納関数、
A1(a,a)を根にしたs2変換b回をA2(a,b)が４重帰納関数と続けて、
An-2(a,a)関数がs(n-2)変換a回のn多重帰納関数ということです。
- 822 名前：１３２人目の素数さん ：04/01/14 10:51
- ttp://www.geocities.co.jp/Technopolis/9946/function.html#tower
x↑↑1 = x↑x じゃなくて x↑↑1 = x かと。
x↑↑↑1 = x↑↑x なんかも同様。
- 823 名前：１３２人目の素数さん ：04/01/15 23:32
- age
- 824 名前：１３２人目の素数さん ：04/01/24 20:19
- age
- 825 名前：もやしっ子 ：04/01/28 02:24
- こぶさたですヽ(´ー｀)ノブックマークが死んでて更新に気が
つかないまま年を越してしまいましたヽ(´ー｀)ノあけおめ
サイトのタワー定義も直してません。申し訳ないっす。
相変わらずログ読む暇がないんですが、無責任に応援します。ワーワー
さて。
個人的には、n重帰納(n>2)という言葉はあまり考えなくてよいと思います。
そこの議論に終始してしまうと泥沼にはまります。実際いまだ
確実な定義に出合ってない訳ですから、どちらかといえば
既存の巨大数との比較検討をする方法論の話題の方が建設的なの
かなぁ、とか思ったりします。
もちろん作ったn重帰納関数がすげえ強くて、でもBBやヒドラにはかなわない
というのが理想ですが、やはり屋台骨が不透明では追い込んでも
徒労になってしまう可能性がありますし。大小比較しているうちになんか
妙なことが分かるかも…とか超無責任発言。
で、結局ふいっしゅver.3>>バード でいいんだっけ？(;´Д`)ど忘れ
- 826 名前：１３２人目の素数さん ：04/02/01 05:17
- 058
- 827 名前：１３２人目の素数さん ：04/02/07 19:27
- age
- 828 名前：木魚 ：04/02/29 17:09
- パート２で誰かが書いてたんだけど、
アッカーマン関数よりもその関数が呼び出される回数の方が発散力が強いというのを、具体的に計算してみた。
ソースはC++で。
int k;
A(int m, int n)
{
k++; //カウンター
if(m==0) //A(0,n)=
return n+1; // n+1
else if(n==0) //A(m,0)=
return A(m-1,1); // A(m-1,1)
else //A(m,n)=
return A(m-1,A(m,n-1)); // A(m-1,A(m,n-1))
}
A(m,n)が呼び出される回数をβ(m,n)とする。
まず、m=0の時は一回しかカウントされない
β(0,n) = 1
次に、A(1,n)=A(0,A(1,n-1)) より、
A(1,n)からA(0,A(1,n-1))に変換するのに１回、A(0,A(1,n-1))をA(1,n-1)+1に変換するのに１回、A(1,n-1)を具体的な数値に求めるまでにβ(1,n-1)回だから、
β(1,n)=β(1,n-1)+2
β(1,0)=2
となる。これを解くとβ(1,n)=2n+2となり、
同様にしてβ(2,n) = 2n^2+7n+5
β(3,n)=β(3,n-1)+2*2^(2n+4)-5*2^(n+3)+3 となり、
β(4,n)はどうなるのかさっぱりわからん。
で、ふぃっしゅ数の最初らへんで登場するA(3,3)なんだけど、これはβ(3,3) = 2432回になって、もうびっくりです。
ちなみにβ(4,1) = 2862984010となり、β(4,2)=1+2862984010+β(3,65533)となって、もうびっくりです。
これで、ふぃっしゅ数が出来るまでに最下層のB(0,n)が呼び出される回数なんかは少なくともふぃっしゅ数よりは大きいんだけど、もうそんな次元の話じゃないのかな。
- 829 名前：木魚 ：04/02/29 17:19
- ちなみに
アッカーマン関数を
A(0,n)=n+1
A(m,0)=A(m-1,1)
A(m,n)=A(m-1,A(m,n-1))
とするとき、
その呼び出される回数の関数は
β(0,n)=1
β(m,0)=1+β(m-1,1)
β(m,n)=1+β(m,n-1)+β(m-1,A(m,n-1))
となる(証明略)。
これの呼び出される回数の関数、それがまた呼び出される回数の…という感じで増やしていったら、また新しい巨大数が生まれるんじゃないかな。
- 830 名前：１３２人目の素数さん ：04/02/29 20:52
- なかなかよさげですね。
根っ子を強化するのは、その後の増加ｽﾋﾟ-ﾄﾞを考えると
けっこう意味があると思います
なんにせよ、久々の話題で楽しませてもらいました。
- 831 名前：１３２人目の素数さん ：04/03/03 20:54
- 前に書いてあった Peter の英語の本をちゃんと読めば、ｎ重帰納法
の定義も書いてあるよ。見つけ難いけどね。ただ前にも書いてあった
けど、その後研究があって見捨てられてるみたいだね。これも前に
書いてあったよ。
- 832 名前：１３２人目の素数さん ：04/03/03 22:55
- >前に書いてあった Peter の英語の本をちゃんと読めば、ｎ重帰納法
>の定義も書いてあるよ。
どの本？
俺は一冊図書館で読んだが、見つけられなかった。
>ただ前にも書いてあった
>けど、その後研究があって見捨てられてるみたいだね。
以前に（遊びだが）n重帰納の候補が何個も出てきた事等から推測するに、
定義の妥当性が欠如してるんじゃないかな。
専門家は本質的でないものを切り捨てる事には躊躇しないからね。
- 833 名前：１３２人目の素数さん ：04/03/03 23:05
- >>831
その、ｎ重帰納法の定義というものを一つかいつまんで説明してもらえませんか？
「書いてある」という人は今までにも何人かいるけど、まだ誰も書いてくれてないので、ぜひ。
- 834 名前：木魚 ：04/03/04 00:30
- 「n重帰納法」
http://www.google.com/search?q=%EF%BD%8E%E9%87%8D%E5%B8%B0%E7%B4%8D%E6%B3%95&ie=UTF-8&oe=UTF-8&hl=ja&lr=
いろいろありました。
- 835 名前：１３２人目の素数さん ：04/03/04 00:42
- >>834
その中では最もきちんと書いてある
www.dumbo.ai.kyutech.ac.jp/hirata/lecture/ computation/recursive_main.pdf
にも定義は無い。
- 836 名前：１３２人目の素数さん ：04/03/04 02:08
- Peterさんの論文に書いてある、て言うけど、その人が独自に使ってる用語なのかもよ。＞ｎ重帰納法
- 837 名前：１３２人目の素数さん ：04/03/04 02:53
- >>76 が定義を与えていると思うのだけれど、より簡明な定義の例。
H.E.Rose,
Subrecursion: functions and hierarchies, (Oxford logic guides 9),
Oxford University Press, 1984.
ISBN 0-19-853189-3
の pp.16--17 より
DEFINITION k-recursion. A function is k-recursive if it can be
defined using elementary functions and a finite number of k-recursions
given by the following scheme for φ,
φ(x,y_1,...,y_k)=0 if y_1・y_2・...・y_k=0
φ(x,y_1+1,...,y_k+1)=g(x,y_1,...,y_k,φ1,...,φk)
where for i=1,2,...,k, φi is given by
φi=φ(x,y_1+1,..,y_{i-1}+1,y_i,
f_1^i(x,y_1,...,y_k,φ(x,y_1+1,...,y_{k-1}+1,y_k)),
...
f_{k-i}^i(x,y_1,...,y_k,φ(x,y_1+1,...,y_{k-1}+1,y_k))),
and where g and f_j^i (j=1,2,...,k-i) have been defined previously.
- 838 名前：１３２人目の素数さん ：04/03/04 16:04
- サンクス。
しかし>>76の意を汲み取るとして、>>837はk-termでは無く2-termでは？
他にもいろいろな定義が考えられるんだが、それらは同値なんだろうか。
もし仮にそうなら、そこそこ意味のある概念と思う。
- 839 名前：１３２人目の素数さん ：04/03/04 22:59
- >>838 の引用の次から。
Peter has shown that a number of other nested schemes can be reduced to
k-recursion. We shall not give the details here. The readers is referred
to Peter(1957) for the two variable case and Peter(1936) for the general
case, ...
Peter(1936)
R. Peter, Uber die mehrfache Rekursion, Math. Ann. 113, 489--527.
Peter(1957) の英訳が次の本
R. Peter, Recursive Functions (3rd Ed.), Academic Press, (1967)
- 840 名前：１３２人目の素数さん ：04/03/05 04:31
- ９＾９＾９。
- 841 名前：１３２人目の素数さん ：04/03/05 07:40
- 76 の定義は「 f(x,y,0,a), f(x,0,z,a),f(0,y,z,a) が与えられていて」
っていうのの a が抜けてるみたいだけど、割合自然だから、それを
使うと、837,839 から推測すると Peter は76のような意味の k重帰納法
は 2-term だけを使った 837 の型の繰り返しに還元できるってことを証明
したのかな?
それに 76 の定義によるどの2 重帰納法で定義された関数も 181, 182 で定義
された関数を対角化したものの方が早く大きくなるってことは,どの原始
帰納関数より A(x,x) の方が早く大きくなることの証明みたいにやれば
いいんじゃないの? いままで76の定義は無視されていたのかな?
- 842 名前：↑ ：04/03/05 07:57
- 過去レス見れば分かるよ。
- 843 名前：１３２人目の素数さん ：04/03/05 13:20
- >>841
「関数を対角化」とは？
- 844 名前：１３２人目の素数さん ：04/03/05 21:53
- >>839
良い感じだけど、Ｐｅｔｅｒさん一人というのが、どうもね。
- 845 名前：１３２人目の素数さん ：04/03/05 22:28
- せめてWebのどこかに転がってるといいんだけど。
>>843
A(x_1,x_2,...,x_n)に対し、A(x,x,...,x)=B(x)なる新しい関数を定義すること・・・でいいんだっけ？
- 846 名前：１３２人目の素数さん ：04/03/05 22:37
- >>844
多重帰納関数についての基本的な定義と結果は Peter が全部やって
しまっただけのことです。
いちゃもんは Peter(1936) を検討してからにしてください。
- 847 名前：１３２人目の素数さん ：04/03/05 22:47
- >>846
そういうことではなくて、その結果を誰も引用したり
紹介したりしていないところが不思議だ、ということ
じゃないのかな。
なんでだろう。
- 848 名前：１３２人目の素数さん ：04/03/05 23:05
- 多重帰納関数について触れている本で Peter を引用していないものは、
見たことがないのですが。
Kleene の Introduction to metamathematics,
上に書いた Rose の本、
Odifreddi の Classical recursion theory, Part II
とか、代表的な本には Peter の仕事が引用されています。
- 849 名前：木魚 ：04/03/05 23:45
- 既出かもしれませんが、一応。
英語の翻訳サイトを見つけました。
http://www.excite.co.jp/world/
数学の論文を訳すために作られているわけではないので、
訳した結果はすこぶる読みにくいですがまあ無いよかマシかと。
- 850 名前：１３２人目の素数さん ：04/03/05 23:53
- 普通、本当に有用な概念は創始者に追随した多くの論文でより深められていくよね。
決して、We shall not give the details here.なんて歴史的記述程度の引用ではすまない。
- 851 名前：１３２人目の素数さん ：04/03/06 00:48
- >>837 が Peter の与えた k-recursion の定義。他にも、k-recursion の
定義はいろいろ考えられるが、それらはすべてこの定義に帰着できる。
この本では、k-recursion の性質を調べることに興味があるので、その他
大勢の定義を述べることや、帰着できることの証明は detail だと言って
いるだけでしょ。
k-recursion の定義が確立していると考えられているからこそ、detail
なわけ。
- 852 名前：１３２人目の素数さん ：04/03/06 01:36
- ところで、k-recursion＝ｋ重帰納 と考えて本当にいいのか？
- 853 名前：１３２人目の素数さん ：04/03/06 01:47
- >>851
なるほどなるほど。
やはり太鼓判を押してくれる人がいると、安心感が違うね。
- 854 名前：１３２人目の素数さん ：04/03/06 01:55
- さて>>76の段階ではk-termのkがｋ重帰納のｋと一致する事が、
重要であるかの様な誤解があった訳だけど、
結局は何termであっても良いのかな？
要は辞書式順序が入っているN^kの指数のkのみが重要と。
これ位の普遍性があれば、相当良い感じです。
- 855 名前：１３２人目の素数さん ：04/03/06 06:31
- >>76 の定義をその後の >>155 や >>854 の書き込みに従って書きかえると次
のようでよいのかな?
term の定義を変数記号と 0, x+1 から始めて普通のとおりとする。
a は変数の有限列の略。
f(0,y,z,a), f(x,0,z,a), f(x,y,0,a) が既に定義された 3重帰納関数で
f(x+1,y+1,z+1,a) は term で f 以外は既に 3重帰納関数で与えられてい
る関数の記号として f が現れるときは f(x,*,*,a), f(x+1,y,*,a),
f(x+1,y+1,z,a) のどれかであるという形である。
このとき f は 3重帰納関数を定義しているという。
このように k 重帰納関数を定義する。たとえば2 重帰納関数は3 のとき
の z がない形で定義する。そうすると >>837 の線では
1. k 重帰納関数は k-recursion の繰り返しで定義できる。
2. >>182 >>181 の
A(0,y,z) を良く知られた Ackerman 関数として
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)))
で A(x,y,z) を定義して、A(x,x,x) がどんな 2重帰納関数よりも早く
大きくなる。(1が示せれば 2-recursion でおきかえて示せばよい
わけであるけど。)
この2つを示すと多重帰納法に関する今までの疑問のかなりの部分
が解けるってことでしょうか?
- 856 名前：１３２人目の素数さん ：04/03/06 17:57
- 参考になるかどうか分からんが
k=1のとき
φ(x,0)=0
φ(x,y+1)=g(x,y,φ(x,y))
k=2のとき
φ(x,y,0)=φ(x,0,z)=0
φ(x,y+1,z+1)=g(x,y,z,φ1,φ2)
[ φ1=φ(x,y,f(x,y,z,φ(x,y+1,z))), φ2=φ(x,y+1,z) ]
・・・なんだかｘがちっとも働いてないように見えるのは気のせいか？
- 857 名前：１３２人目の素数さん ：04/03/06 18:23
- >>856
それは、そのとおりで気のせいではない。 855 の a に対応するパラメーター
の部分だから。
- 858 名前：１３２人目の素数さん ：04/03/07 11:07
- >>841
＞k重帰納法は 2-term だけを使った 837 の型の繰り返しに還元できる
>>855
＞1. k 重帰納関数は k-recursion の繰り返しで定義できる。
＞(1が示せれば 2-recursion でおきかえて示せばよいわけであるけど。)
どこをどう数えて"2-term"とか"2-recursion"とか
いってるのかわけわかめ。説明してみそ。
- 859 名前：１３２人目の素数さん ：04/03/07 11:12
- >>858
説明だけど、>>76は忘れて、>>837のk-recursionの定義だけから
k-recursionは2-recursionで置き換えられることを、具体的手順に
よって示してくれるかな。そこだけが重要だから。
- 860 名前：１３２人目の素数さん ：04/03/07 11:31
- そういやk重帰納に関するソースってどこよ？
Peterの論文だってことなら当然"k重帰納＝k-recursion"ってことになるんだろうけど、
837を見る限りでは、k-recursionは今まで俺らがイメージしてた「多重的な帰納法」とは違う気がする。
>>859
何質問者に要求してるんだ、おまいは。
- 861 名前：１３２人目の素数さん ：04/03/07 11:31
- >>859
>k-recursionは2-recursionで置き換えられる
これはありえない。この k は本質的だから。
>>858
2-recursion は 837 にある定義。しかし、この定義は k重帰納法と
いった場合のもっと一般的と感じられるものを含んでいるか不明。
そこで、76 の流れで自然な定義のものを考えて、837 の定義の繰り返し
に還元できることをいえばよかろうってこと。855 は 76 の流れの
なかでは一番一般的なものだから、これを k-recursion の繰り返しに
還元すれば 839 にかいてある Peter の結果の一部を証明したことに
なるだろうってこと。
- 862 名前：１３２人目の素数さん ：04/03/07 16:16
- 誤解しておられる方がいらっしゃるようだが、問題は
2-term k-recursion=任意term k-recursion。
kは固定しなくては無理。
- 863 名前：１３２人目の素数さん ：04/03/07 16:19
- >837を見る限りでは、k-recursionは今まで俺らがイメージしてた「多重的な帰納法」とは違う気がする。
では何が自然？
Ｎ＾ｋを使うあたりいかにもそれらしいと思うのだが。
- 864 名前：１３２人目の素数さん ：04/03/07 16:22
- 某日本語対応ターミナルについて語るスレはここですか?
- 865 名前：１３２人目の素数さん ：04/03/07 16:23
- >>855
より単純な
＞A(x+1,y+1,z+1) = A(x,A(x+1,y,z),A(x+1,y+1,z)))
では？
- 866 名前：１３２人目の素数さん ：04/03/07 17:56
- >>863
そういわれればそうなんだが・・・ほら、前から
「2重帰納をいくら繰り返しても3重帰納は超えられない」
とか言われてたじゃない？ それで、k重帰納＝k-recursionとして
837の定義を見てもほんとかよ？ と思ってしまうのよ。
- 867 名前：１３２人目の素数さん ：04/03/07 18:20
- >>865
それでもいいのかもしれないけど、まだ 855 の 1 の証明が終って
いない。つまり 866 の心配もあるから、855 の形のk 重帰納法
でも通用することがほぼ見える形になってるわけ。
ともかく 855 の A(x,y,z) が 837 の k-recursion の何回かで
書けることを示すことが Peter の結果にちかづくことなので
しょうか?
- 868 名前：１３２人目の素数さん ：04/03/07 21:36
- >>861
>>k-recursionは2-recursionで置き換えられる
>これはありえない。この k は本質的だから。
了解
>>862
>問題は2-term k-recursion=任意term k-recursion。
問題はtermの数でなくrecursionのオーダーじゃないだろうか？
つまりｋ重帰納法＝k-recursionとするなら、
2-recursionだけではkが3以上の関数を作れない
ことを>>866のような人に示すことではないだろうか？
- 869 名前：１３２人目の素数さん ：04/03/07 21:49
- どんな2-recursion関数よりも早く増加する
3-recursion関数(855のAでも他の関数でもよい）
があることを、ずばり対角線論法で示せないか？
- 870 名前：714 ：04/03/07 22:46
- 久しぶりに現れてみました。
>>837.の定義はそれっぽいのですが、ひとつ疑問が。
この定義では合成は認めてるんでしょうか？
つまりk重帰納的な関数の合成はまたk重帰納的であるということが
定義に含まれているのかどうかがはっきり分からないのですが。
- 871 名前：１３２人目の素数さん ：04/03/09 18:22
- >>870
837 の k-recursion をみれば極めて特殊な形をしているので当然
合成その他、原始帰納関数の定義で許されるものははいっていて
そのほかにこれを使ってよいということでしょう。
>>869
855 の1 の部分はよくわからないのですが、855 の A(x,y,z) が
855 の意味のどんな2重帰納関数(これは837を含むことは明らかです)
より早く大きくなることは、Ackermann 関数がどんな原始帰納関数
よりも早く大きくなることの証明マネすればよい形となっていると
思うのですが、、、。とくに、この証明を term の形で原始帰納関数
を定義しておけば、マネしやすいと思いますが。
- 872 名前：１３２人目の素数さん ：04/03/10 21:18
- >>871
じゃ、マネしてごらん。
Peterのk-recursionがｋ重帰納法であって
ｋ−１重帰納法より真に強いことが
君にも分かるだろう。
- 873 名前：１３２人目の素数さん ：04/03/11 00:00
- >>872には分からない模様（ｗ
- 874 名前：１３２人目の素数さん ：04/03/11 12:18
- またか
まあ、dat落ちするよりはたまに活性化してくれた方がいいけど
- 875 名前：１３２人目の素数さん ：04/03/12 08:50
- >>873には分からない模様（ｗ
- 876 名前：714 ：04/03/12 15:30
- >>871
確かに考えてみれば当然許されるはずですね。
そうでないとf(x)=x+2みたいなものも入らない。
- 877 名前：714 ：04/03/12 15:56
- とりあえず837の1-recが原始帰納関数を含むことの証明を試みました。
elementary functions とは定数、後者、射影関数と解釈しています。
nonzero(0)=0
nonzero(y+1)=1
とおくと1は定数関数だからこれは1-recであることに注意しときます。
f, hがすでに与えられたとし、原始帰納
ψ(x, 0)=f(x)
ψ(x, y+1)=h(x, y, ψ(x, y))
でψが定義されているものとします。
すると、φを1-recにより
φ(x, 0)=0
φ(x, y+1)=h(x, y, f(x))*(1-nonzero(y)) + h(x, y, φ(x, y))*nonzero(y)
と定義することで
ψ(x, y)=φ(x, y)+f(x)*(1-nonzero(y))
となります。
あとは足し算と1-x（x=1のとき0、それ以外で1となる関数）ができれば
x*0=0, x*(y+1)=(x*y)+x
で掛け算ができて証明完了なんですが。
- 878 名前：714 ：04/03/12 15:58
- >1-x（x=1のとき0、それ以外で1となる関数）
ここの書き方が変でしたが、
とにかくf(0)=1, f(1)=0 となる関数なら何でもいいです。
- 879 名前：714 ：04/03/12 23:39
- あれ、よく考えたら>>837の1-recでは非減少関数は作れない？
elementary functionsは非減少だし、
gが非減少なら
φ(x,0)=0
φ(x,y+1)=g(x,y,φ(x,y))
で定義されるφも非減少になります。
φ(0)=0≦φ(1).
あるy>0に対してφ(y)≧φ(y-1)とすると
φ(y+1)=g(y,φ(y))≧g(y-1, φ(y-1))=φ(y).
（簡単のためパラメータ省略しました）
原始帰納ならy=0の部分がいえないんですが・・・
φ(0)=0が効いてますね。
- 880 名前：１３２人目の素数さん ：04/03/14 01:39
- >>879
おお、ごめんなさい。これも定義を書いておくべきでした。
Rose の本で elementary function と言っているのは、次の class に
属する関数です。
the class of functions containing the successor, projection, zero,
addition, multiplication, and modified subtraction functions and
closed under composition and bounded sums and products
- 881 名前：714 ：04/03/14 11:16
- >>880
elementary functionsに含まれてたんですね。了解です。
じゃあ837の意味の1-recは原始帰納に含まれるということはよくて、
>>837の1-rec ⊂ >>855の1重帰納 ⊂ 原始帰納
だからk=1のときは>>855の1. は示せたのかな。
- 882 名前：１３２人目の素数さん ：04/03/15 08:19
- まずk重帰納法の定義のため：関数記号 f
1. 既にk重帰納関数となっている関数 g として g(y_1,...,y_m) は 0-term
g(*,...,*) で * は k-term で k の最大を i する。このとき
g(*,...,*)は i-term。
2. * は k-term で k の最大を i するとき f(x_1,*...*,a),
f(x_1+1,x_2,*...*,a),f(x_1+1,...,x_k,a) は i+1-term.
変数 x_1,...,x_k と a = (a_1,...,a_m) に対して原始帰納法を一般化したもの：
g,h は既にk重帰納関数であるもののとき
f(0,*...*,a) = g(*...*,a)
f(x_1+1,...,x_k+1,a) =
h(f(x_1,*...*,a),f(x_1+1,x_2,*...*,a),f(x_1+1,...,x_k,a),x_1,...,x_k,a)
ただし、* は k-1-term で変数記号は x_1,...x_k,a_1,...,a_m 以外にない。
とくに k=2 のときに着目し 855 の 3重帰納関数 A(x,y,z)について次のこと
を示す筋を書く。
「任意の 2重関数 f(x_1,...,x_n) に対して x_0 が存在し
x = max{ x_1,...,x_n } で x > x_0 なら f(x_1,...,x_n) < A(x,x,x)」
(続く)
- 883 名前：１３２人目の素数さん ：04/03/15 08:22
- (続き)
1. まず A(x,y,z)の単調増加性を示しておく。
2. 2重関数 f(x_1,...,x_n) に対して x_0 が存在し x = max{ x_1,...,x_n }
とすると f(x_1,...,x_n) < A(x_0,x,x) であることを2重帰納関数の定義
に関する帰納法で示す。
ここで2の証明のうち原始帰納関数に対する Ackermann 関数の場合の証明より
議論が複雑となる場所を指摘する。
f(0,y,a) = g(y,a)
f(x_1+1,x_2+1,a) = h(f(x_1,*,a),f(x_1+1,x_2,a),,x_1,...,x_k,a)
の * の部分に 1-term が現われる。この 1-term の一般形を考えておかない
と証明できない。これは 既に2重帰納関数となっている関数 g_1,g_2 として
g_1(f(x_1,g_2(x_1,x_2,a),a),f(x_1+1,x_2,a),x_1,x_2,a) となることを示し
ておく。この g,h,g_1,g_2 を使って x_0 を定める。k>2 についてk-重帰納関
数に関する結果をうるためには * の部分が複雑さを増すのでうまく用意をす
るかあるいは、Peter の結果 837 のような nesting が２回の場合に帰着でき
ることを使うとよい。
- 884 名前：１３２人目の素数さん ：04/03/24 18:46
- age
- 885 名前：１３２人目の素数さん ：04/03/24 19:34
- (loop (format "~A" #\9))
- 886 名前：１３２人目の素数さん ：04/03/27 23:05
- 「９を延々と書き続けるプログラム」
- 887 名前：１３２人目の素数さん ：04/03/29 01:55
- age
- 888 名前：１３２人目の素数さん ：04/03/31 15:40
- ってことは、>>182 の3 重帰納法で大体普通のやつよりは早く大きくなるって
ことなわけ?
- 889 名前：１３２人目の素数さん ：04/04/03 11:01
- もうすぐ、このｽﾚ１年
- 890 名前：１３２人目の素数さん ：04/04/03 14:44
- 初めてこのスレに来たけど、いま多重再帰法って
そんなに流行ってるの？それとも単に趣味的なだけ？
k-重再帰的函数やω-重再帰的函数は計算可能性の定義が
なされた時点で終わっちゃったと思ってたが。
- 891 名前：１３２人目の素数さん ：04/04/03 15:21
- ＞いま多重再帰法ってそんなに流行ってるの？
巨大数スレではリバイバルヒットしてるね。
そもそもここでやってることが、
k-重再帰的函数やω-重再帰的函数の構成
なんだよね。実は
- 892 名前：１３２人目の素数さん ：04/04/03 15:41
- そういう考え方では、ヒットは生まれない。
遊びと学問を要所で分離するセンスが必要。
多重再帰は、多分に遊びくさいにしても、ヒットにはならないだろう。
- 893 名前：１３２人目の素数さん ：04/04/03 15:55
- >>892
そういう考えでは遊べないよ。
学問は遊びなんだよ。遊び。
遊べる人が学問でヒットできる。
- 894 名前：１３２人目の素数さん ：04/04/03 16:02
- 脊髄反射ですなぁ
- 895 名前：１３２人目の素数さん ：04/04/03 16:05
- ＞学問は遊びなんだよ。遊び。
遊びは学問とは限らない。
＞遊べる人が学問でヒットできる。
このスレと関係ない発言は無意味。
- 896 名前：１３２人目の素数さん ：04/04/03 16:15
- >遊びと学問を要所で分離するセンスが必要。
マーチン・ガードナーとかだね。
- 897 名前：890 ：04/04/04 03:15
- 別に漏れは趣味でも遊びでも構わんと思うがね。
2chで必ずしも学問をしなけりゃいけないわけではない。
ただ学問的に意義深いことをやっていると勘違いすると
イタい目を見ることになると思う。
- 898 名前：スレの趣旨と外れてたらスイマセンね ：04/04/04 03:35
- このスレはでやっていることは巨大数の探索と言うより
急増化な自然数の上の函数の探索だね。まあ
大きな自然数は函数を作って定義するしかないから当然だが。
ときに、急増化函数が元々考えられたのはどういうご利益が
あるからだっけ？Ackermann函数は任意の原始再帰的函数を
追い越してくれるから、Ackermann函数自体は原始再帰的函数
でないことになって、明らかに計算可能な全域的函数で、
原始再帰的でないいい例となっているわけだが。
あと急増化函数はPAからの独立命題を作るときなどにも
一役買ってたと思うけど。Graham's NumberはGrahamがなにか
論文で使ったんだろうから組み合わせ論の役には立つんだろうが。
- 899 名前：１３２人目の素数さん ：04/04/04 04:32
- >2chで必ずしも学問をしなけりゃいけないわけではない。
>>892で言わんとしていることは、まさにそれ。
学問からうまく分離させないと、遊びとしてはヒットしない。
- 900 名前：１３２人目の素数さん ：04/04/04 07:40
- 900!and１年ｇｅｔ！
- 901 名前：１３２人目の素数さん ：04/04/04 10:14
- >>899
学問アレルギーのヒッキーですか？（ﾌﾟ
- 902 名前：１３２人目の素数さん ：04/04/04 11:10
- >>900
おみごと
- 903 名前：１３２人目の素数さん ：04/04/04 16:59
- >>901
煽りだろうが、念のために
「2chで」に注意
- 904 名前：１３２人目の素数さん ：04/04/07 11:45
- 結局 882,883 で n+1 重帰納的関数でどんな n 重帰納的関数より
早く大きくなるものが以前からあったものだったってことは終った
のかな?
- 905 名前：１３２人目の素数さん ：04/04/12 20:45
- まだ、チェインとスネ−ク以外のこと何も示されていないのに
もう終っちゃうの? どうなっての?
- 906 名前：１３２人目の素数さん ：04/04/13 20:04
- >>905
スネークの何が示されたって？
- 907 名前：１３２人目の素数さん ：04/04/13 20:15
- スネーク数はその概要すらろくに示されてないし。
ふぃっしゅ数がその名を残したのは何より作者がまめで
住人の質問にも丁寧に答えていたからだと言える。
この先、再びまめな人が現れない限りこのスレは休眠状態だろう。
- 908 名前：１３２人目の素数さん ：04/04/13 21:44
- 適当に漸化式でっち上げても、うけないのよ。
そゆこと。
- 909 名前：１３２人目の素数さん ：04/04/13 22:59
- ふぃっしゅ数が作者がまめで住人の質問にも丁寧に答えていたにも
かかわらず概要すら明らかにならなかった。
その理由として
１．作者の数学的レベルが高くなかった
２．住民の数学的レベルも高くなかった
ことがあげられる。
時たま数学的レベルが高い人がきても
理解されずに排斥される始末。
この先、レベルの低い住民が淘汰されないかぎり
このスレはダメだろう。そゆこと。
- 910 名前：１３２人目の素数さん ：04/04/13 23:06
- >>909
分からんことがあったら教えるぞ。
- 911 名前：１３２人目の素数さん ：04/04/14 00:13
- 松本真吾降臨か？（爆笑
- 912 名前：１３２人目の素数さん ：04/04/14 00:22
- ふぃっしゅ数を理解できない>>909って、
松本真吾さんっていうんですか？
- 913 名前：714 ：04/04/14 17:33
- 帰納的関数 共立講座 現代の数学
http://www.amazon.co.jp/exec/obidos/ASIN/4320011201/qid=1081930791/sr=1-9/ref=sr_1_10_9/249-0313927-8909963
まだ2章までしか読んでないけど、これ面白そうですよ。
- 914 名前：１３２人目の素数さん ：04/04/14 21:16
- >>910-912
マツシンヲタ一人で大暴れ(ﾜﾗ
- 915 名前：910 ：04/04/15 00:58
- 考えてみれば、何で巨大数を語るのに帰納的関数の知識が必要になったんだろう？
>>914
910≠911,912
はい残念。
- 916 名前：１３２人目の素数さん ：04/04/15 09:46
- >>915
898 に書いてあることじゃないの。
とくに、このスレッド5 の初めのほうで今までものが2 重帰納的関数
になっているという指摘があって帰納的関数の知識が必要だろうという
ことじゃないかな?
Knuth とか Conway がちょっと気軽に導入した記法を押し進めたって
のがスレッド4 までの流れだから、本格的に考えるのはちょっとつらい
んじゃないかなぁー。
- 917 名前：１３２人目の素数さん ：04/04/15 17:35
- >>916
>Knuth とか Conway がちょっと気軽に導入した記法を押し進めた
ふぃっしゅはもっとお気楽だったが。
910はなんかわかってるみたいだから聞いてみたら？。
多分いってることワケワカランで終りだろうけど。
- 918 名前：１３２人目の素数さん ：04/04/15 17:39
- 何が分からないのかさえ分からない917が聞いても無駄と思われｗ
- 919 名前：910 ：04/04/15 22:41
- >>916
KnuthはタワーでConwayはチェーンでしたかね、確か。
いずれにしても今まで出てきた関数はどれもAｃkermann関数の応用に過ぎないのでしょうね。
これまでと全く異なる手法で巨大数あるいは急増化関数が編み出されれば
このスレもまた盛り上がるのでしょうけど・・・。
>>917
909氏がふぃっしゅ数の概要が理解できないそうなので
それくらいなら教えられるだろうと言ったまでです。
・・・とは言ったものの、ふぃっしゅっしゅ氏の丁寧な説明でも理解できないとすると
そのような人に理解してもらうのはさすがに骨が折れそうな悪寒。
- 920 名前：１３２人目の素数さん ：04/04/15 23:03
- みんな909氏を馬鹿にしているみたいだけど、
初めの定式化の拙さもあって、
ふぃっしゅ数は確かに理解しずらいな。
そして、それを理解していく過程を楽しめた事が、
ふぃっしゅ数がうけた要因の一つだろう。
彼は>>892の意味でのセンスの持ち主だな。
- 921 名前：１３２人目の素数さん ：04/04/16 06:15
- >>920
彼って、ふぃっしゅ氏?
909 は馬鹿にされて当然だよ、
「この先、レベルの低い住民が淘汰されないかぎり
このスレはダメだろう。そゆこと。」 なんてのは話しにもならない。
レベルの低い人がいなくなったらスレッドはダメになる。大学の
セミナーだってよくできる人ばかりになったら、あまり集まらなく
なる。マツシンがよくも分かりもしないことを偉そうに振り回して
馬鹿にされるが、いい歳をしているのに、そのあたりさえ、わかって
いないのだから当然だ。
- 922 名前：もやしっ子 ：04/04/16 08:21
- 巨大数というものについて、誰かが好きな遊び方をすればいいと
思うんです。ここは少し宗教がかった公園みたいなもんだし。
自分などは「数式みたいなのを眺めて知った風な気分に浸り
ニヤニヤする」という人間の典型ですし、荒れたら荒れたで
それがまた楽しい場合もあります(´ー｀)うはは
- 923 名前：１３２人目の素数さん ：04/04/16 09:23
- >>921も妙なプライド捨てて、もやしっ子みたいになっちゃえば楽なんだけどね。
てゆーか、>>921って知ったかぶりっていう点ではマツシンと同じだよね。
なんてゆーか、知ったかぶりって反発しあうんだよね。
- 924 名前：１３２人目の素数さん ：04/04/16 09:29
- >>920はよく見てるね。
ふぃっしゅ数ってよくある竜頭蛇尾の典型だと思うわけ。
で、訳もわからず礼賛するヤシ貶すヤシと有象無象が
出てくるのが滑稽極まりないってのがこのスレの持ち味なわけ。
- 925 名前：１３２人目の素数さん ：04/04/16 11:50
- >>924
訳もわからず貶める輩しか見受けられないのだが。
そもそもふぃっしゅ数のどこが竜頭蛇尾の典型だと？
- 926 名前：１３２人目の素数さん ：04/04/16 14:47
- ふぃっしゅ数を理解できない事に対する心情が
「竜頭蛇尾」という言葉に良く表れているな。
- 927 名前：１３２人目の素数さん ：04/04/16 14:50
- 921氏も苛立ちすぎだなぁ。
まともに読解すれば彼＝ふぃっしゅ氏だろう。
- 928 名前：１３２人目の素数さん ：04/04/16 17:34
- なんか、やたらふぃっしゅを弁護するﾔｼがいるけど
もしかして、ｼﾞｻｸｼﾞｴﾝ？(藁
- 929 名前：１３２人目の素数さん ：04/04/16 18:35
- ９２８はふぃっしゅ数への評価とふぃっしゅっしゅ氏への評価を分離して考えられないようです。
- 930 名前：１３２人目の素数さん ：04/04/16 18:52
- ＞ふぃっしゅ数への評価とふぃっしゅっしゅ氏への評価を分離して考えられない
それは９２９のほうじゃない？
- 931 名前：１３２人目の素数さん ：04/04/16 19:38
- 909にしろ924にしろ、ふぃっしゅ氏を貶すやつって
根拠のないことばっかり言って反論にまともに答えようともしないのな。
でもって複数のレスがつくと決まって自作自演扱い(w
文句があるならきちんと筋道立てて説明したらいかがです、自称レベルの高い人。
- 932 名前：１３２人目の素数さん ：04/04/16 20:59
- しかし、それがあるからスレが活性化したという面もある。
今となっては、ときどき懐かしみつつ煽りあうことによって、
ようやくスレが保全されているというところか。
- 933 名前：１３２人目の素数さん ：04/04/16 21:50
- ふぃっしゅ氏のアイデアの面白いところは、
Ｎ
Ｎ＾Ｎ
（Ｎ＾Ｎ）＾（Ｎ＾Ｎ）
（（Ｎ＾Ｎ）＾（Ｎ＾Ｎ））＾（（Ｎ＾Ｎ）＾（Ｎ＾Ｎ））
・・・
と考える集合を変えていっている所にある。
このアイデア一発で、巨大数スレは５まで
盛り上がったといっても過言じゃないな。
- 934 名前：１３２人目の素数さん ：04/04/16 22:02
- 巨大数スレでマツシンが活躍中だぞ。
久々にほめられたと勘違いして、恥をかいて八つ当たりの様子（ｗ
- 935 名前：１３２人目の素数さん ：04/04/16 22:11
- 巨大数スレももう終わりだね。
934のようなカスばっかじゃね。
- 936 名前：１３２人目の素数さん ：04/04/16 23:07
- >>934
ここに書いてどうする。あんたも赤っ恥だな(w
- 937 名前：１３２人目の素数さん ：04/04/16 23:42
- F(n)=
(n^n^n^・・・計n個・・・^n^n^n)^(n^n^n^・・・計n個・・・^n^n^n)^(n^n^n^・・・計n個・・・^n^n^n)^
(n^n^n^・・・計n個・・・^n^n^n)^・・・計n個の(n^n^n^・・・計n個・・・^n^n^n)・・・^
(n^n^n^・・・計n個・・・^n^n^n)
こんな風にやっていけばあっという間にフィッシュ数超えちゃうじゃん。
少なくとも文字数を厳密に制限しないと。
- 938 名前：１３２人目の素数さん ：04/04/16 23:49
- ループｗ
- 939 名前：１３２人目の素数さん ：04/04/17 03:46
- >>937
あっという間というのは何文字？
- 940 名前：１３２人目の素数さん ：04/04/17 08:09
- 937 はその典型だが、今まででも、本当にどちらが早く大きくなるか？と
いうことの証明がされてるのは、同じ形式で定義される関数の間でしか
ないようだ。例えば、Ackermann 関数がどの原始帰納的関数より早く大きく
なることの証明を実行している人は少ないように思う。
882,883 で 182 の三重帰納的関数がどの二重帰納的関数より早く大きくなる
ことの証明の道筋が示されているが、この追証がされていないようだ。
大きくなる関数の定義形式の競争をするということより、定義の明確にある
関数を２つ与えてどちらが早く大きくなるか、証明を与えるということに目
を向けるのがよいかと思う。証明を与えることの練習として以下の問題を考
えるのはいかが。
単調増加つまり f(n)≦f(n+1) である自然数値関数 f で定数関数でなくなる
べくゆっくり大きくなるものをつくることを考える。このことと今までやって
いる早く大きくなる関数を探すというのは強く関係する。
単調増加関数 f について F_f(0) = f(0), F_f(n+1) = k, F_f(n) より f(k)
が本当に大きくなる最小を k とする。
与えられた g より F_f が早く大きくなるような f があることを示せ。また
f,g が単調増加で定数関数でなく、f の方がゆっくり大きくなれば F_f の方
が F_g より早く大きくなるか?
- 941 名前：１３２人目の素数さん ：04/04/17 09:15
- >>937
こういう初心者が来るのも宿命だが、いちおう言っておくと
そのやり方だと
Ｆ(ｎ)＝ｎ1
Ｆ(ｎ1)＝ｎ2
Ｆ(ｎ2)＝ｎ3
‥‥延々とやっていくと、けっこうでかい数にはなりますが
あなたが、言うように「あっと言う間」ではなく、もっと繰り返して
無量大数回この演算を続けたとしましょう、すると
Ｆ(ｎ無量大数)＝ｎM となります
でｎ＝無量大数としても、ｎMは、3↑↑↑↑3にさえはるか〜に及ばない
さらに、グラハム数にはもっと、もっと及ばないし
ふぃっしゅ数の入口のVer1には、問題外に及ばん というわけです。
- 942 名前：714 ：04/04/17 09:50
- >>940
帰納的関数の定義に従って書けばこういうことですか？
F_f(0)=f(0)
F_f(n+1)=G(F_f(n))
where
G(x) = x+μy.(1+f(x)-f(x+y))
（=min{ y | f(y)>f(x) }）
で、単純に考えて
f(n)=g([√n])などとすればF_fはF_gより速そうですが。
- 943 名前：714 ：04/04/17 11:00
- 関数srtをsrt(a)=[√a]で定義します。
一般にF_f(x)=min[ f^(-1)([f(0)+x,∞)) ] と書けることと
定義からf(0)=g(0)であることから
a≧F_f(x)
⇔ a∈f^(-1)([f(0)+x,∞))
⇔ f(a)≧f(0)+x
⇔ g(srt(a))≧f(0)+x=g(0)+x
⇔ srt(a)∈g^(-1)([g(0)+x,∞))
⇔ srt(a)≧F_g(x)
よってa≧F_f(x) ⇔ srt(a)≧F_g(x)が示せました。
aにF_f(x)とか(F_g(x)+1)^2を入れてみれば
F_f≒(F_g)^2となることが分かります。
- 944 名前：１３２人目の素数さん ：04/04/17 11:01
- >>942
よく問題を読んでください。そして問題は予想をすることでなく証明
することなのです。予想したらそれを証明することが、今までと違う
流れをつくるのではないか？という提案なのです。（G_f の定義は
そのとおりです。）
- 945 名前：１３２人目の素数さん ：04/04/17 11:54
- >>940
F_fというのも関数なのですか？
- 946 名前：１３２人目の素数さん ：04/04/17 12:56
- >よく問題を読んでください。そして問題は予想をすることでなく証明
>することなのです。予想したらそれを証明することが、今までと違う
>流れをつくるのではないか？という提案なのです。
すばらしい提案です。
以前、ふぃっしゅ関数が2（？）重帰納的等という
発言をされた方にも、ここを覗いておられるなら、
ぜひとも実行していただきたいですなぁ。
- 947 名前：１３２人目の素数さん ：04/04/17 13:04
- ＞単調増加関数 f について F_f(0) = f(0), F_f(n+1) = k, F_f(n) より f(k)
＞が本当に大きくなる最小を k とする。
g(n)からG(n)=g^n(0)を作る操作を、グラフの縦横ひっくり返した見たいね。
- 948 名前：１３２人目の素数さん ：04/04/17 13:42
- >>946
定義を見たとたんに計算ができるということがわかる関数の増大度は
たかが知れているという定理があるので、そういう問題を真面目にや
る人は少ないと思います。
- 949 名前：１３２人目の素数さん ：04/04/17 13:55
- それは、巨大数スレの否定ですね（笑
- 950 名前：１３２人目の素数さん ：04/04/17 14:06
- ＞定義を見たとたんに計算ができるということがわかる関数の増大度は
＞たかが知れているという定理があるので、そういう問題を真面目にや
＞る人は少ないと思います。
その定理を本当に理解してるなら、こんないい加減な紹介ではなく、
ふぃっしゅ関数はその仮定を満たすのか、その結果何が結論されるのか、
などもっと生産的な話をして下さいよ、先生。
- 951 名前：１３２人目の素数さん ：04/04/17 14:14
- >>948
それでも最低限、提唱したご本人は責任を持って証明していただかないと。
ところで
> 定義を見たとたんに計算ができるということがわかる関数の増大度はたかが知れているという定理
なんなんですか、このあいまい極まりない「定理」は。数学を馬鹿にしてるのですか？
- 952 名前：714 ：04/04/17 15:07
- >>943
>一般にF_f(x)=min[ f^(-1)([f(0)+x,∞)) ] と書けることと
なんか違う。
そもそもF_fの定義を読み違えていたようです。
- 953 名前：714 ：04/04/17 15:15
- で、>>942のGはこっちが正しいような気がしてきたんですが
G(x) = μy.(1+x-f(y)) =min { y | f(y)>x }
直感的には逆関数を合成したようなものになってるんでしょうか？
- 954 名前：１３２人目の素数さん ：04/04/17 20:43
- まず、>>7 について考えてみました。
有限列 s に関する原始帰納的関数を用意します。
(s)_i ：s の i 番目と (a\m)_i = a, i≦m ：長さ m の有限列など。
f_n(3,a,b,1) = a^b
f_n(3,a,b,2) = f_{n-1}(a, b\(a-2), b, b)
b>1,c>2 のとき
f_n(3,a,b,c) = f_n(3,a,f_n(3,a,b-1,c), c-1)
ここまでが初期状態 (3から始めている)。 f_{n-1} が2重帰納的関数なら
2重帰納的関数となっている。
k≧4 のとき
b=1 または c＝1 なら f_n(k,a,b,c) = a^b
b>1 かつ c>1 なら f_n(k,a,b,c) = f_n(k,a,f_n(k,a,b-1,c), c-1)
ここの形も2重帰納的関数の定義となっている。
7 の関数は f_n の a のところに有限列 a,b,...,x をかためてほうり込めば
えられる。
- 955 名前：714 ：04/04/17 21:29
- >>954
f_{n-1} が2重帰納的関数ならといっても、
そもそもf_{n-1}はnumeric functionではないんじゃないですか？
>f_n(3,a,b,2) = f_{n-1}(a, b\(a-2), b, b)
ここを見る限り任意の長さの有限列σに対して一斉に
f_{n-1}(σ)が定義されているという仮定があるように思えます。
それと第1変数のkが何のために存在しているのかよく分からないのですが・・・
- 956 名前：１３２人目の素数さん ：04/04/17 22:02
- >>955
帰納関数論で自然数の有限列がどのように自然数として扱えるか学んで
ください。
それがわからないと理解できないと思います。
- 957 名前：714 ：04/04/17 22:20
- >>956
そういうことですか。わかりました。
- 958 名前：１３２人目の素数さん ：04/04/18 00:31
- >>956
や、だからそういう態度をとられてしまうと議論がそこでストップしてしまうのですが・・・。
- 959 名前：１３２人目の素数さん ：04/04/18 00:50
- >>958
もう限界なんでしょう。
- 960 名前：１３２人目の素数さん ：04/04/18 00:52
- 一番肝心な部分を省略して証明とは・・・
- 961 名前：１３２人目の素数さん ：04/04/18 01:05
- f_nの最初のパラメータの意味とか、何で3から始めるのかとかぐらいは素人にも説明できそうなものだが。
- 962 名前：１３２人目の素数さん ：04/04/18 01:21
- >>961
教えてクンってウザイ
- 963 名前：１３２人目の素数さん ：04/04/18 01:54
- >>962
それはこういうときに言う台詞じゃないだろう・・・。
- 964 名前：１３２人目の素数さん ：04/04/18 07:37
- 954 は肝心なところを書いている証明なのですが、おわかりにならない方も
いらっしゃるようなので少し説明します。しかし自然数の有限列を自然数で
表したり、その数から元の有限列の要素を取り出したりすることが原始帰納的
関数でできることは帰納的関数に関することを書いてある数学の本のほとんど
に書いてあることなので説明しません。
まず >>7 にある ↑n は関数とはなっていないことに注意します。関数という
のは変数の個数が決まっているものです。そこで変数の個数についての情報
を k としていれて4 変数の関数を定義することにします。n = 1 の場合は
b\(a-2) に関するところがないので2重帰納的であることが明らかです。
k=3 からやっているのは 1,2 のときは 3以上に含まれているので不必要だ
からです。954の式は決して簡単な書き直しではありません。n を含んだ5
変数関数の定義としてみると3重帰納的であるという形ではなく、5重帰納的
であるという形となっています。つまり、元の ↑n(a,b,2) は複雑な要素を
含んでいるということなのでしょう。
有限列を使えば簡単に2重帰納法で表されるというわけではありません。7に
ある定義を見て前の部分のみ有限列としてまとめるから2重帰納的である
ことがわかるわけで、すべてをまとめてしまっては帰納的であることさえ定か
でなくなります。
このあと、ふぃっしゅ数に関することの証明をしようとすれば、定義を正確
に書いておくことが必要です。954 の証明でわかるように、概念や雰囲気だけ
では間違える要素が多くあるところのようです。
- 965 名前：１３２人目の素数さん ：04/04/18 10:40
- >>964
どもども。ありがとうございます。
- 966 名前：１３２人目の素数さん ：04/04/18 15:38
- ＞関数というのは変数の個数が決まっているものです。
＞そこで変数の個数についての情報を k としていれて4 変数の関数を定義することにします。
aの部分の変数の個数が、ｋによってコロコロ変わるようなものも、関数なのか？
情報が変数の一つに入っていれば良いなんて、変だぞ。
- 967 名前：１３２人目の素数さん ：04/04/18 15:54
- ＞自然数の有限列を自然数で
＞表したり、その数から元の有限列の要素を取り出したりすることが原始帰納的
＞関数でできることは帰納的関数に関することを書いてある数学の本のほとんど
＞に書いてあることなので説明しません。
素数列p_nを取って、
N^n∋(x_1,x_2,...,x_n)→p_1^x_1*p_2^x_2*...*p_n^x_n∈N
とする、という事だろうが、しかしnも変化させる時、
これを原始帰納的「関数」と捉えて良い？
- 968 名前：１３２人目の素数さん ：04/04/18 16:03
- ＞このあと、ふぃっしゅ数に関することの証明をしようとすれば、定義を正確
＞に書いておくことが必要です。
どれをふぃっしゅ数というのか、よく知りませんが、
少なくとも>>10-12は正確な定義でしょう。
- 969 名前：１３２人目の素数さん ：04/04/18 16:17
- >>968
分からないのにくいさがる馬鹿ってウザイ
- 970 名前：１３２人目の素数さん ：04/04/18 16:19
- 君、10-12がわからないの？
- 971 名前：714 ：04/04/18 20:46
- >>966>>967
おそらく両氏の疑問は同じところにあるのだと思いますが
>N^n∋(x_1,x_2,...,x_n)→p_1^x_1*p_2^x_2*...*p_n^x_n∈N
みたいな"写像"を考えて自然数の話に帰着するのではなく、
自然数列を扱う代わりにそのコード化である自然数を扱うという話です。
ゲーデル数みたいに。
あんまりうまく説明できないんですが、
何か一つ例を出すとわかりやすいかもしれません。
ちょっと考えてみます。
- 972 名前：１３２人目の素数さん ：04/04/18 21:09
- 自然数上の原始帰納関数 ( )_i, *, lh 等が存在し、
>>967 にあるコーディングの下で、lh は有限列の長さ、
* は列の連結、( )_i は列の第 i 成分等を表すことが
わかる。
これは、自然数とこれらの原始帰納関数のなるカテゴリーが
自然数の有限列全体と有限列を扱う基本的な演算のカテゴリー
と同型となることを意味している。
だから、自然数の有限列上の関数 f についての議論は、上の
同型で対応する自然数上の関数 g についての議論に帰着できる。
- 973 名前：１３２人目の素数さん ：04/04/18 22:27
- >これは、自然数とこれらの原始帰納関数のなるカテゴリーが
>自然数の有限列全体と有限列を扱う基本的な演算のカテゴリー
>と同型となることを意味している。
圏１：対象はN一つ、Hom(N,N)は原始帰納関数全部
圏２：対象は自然数の有限列の成す集合X一つ、Hom(X,X)は原始帰納関数（？）全部
この二つの圏が同型というのは、良いんだろうけど、問題はHom(X,X)の定義が、
先に与えられるのか、あるいはHom(N,N)を用いて定義するのか、
後者の場合はN^nの時の定義とうまくかみ合うのか？
といった疑問が>>966-967の正体だと思う。
- 974 名前：１３２人目の素数さん ：04/04/18 23:01
- > 問題はHom(X,X)の定義が、先に与えられるのか、
> あるいはHom(N,N)を用いて定義するのか
お好きならば、自然数と自然数の有限列からなる 2-sort の
カテゴリーを定義して、その上の原始帰納関数の理論を作れば
同時に解決できますよ。
問題になるのは X 上の基本操作に対応する関数と、N の元 n
に対し、n からなる長さ 1 の列を対応させる関数、それと X
上の列の長さに関する原始帰納法による関数の定義だけでしょ。
> 後者の場合はN^nの時の定義とうまくかみ合うのか？
( )_i, *, lh 等が原始帰納関数なのだから、これはあたりまえ。
- 975 名前：１３２人目の素数さん ：04/04/19 07:16
- どうもすみません。よくみたら >>954 には書き間違いがあります。
967,974で使われている記法は普通のようなのでそれを使います。
まず k≧4 のときですが、b=1 または c=1 のときというのが具合が
わるいです。そのときは、まず
a が長さ k-2 の有限列のコードでないとき、f_n(k,a,b,c) = 1。
これは b,c の値に無関係にそう定義します。
a が長さ k の有限列のコードであるときで、
b=1 または c=1 のとき f_n(k,a,b,c) = f_n(k-1,a',(a)_k,b)
ただし、a'*(a)_k = a 。
b>1 かつ c>1 のときは前と同じで
f_n(k,a,b,c) = f_n(k,a,f_n(k,a,b-1,c),c-1)。
その結果というと変ですが、f_n(3,a,b,c) でも長さ 1 の有限列の
コードとやったほうが整合性があると思います。しかし、準備を
しっかりしないと中々大変なもんですね。
さてそうすると、これは n = 1 のときはほぼ >>7 のままとして、
2 重帰納法 ですが n が 2 以上では 2重帰納法には見えませんね。
4重帰納法となっていることは形からわかります。a' は a より
小さいから、3重帰納法とはなっていると予想できますが、証明を
する必要がありますね。証明することを提案したので、954を書き
ましたがとても勉強になりますね。
- 976 名前：１３２人目の素数さん ：04/04/20 20:52
- 964 に書きましたが↑n は >>7 で何変数の関数として定義されている
のでしょうか? この定義域が自然数の有限列全体とするならば、その後
>>10 で1 変数の自然数に関する関数として許されるものは何なんで
しょうか? このあたりをはっきりさせないと色々なことの証明は進まない
と思います。>>966 >>967 の疑問はむしろ >>7 に向かうべきなのでは
ないでしょうか? そして、自然数の有限列を自然数で表すというのはむしろ
>>7 の時点でなされることにより、自然数上の関数として定義され、既存
の帰納的関数論とのつながりもはっきりすると思います。
- 977 名前：１３２人目の素数さん ：04/04/20 21:30
- >だから、自然数の有限列上の関数 f についての議論は、上の
>同型で対応する自然数上の関数 g についての議論に帰着できる。
あまり安心できていないのだけど、
例えば>>967の記号の元でg(n)=(p_1p_2...p_n)^nとすると、
これが原始帰納的であることは、
>>972ではどう保証されるのでしょうか？
これは有限列上の関数fからg(n)=f(n,n,...,n)(n個)を
作る事を意識しての質問ですが。
- 978 名前：１３２人目の素数さん ：04/04/20 21:48
- >>>966 >>967 の疑問はむしろ >>7 に向かうべきなのでは
>ないでしょうか?
>>966は、>>964の
>関数というのは変数の個数が決まっているものです。
というご説明を受けての事と思われます。
関数という言葉で、帰納的関数を意味するのは、方言ですので。
もっとも、↑n(a,b,...,x,y,z)は↑n((a,b,...,x,y,z))とするのが良いとは思いますが。
>>954は、すでに↑nとは定義域の別の関数を考察している（aは自然数）、
と理解していますが、その場合a\mは自然数列ではなく(p_1p_2...p_m)^aですか。
安心できればいいんですが。
- 979 名前：１３２人目の素数さん ：04/04/20 22:08
- >>977
972 を書いたわけではないのですが、まず、n 番目の素数を対応
させる関数として p_n は原始帰納的です、これは極めて多くの本
に書いてあります。ですから g(n) が原始帰納的であることは成立
しています。また、今まで書かれているように有限列のコードが
原始帰納的関数でなされることを使い、↑n((a,b,...,x,y,z))
とされるのであれば、これ自然数から自然数への1 変数関数として
しますのが後のなながりをよくすると思います。
a\m は自然数列のコードですから、コードの仕方が p_n を使うのなら
954 はまさしくそれを使っているのです。954 + 975 はすべてを自然数
に関する4 変数関数でなされるため、良く知られている、自然数の
有限列コードを使おうといっているのです。ですから >>971 の説明は
適切だと思います。
- 980 名前：１３２人目の素数さん ：04/04/20 22:30
- >>976
↑n は >>7 で何変数の関数として定義されている
のでしょうか?
変数の数自体が可変、あるいは任意長の関数ということだと思う。
- 981 名前：１３２人目の素数さん ：04/04/21 03:27
- >>>10 で1 変数の自然数に関する関数として許されるものは何なんで
>しょうか? このあたりをはっきりさせないと色々なことの証明は進まない
>と思います。
それは定義の問題ではありませんので、
例えば帰納的関数の枠組みで取り扱う必要のある方なら、
帰納的関数として十分か（即ち以後の定義に支障はないか）？
など考えられると良いと思います。
予想するだけなら、帰納的関数として十分な気はしますが、
なにぶんコード化さえ最近知った所で、証明は手に余ります。
- 982 名前：714 ：04/04/21 12:36
- 列の長さの情報はlh(a)という形でaに含まれているものと考えれば
kは必ずしも必要ではないんじゃないかという気がしてきましたが、
やっぱり必要なんでしょうか？
一応3変数でそれらしい定義を書いてみたのですが
確信がもてないのでもうちょっと検証してみます。
- 983 名前：１３２人目の素数さん ：04/04/21 21:48
- >>982
とくに必要というわけではなく、↑n から関数を定義する際、変数の個数
を指定すべきであるという観点で、対応が見えやすいという理由でした。
↑n を使って定義する関数が最終的に n を含んだ関数とするなら、必要
ないと思います。
目標は、この関数が4 重帰納的あるいは5 重帰納的であることを明確に
すること。>>10 のやり方が原始帰納法で置き換えられるということを
示すといった2 点であろうと思います。
n 重帰納的であることを示すために、原始帰納的であることを示すときに
使う補題を用意しておかないで直接示すのはやっかいかもしれません。
- 984 名前：１３２人目の素数さん ：04/04/22 21:48
- ９８４。
- 985 名前：１３２人目の素数さん ：04/04/22 22:29
- ふぃっしゅ関数のバージョンが6以降も無限に拡張できるとしたら
ヴァージョン番号を引き数にとる関数を作ればふぃっしゅ関数が生成する数を
こえる巨大数を生成する関数ができるじゃん
ふぃっしゅ関数ヴァージョン1〜nをF1(x)〜Fn(x)とすると
FF(x,1) = F1(x)
FF(x,2) = F2(x)
FF(x,3) = F3(x)
FF(x,4) = F4(x)
FF(x,5) = F5(x)
・
・
・
FF(x,n) = Fn(x)
G(x) = FF(FF(x,x),FF(x,x))
てなぐあいにね
- 986 名前：１３２人目の素数さん ：04/04/22 22:57
- 任意の数に対して任意の関数または任意の演算子を任意の回数くり返して
導出された関数または演算子のヴァージョン番号に自然数を対応させてせれば
そのバージョン番号を引き数とする関数または演算子を定義することにより
その引き数に導出した関数または演算子を任意の回数入れ子にすることによって
いくらでも次元を超越する巨大数を生成する関数を導き出せますよね
よって、キリがない。
- 987 名前：１３２人目の素数さん ：04/04/22 23:50
- >>985
その考え方は素晴らしい考え方だ！ >>1 の一番はじめの書いてある
「前の数＋１」というのと本質的に変わらない！と思えれば、
あなたは数学者への道を歩んでいる！なんちゃって。
- 988 名前：１３２人目の素数さん ：04/04/22 23:52
- >>985
>ふぃっしゅ関数のバージョンが6以降も無限に拡張できるとしたら
とか言ってる時点で、意味の無い発言ですな。
- 989 名前：１３２人目の素数さん ：04/04/23 01:25
- >>985-986
Ver5及び6自体がそういう感じの関数じゃないの？
もっとも、985のような、いい加減な定義ではないけど
- 990 名前：１３２人目の素数さん ：04/04/23 11:54
- >>989
Ver.5はまだできてない、はず。
というか、ver.4がどんなのだったかも記憶にないのだが。
- 991 名前：１３２人目の素数さん ：04/04/23 13:09
- Ver.5を作ろうとして、帰納関数のところで話が混乱してそのままになっている、といった感じだったかな。
- 992 名前：１３２人目の素数さん ：04/04/23 13:20
- てゆうか早くVer.5完成させてください。
- 993 名前：１３２人目の素数さん ：04/04/23 13:31
- つうかアッカーマン関数やタワー演算子がすでにその演算子のバージョンを
引き数にとってシステムを増大させているわけだから、>>987の言っている
『「前の数＋１」というのと本質的に変わらない』
ということなってしまう。
そうするとこのスレで議論していること自体が
スレの前提条件と矛盾したことになるのでは？
- 994 名前：１３２人目の素数さん ：04/04/23 15:58
- ※種関数f(x,n)を決める。
※定義したい定義番号kを決める。
※定義番号iを1に初期化
k = 1 『定義番号kが決まってない場合』
f(x,n) = x+n 『f(x,n)が決まってない場合』
※繰り返しポイント(A)
x[0]n := f(x,n)
x[1]n := x[0](x[0](x[0](...[0](x[0]x)...))) 『xに演算子[0]をn-1回適用』
x[2]n := x[1](x[1](x[1](...[1](x[1]x)...))) 『xに演算子[1]をn-1回適用』
x[3]n := x[2](x[2](x[2](...[2](x[2]x)...))) 『xに演算子[2]をn-1回適用』
x[4]n := x[3](x[3](x[3](...[3](x[3]x)...))) 『xに演算子[3]をn-1回適用』
x[m]n := x[m-1](x[m-1](x[m-1](...[m-1](x[m-1]x)...)))
『xに演算子[m-1]をn-1回適用』
f(x) := x[x]x 『関数fはxに演算子[x-1]をx-1回適用すること』
f(x,1) := f(f(x)) 『関数fを1回入れ子』
f(x,2) := f(f(f(x))) 『関数fを2回入れ子』
f(x,3) := f(f(f(f(x))))) 『関数fを3回入れ子』
f(x,4) := f(f(f(f(f(x))))) 『関数fを4回入れ子』
f(x,n) := f(f(f(f(f(...f(x)...))))) 『関数fをn回入れ子』
※もし定義番号iと定義番号Kが等かったら終了ポイント(B)へジャンプ
※定義番号iをインクリメントする。
※繰り返しポイント(A)にもどる。
※終了ポイント(B)
- 995 名前：１３２人目の素数さん ：04/04/23 16:01
- f(x,n,1)『定義番号kが1の場合のf(x,n)』
f(x,n,2)『定義番号kが2の場合のf(x,n)』
f(x,n,3)『定義番号kが3の場合のf(x,n)』
f(x,n,4)『定義番号kが4の場合のf(x,n)』
f(x,n,m)『定義番号kがmの場合のf(x,n)』
g(x) := f(x,x,x) 『関数gは関数fの引き数全てに同じ値xを入れること』
g(x,1) := g(g(x)) 『関数gを1回入れ子』
g(x,2) := g(g(g(x))) 『関数gを2回入れ子』
g(x,3) := g(g(g(g(x))))) 『関数gを3回入れ子』
g(x,4) := g(g(g(g(g(x))))) 『関数gを4回入れ子』
g(x,n) := g(g(g(g(g(...g(x)...))))) 『関数gをn回入れ子』
f(x,n) := g(x,n)
※g(x,n)を種関数として>>994の定義を適用
- 996 名前：１３２人目の素数さん ：04/04/23 19:58
- どうでもいいでつが、次スレは何時起つのでつか
- 997 名前：１３２人目の素数さん ：04/04/23 22:14
- >>995
それで、ようやくSS変換１回分くらいかな。
久々に「SS変換」という言葉を使ってみたかっただけ。
- 998 名前：１３２人目の素数さん ：04/04/23 22:33
- >>993
アッカーマンやタワーのどこに、
>>1の「前の数」とか、>>985の「拡張できたとして」
に相当する遅出し要素がある？
- 999 名前：１３２人目の素数さん ：04/04/23 22:36
- >>994-995
ふぃっしゅのアイデアにさえ、遠く及ばない。
- 1000 名前：１３２人目の素数さん ：04/04/23 22:41
- 巨大数探索スレッド6
http://science2.2ch.net/test/read.cgi/math/1082727613/
- 1001 名前：１００１ ：Over 1000 Thread
- このスレッドは１０００を超えました。
もう書けないので、新しいスレッドを立ててくださいです。。。