【ふぃっしゅ数】巨大数の探索スレ【ばーど数】

663 名前：１３２人目の素数さん ：02/11/20 02:00

ふぃっしゅ数が計算可能なのは初めから明らかだった。
ただどうやって計算していいか判らないだけ。

しかし、何で計算可能性に不必要に拘る人間がいたのだろう。
値が存在する事と、計算可能性は直行する概念なのに。

664 名前：１３２人目の素数さん ：02/11/20 02:26

>>663
うーんと、よそからきて眺めた計算機屋ですが、よかったら
ゲームのルールを教えて下さい。このスレの目標は大雑把にいって
1変数の帰納関数の中でもっとも早く成長する関数を構成すること
であるという理解で正しいですか?

665 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/20 02:50

>>658
なるほど、繰り返しの意味が不明確でしたね。
「仮にｎ項漸化式が2項漸化式をｎ回行う、といった操作に相当すると」
といった書き方では、たとえば
B(a,b,c)=B(a,B(b,c))
のような表現を考えますからね。

私が「2項漸化式の繰り返し」といった表現をしたのは、正確に表現
するとすれば「2項漸化式的拡張であるＳ変換の繰り返し」という
意味です。これではなんのことだかより不明確になりますので、
3項漸化式を例にとって私の予測（厳密な検討をしていないので、
あくまでも予測です）を説明します。

666 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/20 03:00

2変数Ackermann関数をA(x,y)とします。このとき、Ｓ変換を
2回繰り返した関数は、

　B(0,n)=A(n,n)
　B(m+1,0)=B(m, 1)
　B(m+1,n+1)=B(m, B(m+1, n))
　g(x)=B(x,x)

と表記できます。このときのg(x)は、たとえば >>10 のような
漸化式を定義したときに、

g(x)=f[3](x)=B_3(x,x,x)

に相当するのではなかろうか、とふと思ったわけです。

そうすると、f[n](x)はおそらくＳ変換をn-1回繰り返すことで
表現できるかもしれない。そういったようなことを意味して
いました。

667 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/20 03:35

ただ、よくよく考えてみると、>>10の中には
B_n(0,0,…,0,x)=f[n-1](x)
といった定義があるので、この予想は成り立ちませんね。

なぜそんな予想をしたのかを思い出してみると、おそらくは
B_n(0,0,…,0,x)=x+1
といったような漸化式を考えていたためだと思います。

というわけで、>>10の増加程度を、ふぃっしゅ数の定義の
Ｓ変換と比較するとどうなるのか、といった検討をして
みたくなってきました。また、時間ができたときにでも。

669 名前：１３２人目の素数さん ：02/11/20 14:58

>>664
このスレの住人ではないが、違うと思われ
粗い記数法のなかで最速のものを作っているのであろう

「粗い」というのは、記数法 f に対し n[f]: N->N が存在して、
f によって d 文字で数 n[f](d) は表せても
n[f](d) までの数を全部表せる必要はないという意味
「記数法 g より記数法 f が速い」とは
∃a: ∀d: a < d => n[g](d) < n[f](d)

記数法は「文字だけで構成された図形」から数への変換規則のことで
どういう制限があるかは分からんが、
記数法 f に よる表記全体 G[f] に対し、少なくとも、
表記 x ∈ G[f] の値を求める関数 val[f]: G[f] -> N が
well-defined であることが要求されるだろう
また busy beaver が禁じ手らしいので val を帰納関数で書けることも暗黙の条件

670 名前：１３２人目の素数さん ：02/11/20 14:59

>>669 の続き
記数法 f で許される文字の有限集合を Σ[f] とするとき、
読み方を与える seq[f]: G[f] -> (Σ[f]+C[f])* と
表記の読み下しから値への関数 V[f]: (Σ[f]+C[f])* -> N があって、
val[f](x) = V[f](seq(x)) と書き直すことができる。
ただし X* は X の連結に関する閉包で C は図形を文字列化するのに必要な文字

例えば G[f] を(十分制限された)TeXによる数式表記(a^bなど)に限るとき、
G[f] ⊂ (Σ[f]+C[f])* と見做すことができて、
seq は恒等写像で val = V と見做すことができる
このとき表記 f を構成するものは、組 <G[f], V[f]> と考えられる
２ちゃんでやる以上はAAを使うのは繁雑なので、このような見做しが有効
Gは文法で、Vは評価と考えられる

結局、V を帰納関数に制限したとき、できるだけ速い f = <G, V> を構成し、
インパクトのある値を f で具体的に表記するというのがルールだろう

671 名前：１３２人目の素数さん ：02/11/20 15:03

>>670 の続き
というわけで勝手に説明したがなんか違ってたら訂正してやってちょ

672 名前：１３２人目の素数さん ：02/11/20 17:50

>>６７９-６７1さん

えと、とりあえず、なんでそんなルールが必要なのか、教えてください。

それと、そのルールだと、ふぃっしゅ数はバージョンいくつまで許容ですか？

673 名前：１３２人目の素数さん ：02/11/20 19:49

ルールを先に決めようというのはツマラナイね。
具体的に提出された数に対して、それを許容するか否か決める方が良い。

674 名前：１３２人目の素数さん ：02/11/20 21:22

>>672 >>673
もちろん皆さんに従えというつもりはまったくなくて、何をやっているかと
いう説明が与えられないから外野が書いてみただけ。むしろ現象説明。
ルールといったのは間違いだったかも。すまん。
それに法律を作れというつもりもないけど、ただ 前の数+1 が駄目とか、
busy beaver が駄目とかといったことにどういった数学的説明が
与えられるのかにはやっぱり興味がある。数学板だし。

ふぃっしゅ数は多分バージョン３まで >>669-671 を満たすと思うのだけど、
残念ながら Second step 以降の定義が理解できないので断定はできない。
>>188-192 では mapping といいつつ慣用的な写像の書き方ではないので、
p,q,r や ^y そしてプライム「'」の意味がつかめない。

675 名前：１３２人目の素数さん ：02/11/20 23:16

[1] 集合Xに対しXからXへの写像全体をEnd(X)で表す。
Nは自然数全体とし、集合T(n)を
T(0)=End(N),T(n)=End(N×T(0)×･･･×T(n-1)) (n>0)と定義する。（×は直積集合）

[2] T(n)の元s(n) (n>0)を次の様に定める。
m∈N,f∈T(0)に対して、
s(1)[m,f]:=[n,g]
ただし、B(0,n)=f(n),B(m+1,0)=B(m,1),B(m+1,n+1)=B(m, B(m+1,n)),g(x)=B(x,x)

m∈N,f_i∈T(i)に対して、
s(n)[m,f_0,f_1,f_2,･･･,f_{n-2},f_{n-1}]:=[n,g_0,g_1,g_2,･･･,g_{n-2},g_{n-1}]
ただし、
g_{n-1}=f_{n-1}^{f_0(m)},
g_{n-1}[m,f_0,f_1,f_2,･･･,f_{n-2}]=[n,*,g_1,g_2,･･･,g_{n-2}],
g_{n-1}^x[m,f_0,f_1,f_2,･･･,f_{n-2}]=[*,r_x,*,*,･･･,*]と置く時、g_0(x)=r_x(x)
(*はs(n)の定義には用いられない部分)

[3] T(1)の元ss(1)を次の様に決める。
ss(1)[m,f]:=[n,g]
但しs(m+1)^{f(m)}[m,f,s(1),s(2),･･･,s(m)]=[n,g,*,*,･･･,*]

最後に[F,*,*]:=s(2)^63[3,x+1,ss(1)]と置く。

676 名前：１３２人目の素数さん ：02/11/20 23:17

糞スレだな

677 名前：675 ：02/11/20 23:21

http://science.2ch.net/test/read.cgi/math/1033320305/188-192
を読ませていただきました。
全体のアイデアは>>675の様なものでないかと推測いたしました。
私の慣れた記号に変えさせて頂いておりますが、これで宜しいでしょうか？
（元のままでは、類似した記号を用いている部分が混乱を招き易く、
また定義に所々穴がある様に感じます。）

678 名前：664 ：02/11/21 00:53

おかげで気分的にだいぶすっきりしました。
巨大数の表示は busy beaver やアルキメデスの家畜問題みたいに
方程式の根として表すこともできるけど、既知のものより大きいことを
主張するには何か実行可能な概算手続きがないと難しいでしょうね。
帰納的でなくてももちろん良いのだけど、見積もれる条件としては
帰納的でも弱くて難しそうなので実際に大きなことが主張できるのは
証明可能帰納的(provably recursive)あたりなのかもしれません。

679 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/21 05:32

>>669
なるほど、ようやく「自分がなにをしようとしてきたか」が
すっきりしました。ありがとうございます。

>>677
はい、まさにそういった定義です。定義のわかりにくさ、
そして不完全さを直していただき、ありがとうございます。

680 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/21 05:35

せっかくなので、２つほど質問をさせてください。

まずは1つ目の質問です。

「粗い記数法のなかで最速のものをつくる」という
観点から、このスレッドにまだでてきていないもので
なにか面白いものがありましたら紹介してください。

681 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/21 05:37

2つ目の質問です。

バージョン４は well-defined である、つまり有限の数と
して一意に定まると考えていますが、この考えは正しいで
しょうか、間違っているでしょうか。それとも、正しいと
するためには、ある一定の仮定なり公理が必要とされる
のでしょうか。

バージョン4の定義を書きます。

682 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/21 05:44

[1] 集合Xに対しXからXへの写像全体をEnd(X)で表す。
Nは自然数全体とし、集合T(n)を
T(0)=End(N),T(n)=End(N×T(0)×･･･×T(n-1)) (n>0)と定義する。（×は直積集合）

[2] T(n)の元s(n) (n>0)を次の様に定める。
m∈N,f∈T(0)に対して、
s(1)[m,f]:=[n,g]
ただし、O(f)=g, g(m)=n
ここで、O(f)は関数fの値を返すオラクルを１つだけ持つO-machinesによって
生成されるビジービーバー関数

m∈N,f_i∈T(i)に対して、
s(n)[m,f_0,f_1,f_2,･･･,f_{n-2},f_{n-1}]:=[n,g_0,g_1,g_2,･･･,g_{n-2},g_{n-1}]
ただし、
g_{n-1}=f_{n-1}^{f_0(m)},
g_{n-1}[m,f_0,f_1,f_2,･･･,f_{n-2}]=[n,*,g_1,g_2,･･･,g_{n-2}],
g_{n-1}^x[m,f_0,f_1,f_2,･･･,f_{n-2}]=[*,r_x,*,*,･･･,*]と置く時、g_0(x)=r_x(x)
(*はs(n)の定義には用いられない部分)

[3] T(1)の元ss(1)を次の様に決める。
ss(1)[m,f]:=[n,g]
但しs(m+1)^{f(m)}[m,f,s(1),s(2),･･･,s(m)]=[n,g,*,*,･･･,*]

最後に[F,*,*]:=s(2)^63[3,x+1,ss(1)]と置く。

683 名前：１３２人目の素数さん ：02/11/21 06:42

>>675
>m∈N,f_i∈T(i)に対して、
>s(n)[m,f_0,f_1,f_2,･･･,f_{n-2},f_{n-1}]:=[n,g_0,g_1,g_2,･･･,g_{n-2},g_{n-1}]
>ただし、
>g_{n-1}=f_{n-1}^{f_0(m)},
>g_{n-1}[m,f_0,f_1,f_2,･･･,f_{n-2}]=[n,*,g_1,g_2,･･･,g_{n-2}],
>g_{n-1}^x[m,f_0,f_1,f_2,･･･,f_{n-2}]=[*,r_x,*,*,･･･,*]と置く時、g_0(x)=r_x(x)
>(*はs(n)の定義には用いられない部分)

ここで、f_0,…,f_{n-1}は入力として外から与えると理解すればいいんでしょうか。

684 名前：１３２人目の素数さん ：02/11/21 06:48

>>675
>[3] T(1)の元ss(1)を次の様に決める。
>ss(1)[m,f]:=[n,g]
>但しs(m+1)^{f(m)}[m,f,s(1),s(2),･･･,s(m)]=[n,g,*,*,･･･,*]

３行目はｇの定義でしょうか？
もし、そうなら以下のように書くほうが分かると思います。

「但しgは以下で求められる関数とする。
　s(m+1)^{f(m)}[m,f,s(1),s(2),･･･,s(m)]=[n,g,*,*,･･･,*]」

685 名前：675 ：02/11/21 09:11

すみませんが、>>675を下のように訂正します。
記号nを2通りの意味で用いている部分等がありました。>>684も参考にさせていただきます。
正確な定義を書こうとしても、自分で書くと先入観で気付かない物です。

[1] 集合Xに対しXからXへの写像全体をEnd(X)で表す。
Nは自然数全体とし、集合T(n)を
T(0)=End(N),T(n)=End(N×T(0)×･･･×T(n-1)) (n>0)と定義する。（×は直積集合）

[2] T(k)の元s(k) (k>0)を次の様に定める。
m∈N,f∈T(0)に対して、
s(1)[m,f]:=[g(m),g]
ただし、B(0,y)=f(y),B(x+1,0)=B(x,1),B(x+1,y+1)=B(x,B(x+1,y)),g(x)=B(x,x)

m∈N,f_i∈T(i)に対して、
s(k)[m,f_0,f_1,f_2,･･･,f_{k-2},f_{k-1}]:=[n,g_0,g_1,g_2,･･･,g_{k-2},g_{k-1}]
ただし、
g_{k-1}=f_{k-1}^{f_0(m)},
g_{k-1}[m,f_0,f_1,f_2,･･･,f_{k-2}]=[n,*,g_1,g_2,･･･,g_{k-2}],
g_{k-1}^x[m,f_0,f_1,f_2,･･･,f_{k-2}]=[*,r_x,*,*,･･･,*]と置く時、g_0(x)=r_x(x)
(*はs(k)の定義には用いられない部分)

[3] T(1)の元ss(1)を次の様に決める。
ss(1)[m,f]:=[n,g]
ただし、n,gは以下で求められるものとする。
s(m+1)^{f(m)}[m,f,s(1),s(2),･･･,s(m)]=[n,g,*,*,･･･,*]

最後に[F,*,*]:=s(2)^63[3,x+1,ss(1)]と置く。

686 名前：675 ：02/11/21 09:15

>>683
>ここで、f_0,…,f_{n-1}は入力として外から与えると理解すればいいんでしょうか。

そうです。ただし、私は計算論に関しては全くの素人ですので、
"専門用語"を使っておられるとすれば、その限りではありません。

687 名前：１３２人目の素数さん ：02/11/21 13:18

m,f_0の初期値はそれぞれ3,x+1で良いとして、f_1以降はどうなるの？

688 名前：１３２人目の素数さん ：02/11/21 14:26

>>f_1以降はどうなるの？
s(i)等から順次定まるんじゃ？

689 名前：１３２人目の素数さん ：02/11/22 01:11

>>680
知らない。おそらくこのスレの住人の方がはるかに詳しい。
0を空位とする十進表記等の通常のn進法以外はすべて粗い。
位に、百や C や hundred などの名前をつける自然言語のやりかたも粗い。
ある数を「Graham's number」や「ふぃっしゅ数」と呼ぶのもこれと少し似てる。

むしろ「速い」の定義を洗練していくことは面白いかも。
>>669 の「速い」の定義は非常に細かいため「前の数+1」を排除しない。
アルゴリズム論で使われるＯ記法は多項式に焦点を絞ってるから
O(log_2 n) = O(log_3 n) のように対数の底は区別しないが O(2^n) < O(3^n) なんで
これもここでは目が細か過ぎて記数法の速さを表すには不満足と思われ。
記数法 f, g に対して f < g で「fよりgが速い」ことを表すことにすると、
>>228 にある「上位の表記」であることを表明する関係として
f < g を定義できるか否か問題なんだろうな。

690 名前：１３２人目の素数さん ：02/11/22 01:11

>>681
すまんが分からん。
関数 f が計算可能でも O(f) は well-defined かつ計算不能なんで、
ある関数 h に対して O(h(O(f))) が well-defined であるかは
詳しく調べないと分からんわけだが、専門ではないので手に余る。
計算量の専門家は非常に少ない（日本にも多分10人はいないだろう）から
このスレを見てることも期待できん。

691 名前：１３２人目の素数さん ：02/11/22 01:12

>>681
ところで busy beaver (BB) は構成的な関数じゃないから、
もし >>669 に共感するんだったら、BBを利用した定義をすることは勧められん。
帰納的である必要はないが、より広い「構成的」っつー立場は
とった方がいいと思うがどうよ？ BBだと状況が分かりにくいかもしれんが、
pi0(n) = 「円周率の2進表記に 0 が n 回連続して出現する最初の位置」
のようなものを認められるか？　これと大した違いはないと思うんだが。
もしこういったものも認めて記数法の速さを抽象的に議論したいんだったら
計算量の専門家になるしかねえと思う。

692 名前：１３２人目の素数さん ：02/11/22 01:21

>>691
あ、自分でならなくても専門家を探して訊けばいいかｗ

693 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/22 03:29

>>689

>>685の中で、最後の1行以外は記数法fの定義、最後の1行は
定義された記数法の中で具体的に大きな数n[f](29)を作成
した例、と考えます。

「前の数＋１」は、後者の問題に帰属しないでしょうか。
このとき、「ふぃっしゅ数＋１」はn[f](31)として表現でき
ます。記数法fを定めたときに、あるdの値について最大の
n[f](d)を求める問題は、記数法の速さそのものとは別の
問題です。>>19がこれにあたります。ふぃっしゅ数よりも
大きなn[f](29)は簡単に作成できます。

ただ[F,*,*]:=s(2)^63[3,x+1,ss(1)]を記数法の一部と
する記数法gを考えると、F+1はn[g](3)となるわけですよね。
このとき、f<gですが、これを「上位の表記」と考えて
よいものかどうか。

そのあたりの問題をどう整理するか、というのが>>689の
趣旨だと思います。

さて、どうしましょう。

694 名前：１３２人目の素数さん ：02/11/22 04:24

>>690
> 関数 f が計算可能でも O(f) は well-defined かつ計算不能なんで、
> ある関数 h に対して O(h(O(f))) が well-defined であるかは

専門家じゃないが h が well-defined なら O(h(O(f))) は well-defined だろう。

全くオラクルを持たない TM の族を TM(0) とし、TM(0) に関数 h を
神託として与えるオラクルが付与された TM の族を TM(h) とするとき、
関数 h が well-defined なら、そのオラクルも well-defined と考えてよく、
TM(h) は確定する。TM(h) の中で状態数 n のものを集めることで
BB(n) も確定する。このことから O(h(O(f))) が well-defined といえる。

ただし、TM(h) に対する BB(n) の値は、TM(0) が神託 h を
どのような形で利用できるのかによって変わる余地がある。
つまり O(f) の定義は well-defined になる余地はあるが
現状では不十分ともいえる。神託を受ける方法を決めなければならないのでは?

695 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/22 04:36

>>691
>>674のBBがだめという理由として、当面は構成的な関数でないから、
という説明を与えておこうということですね。

ちなみに、pi0(2)のような例は、前スレでも検討されていました。
似たような例として、たとえばn番目の素数とか、n番目の双子素数
といった関数が考えられますが、後者は双子素数が無限に存在する
ことが証明されていないために没。前者のように、存在が保証されて
いるものについては、たいていの場合初等関数で近似できるため、
たいした関数にはならないのではないか、といったような意見で
まとまりました。存在が保証されていて、しかも初等関数で近似
できないような非構成的関数があれば面白いだろう、といった
ような意味のことは前スレに書いたような気がするのですが、
それがまさにBBです。

そして、当面は「BBの検討は専門家でないと手に負えないので
BBは使用しないことにする」といった、非常に数学的でない
曖昧なところに落ち着けておくのも一つの妥協点かと。

696 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/22 09:07

>>693
ちなみに、ふぃっしゅ数の記数法の元での文字数制限最大数を
競うとすると、たとえば
n[f](30): [F,*,*]:=s(2)^9^9![9,x!,ss(1)]
n[f](40): [F,*,*]:=s(4)^9^9![9,x!,ss(1),s(2),s(3)]
といった感じで、「+1」といった表記に2文字を使う余裕は
どこにもないので、「○○＋１」は簡単に否定されます。

問題は、n[f](d)=F,といった記述をfに加えてgを定義し、
n[g](d)=G,といった記述をgに加えてhを定義し､といった
手法による拡張です。いわゆる「前の数」問題です。

ふぃっしゅ数を例にとると、
[F,*,*]:=s(2)^63[3,x+1,ss(1)]
[G,*,*]:=s(2)^F[F,x+1,ss(1)]
[H,*,*]:=s(2)^G[G,x+1,ss(1)]
といったような拡張を何度も記数法の中に入れたとして、
その記数法はどの程度の強さを持つか、といったことです。

697 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/22 09:08

>>696
この記数法拡張に使われた文字数をxとすると、新記数法g
によるn[g](d)は、元の記数法で少なくともn[f](d+x)程度
にあらわせます。今度は、記数法fの元で、上記表現を
そのまま書き足せばいいだけだからです。そして、
∃a: ∀d: a < d => n[f](d+x) < n[g](d)
のときにf<g、と書けそうですが、ここでxの値が定まらない
のが欠点です。x=Graham's number とでもしておけばいいと
も思いますが、非数学的です。d+xの個所をdの関数として
表記する必要がありますが、たとえば
∃a: ∀d: a < d => n[f](n[f](d)) < n[g](d)
とすれば、十分に粗い定義ができあがります。この場合、
粗すぎてf<gの証明がなかなかできなくなる、という落ちが
ありそうです。

「より上位の表記」といった漠然とした考えを、きちんと
数学的に記述しようとすると、骨が折れますね。

698 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/22 09:45

ふと思ったんですが、記数法が非常に厳密に定義されると、
ある記数法の元でn[f](d)の最大値が決まりませんか？

そうすると、
「n[f](d)の最大値をM[f](d)とする」
といった定義ができてしまい、それを記数法に取り入れると、
なんだかビジービーバー問題っぽくなってきますね。

いや、この定義をした時点で、その記数法はn[f](d)の
最大値が決まらない記数法となるから、やっぱりだめか。

と、混乱するので当面は構成的関数に限るか、やはり。

699 名前：１３２人目の素数さん ：02/11/22 10:33

前スレのミラーをルクダルさんに作ってもらいますた。

http://www.globetown.net/~datdat2ch/021121-1024311743.html

思えば遠くへ来たもんだ。

700 名前：１３２人目の素数さん ：02/11/22 13:26

>>695
構成的でない数を無制限に許すと数の大小比較が非常に難しい。
そのような数は大きいことを主張できるのだろうか。
あるいはそのような数は記されたと考えてもよいのだろうか。
日常的な感覚からすれば「ある数を記す」ということは、
その「ある数の存在を保証する」以上の行為に思えるのだが。

例えば円周率はその小数展開を好きなだけ得る方法がある。
これは任意の有理数と比較できるということにほかならない。
だからπという記号で記した気分になることができるのだろう。
いっぽう構成的でない数はこのような比較手続きの存在を
示すことを放棄している。この違いは大きい。

このスレがきっかけになって数を記すということの意味が
明らかになればとても面白いと思う。

701 名前：１３２人目の素数さん ：02/11/22 20:48

なんだか天井が見えてきた感じですね

ここらで方向を変えて、今まで出てきた数を回転矢印などを使って
比較してみる、というのはどうでしょう？

702 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/22 23:52

>>700
同意します。

だからこそ、BBが非常な奇異な感じがするのです。
BBによってあらわされた数は、計算不可能なため大小比較が
非常に難しいにも関わらず、計算可能な関数を使って普通に
あらわされた数よりは、大きいことが主張されます。
大小比較が難しいのに、大きいことだけは主張している。

「大きな数」を作ることを目的としているのに、BBを
決して超えることのない数を作って満足しているのも
なんだか物足りないのです。もっとも、構成的な巨大数X
を定義すれば、BB(X)でさらに大きな巨大数ができますから、
ここはひとつ構成的な巨大数を求めることに集中しても
いいと思います。

703 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/23 00:02

「巨大数を作る」とはどういうことか？を考察しているだけなので、
スレのルールを規定しようとしているわけではありませんが、
「記数法」の観点から少しだけ整理しました。なんとなくの素案なので、
いくらでも変えてください。

定義「正則な記数法」
記数法fによってd文字以内にあらわされる数n[f](d)の最大値
M[f](d)が存在するとき、fは正則な記数法である。

定義「正則な記数法の速度」
正則な記数法 f, g について、f より g が速い (f < g) とは
∃a: ∀d: a < d => M[f](d) < M[g](d)

定義「上位の記数法」
正則な記数法 f, g について、f より g が上位である (f <<g) とは
∃a: ∀d: a < d => M[f](M[f]d) < M[g](d)

704 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/23 00:07

たとえば、あるバージョンの LISP にて有限の値を出力する
プログラムも正則な記数法 L となります。こういった表記を
されてしまうと、その記数法はふぃっしゅ数よりは上位の
記数法となるのかもしれませんが、この場合は記数法が上位で
あること自体にはたいした面白味がないので、具体的に大きな
n[L](d)を構成してみせてもらって、はじめて「面白い」と
いえることになりそうです。

705 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/23 00:32

>>702の続き
さて、構成的な巨大数Xを作成して、BB(X)を出して「どうだ、この
数は大きいぞ」と主張したとします。ところが、今度はビーバー君
から、「君、Xは少なくともBB(1000)よりは小さいよ。したがって、
X<BB(1000) -> BB(X) < BB(BB(1000))だから、BB(X)よりも
BB(BB(1000))の方が大きいよ」と言われてしまいます。

BBの原始帰納的拡張に意味があるとかないとか、そういう問題では
ないのです。どんなに頑張って大きなBB(X)を作成しようとしても、
少なくともBB(BB(1000))よりは小さい、そういった天井の見えて
いるところで遊んでいるのは、とにかく大きな数を作りたい、という
欲求を十分に満たさない行為なのです。

706 名前：ふぃっしゅしゅ ◆/T2GtW187g ：02/11/23 00:36

ここでの問題は、常に well-defined であるかどうかです。
仮に BB(BB(1000)) が well-defined でなければ、ビーバー君に
「君、その数は一意に定まらないから意味がないよ」と言い返せます。
しかし、well-defined である限りは、ビーバー君にかなわないのです。

さて、そうなってくると、
[F,*,*]:=s(2)^63[3,BB(x),ss(1)]
を考えてしまいます。今度は、ビーバー君がBB(F)などといった拡張を
したところで「君、なにをちまちま原始機能的拡張をしているんだね」
と笑い飛ばすことができます。

ここでの問題は、はたして上記 F が well-defined であるかどうか、
の一点です。well-defined であれば、大きな巨大数が作成できた
ことになります。

707 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/23 00:44

ビーバー君は魚に負けたのが悔しくて、神託を持ってきました。
そして言います。「君、BBを元にいくら頑張って拡張しても、それは
すべてBBをオラクルとして持つO-machinesを使えば計算できるんだよ。
だから、O(BB)(1000)にはかなわないんだよ。」

ここでの問題は、はたしてビーバー君が定義した数が well-defined
であるかどうかです。well-defined でなければ、ビーバー君に
「君、そんな数は一意に定まらないから意味ないよ」と言い返す
ことができます。ですが、well-defined であったとすると、なにも
言い返せません。

「well-defined な関数をオラクルとして持つ o-machines に
よって生成されるビジービーバー関数は well-defined である」
この真偽は定かではありませんが、これが偽であれば、>>706を
もって「とにかく大きい数」ができたということができますし、
これが真であれば、バージョン４をもってはじめて「納得の
できる巨大数」が定義できたことになります。

708 名前：１３２人目の素数さん ：02/11/23 00:48

well-definedという言葉が仮にルールに即している事を意味するのなら、
目的に反した物を排するようにルールを設定すれば良いのではないでしょうか？

709 名前：１３２人目の素数さん ：02/11/23 01:00

もともとBB自体がこのスレの趣旨から外れていると感じる。
BBを排する事は、「今までの最大の数＋１」を排するのと同様に自然じゃない？

710 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/23 01:04

>>708
もちろんそういった立場もあります。
>>705-707 に書いたような気持ちがあるとともに、>>700 にも
非常に共感するのです。

なので、当面「構成的でない数は不許可」といったルールを
設定することについては賛成です。

711 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/23 01:08

ちなみに、well-defined はルールであるというよりは、巨大数で
あるための必須条件です。一つの数に定まらなければ、それは
もはや巨大数とは言えませんから。

712 名前：１３２人目の素数さん ：02/11/23 01:18

写像BB:N→Nがある時、BB^2:N→Nがwell-definedでない理由は、
何か特別な目的でもない限り、無いんじゃないかなぁ？

713 名前：１３２人目の素数さん ：02/11/23 01:33

695ゲトおめ＞ふぃっしゅっしゅ

714 名前：１３２人目の素数さん ：02/11/23 02:02

>>702
> BBによってあらわされた数は、計算不可能なため大小比較が
> 非常に難しいにも関わらず、計算可能な関数を使って普通に
> あらわされた数よりは、大きいことが主張されます。

面白そうですね。このことはどのように示されるのか
証明の概略をどなたか教えてもらえませんか？

715 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/23 04:29

>>691のpi0(n)は計算可能な非構成的関数の例だとすると、
構成的な計算不可能関数は存在するでしょうか。
構成的であれば、その構成通りにアルゴリズムを組めて
計算できてしまうような気がします。したがって、構成的
関数よりは、計算可能関数の方が広い定義のような気が
します。

716 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/23 04:33

>>714
BBについてちょっとだけ調べた知識を元にすると、こんな感じです。
計算可能な関数を使って普通にあらわされた数Xを考えます。
その計算手続きにしたがえば、Xを出力するプログラムを記述する
ことができます。そうすると、Xの値を出力する（Xの数だけ1を
出力して止まる）チューリングマシンを作ることができます。
そのチューリングマシンの状態数をNとすると、X < BB(N)と
なります。ところが、BB(100) < X が成り立つかどうかを
計算で確認することはできません。

717 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/23 04:42

もうしばらく定義ごっこを続けてみます。

定義「計算可能な記数法」
正則な記数法 f について、その記数法で表記された数がすべて
チューリングマシンによって計算可能である時に、f は計算
可能な記数法である。
計算可能な記数法全体の集合を C とする。

定義「ビーバー記数法」
自然数の10進数、ビジービーバー関数BB(x)、関数の繰り返し
表記f^x(y)のみを認める記数法を、ビーバー記数法 B とする。
B は計算不可能な記数法である。

ビーバー記数法の例
M[B](5) = BB(9)
M[B](10) = BB^9999(9)

予想：∀f∈C: f << B

718 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/23 04:55

とりあえず、定義だけはしてみました。
あとは、最速の計算可能な記数法を追いかけるもよし、
最速の正則な記数法（含計算不可能な記数法）を追いかけるもよし。
それぞれのルールの元で、遊ぶのがよろしいかと。

ちなみに、最速の計算可能な記数法を追いかければ、それに
ビーバー記数法の表記を加えるだけで、そのまま最速の
正則な記数法を追いかけることにもなります（たとえば、
ふぃっしゅ数の定義にBB(x)表記を加えるだけで、>>706
のような表記が許される）。

その意味で、分かりやすく、計算可能な記数法の中で
記数法の速度を比較すれば十分といった気もします。

719 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/23 04:58

というか、計算不可能な記数法の中では、速度の比較ができないので、
計算可能な記数法の中で速度をしよう、といったような意味のことを、
みなさんおっしゃっているのだと思います。私もそれが健全な姿勢だと
思います。

720 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/23 05:06

定義「記数法の加算」
正則な記数法 f, g について、f, g で許されるあらゆる記数法を
認め、また f, g で許されない記数法を認めない記数法を、
f+g であらわす。

このとき、計算可能な記数法 f, g について、
(1) f < g -> f+B < g+B
(2) f << g -> f+B << g+B
が、それぞれ成り立つかどうかを検討すれば、計算可能な記数法
である f, g の速度を比較するだけで、計算不可能な記数法
f+B, g+B の速度を議論することができます。

とだけ書いて、誰かやって、といってみよう。

O-machines 関係は、>>707 の真偽がはっきりするまでは
保留ということで。

721 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/23 05:14

あと、もう一つ考えられるのが、正則な記数法 f に対して
f(d)=M[f](d)と表記することだけを許す記数法 g を考える
ことができ、f->gの写像を定義することができるという点です。

頭がうにだ、知恵熱が。

722 名前：１３２人目の素数さん ：02/11/23 17:02

>>699

みました。はじめはグラハム数を越えるためのアイデアだったんですね。

ところで、もとのふぃっしゅ関数は、Ackermann関数をタネにしてますが
これは必ずしも計算しやすいものではありません。

これの代わりに>>342のの関数

ak(x, y, 0) = x + y,
ak(x, y, 1) = xy,
ak(x, y, 2) = x^y,
ak(x, 0, c + 1) = x,
ak(x, y + 1, z + 1) = ak(x, ak(x, y, z+1), z)
（x↑^2 y = x↑↑yと書く場合、x↑^m y = ak(x, y, m+1)）

を利用した、ふぃっしゅ↑関数
g(n)=ak(ak(n,n,n),ak(n,n,n),ak(n,n,n))とする関数をS1とする。
（以下同様。）
を使えば、評価計算が多少やりやすくなるでしょう。

723 名前：１３２人目の素数さん ：02/11/23 17:09

>>722の続き

グラハム数の計算に用いる反復は、おおまかには
ak(n,n,n)
ak(n,n,ak(n,n,n))
ak(n,n,ak(n,n,ak(n,n,n)))
…
のようなスタイルになるので、ふぃっしゅ↑関数より
増加度は小さいでしょう。

724 名前：１３２人目の素数さん ：02/11/23 23:18

>>716
どうもありがとうございました。

729 名前：１３２人目の素数さん ：02/12/10 21:38

もう1スレ目とは似ても似つかぬ姿になってる

730 名前：１３２人目の素数さん ：02/12/11 14:41

皆死んだか

731 名前：１３２人目の素数さん ：02/12/11 14:54

生きてるよ。考える時間がとれなくて。
＞703の「∃a: ∀d: a < d => M[f](M[f]d) < M[g](d)」は、
ふぃっしゅっしゅが巨大数をどう見てるのかが少し見えて面白い。
定義しようとすることはやっぱり大事だと思ったyo

737 名前：Q.man ：02/12/11 19:14

Γ（Γ（Γ（Γ（Γ（Γ（Γ（Γ（Γ（１０＾（１０＾１００））））））））））
ちなみに、Γ（ｘ）＝∫［０＜ｔ＜∞］ｅｘｐ（−ｔ）＊ｔ＾（ｘ−１）ｄｔ。

739 名前：１３２人目の素数さん ：02/12/11 21:38

Γ（１０＾（１０＾１００））は何桁の数か求めよ
--＞Q.Man

745 名前：１３２人目の素数さん ：02/12/17 20:55

>>737
あまりに小さい数を出すから（略

747 名前：１３２人目の素数さん ：02/12/22 11:27

f(1)=10^10
f(2)=10^10^10
f(3)=10^10^10^10
................
とする。
f(10^10^10^10・・・１０の１００億乗桁回・・・^10^10)
とか

748 名前：１３２人目の素数さん ：02/12/22 18:34

>>747
f(4)=10^10^10^10=10^(10^(10^10))は10の100億乗+1桁の数だから
f(f(4)) と書けば済むのでは。

749 名前：１３２人目の素数さん ：02/12/22 19:23

>>748
そうですね。
ならば
f(f(f(...10の100億乗桁回...f(f(10^10^10)))))...10の100億乗桁回...)))

750 名前：１３２人目の素数さん ：02/12/22 19:29

>>749
ではもっと
f(f(f(...10の100億乗桁回...f(f(10^10^10...10の100億乗回....^10^10)))))...10の100億乗桁回...)))

752 名前：１３２人目の素数さん ：02/12/22 19:32

f(f(f(...10の100億乗桁回...f(f(10^10^10...10の100億乗桁回....^10^10)))))...10の100億乗桁回...)))

753 名前：１３２人目の素数さん ：02/12/22 19:37

>>750
それなら、
f^(1)(x) = f(x), f^(n+1)(x) = f(f^n(x)) と定義すれば、
f^(f(4))(f(4)) で済んだのでは。

754 名前：１３２人目の素数さん ：02/12/22 20:59

>>752
このスレでは久しぶりの、すごい小さい数字が出たな

755 名前：１３２人目の素数さん ：02/12/23 13:47

f^(f(f(10^100)))(f(f(10^100)))

756 名前：１３２人目の素数さん ：02/12/23 13:49

>>755
無駄な努力はやめれ。

757 名前：１３２人目の素数さん ：02/12/23 23:36

1と適当な数N,nをとってくる。
そして1=a0<a1<a2…<an=Nで、さらに1〜akと比べてa[k+1]が一気に大きくなったと感じるように（k=0〜n-1）
a0〜anをとってくるにはどうしたらよいか？

っていう問題をふと風呂の中で考えてた。
おっきい数の作り方とa0〜anをとってくる方法は対応してるのかなーって、漠然と考えてた。

まぁ大きさってのは主観である以上この書き込みは電波に過ぎないのだけど。

758 名前：１３２人目の素数さん ：02/12/30 11:11

保　　全

759 名前：旧695 ：02/12/31 10:57

よいお年をヽ(´ー｀)ノ

760 名前：熱き2002年、男達に捧げます ：02/12/31 13:51

　　 　　　　　　　　　　　　　　(￣￣<　 　　　／￣＞
　　 　　　　　　　　　　　　　　　＼　 ヽ　 　／ ／ｿ
　　 　　　 　プ　ロ　ジ　ェ　ク　ト＼　 ヽ P r o j e c t　X
　　 ─────────────────────
　　 　　　　　　挑戦者たち　／|_／ ／＼Challengers
　　 　　　　　　　　　　　　　　|　 　／　　　＼ 　　丶
　　 　　　　　　　　　　　　　　＼／　　　 　　 ＼__ノ

エーックス・・・

　アジア初のＷ杯で日本中が沸きかえった2002年、もひとつの壮絶な戦いが2ｃｈ数学版で起きていた。
驚異的な巨大数論争は前代未聞の「ふぃっしゅ数」を中心に海外の巨大数サイトも巻き込み、
果てしない戦いの様相を呈していた。
　次々に報告される海外の巨大関数は「ふぃっしゅ数」の巨大さを知る人々に計算可能・不可能の
論争も生み出し、検証するために男たちは終わることの無い非情な戦いの日々を送った。
　巨大数スレッドに挑んだ男たちは、終りの無い戦いに挑むことで数学の持つ神秘を垣間見たのだろうか？
プロジェクトは、誹謗や荒らしにも負けず、そして男たちは夢をあきらめなかった。
前回の日米巨大数最終決戦から3か月、2002年は人類がかつて見ることの出来なかった数の領域を
宇宙の彼方に見つめ続けた男たちの年として永遠に記憶に残るだろう。
これは、その執念と夢をあきらめなかった男たちの壮大なドラマの総決算である。

761 名前：熱き2002年、男達に捧げます ：02/12/31 13:51

♪風のなかのすーばるー　　『ふぃっしゅ数、再び発進』
♪砂の中の銀河−　　　　　『　Ｖer2の巨大な全貌　』
♪みんなどこへ行った−　　『チェ−ン関数・バ−ド数の衝撃』
♪見守られることも無く−　『ビジ−ビ−バ−関数登場』
♪草原のペガサス−　　　　『男たちの夢は　　』
♪街角のビ−ナス−　　　　『砕け散るのか？　』
♪みんなどこへ行った−　　『超宇宙のイメ−ジさえ越えて』
♪見送られる事もなく−　　『繰り返される関数・増殖する関数』
♪地上にある星を　　　　　『ふぃっしゅ氏が長文にたくした』
♪誰も覚えていない−　　　『巨大数への思い』
♪人は空ばかり見てる〜　　『Ｖer3.そしてＶer4』
♪つばめよ〜高い空から〜　『これが行き着いた、約束の地か？』
♪教えてよ〜地上の星を〜　『695氏、名無しの物体氏、そしてみんなが』
♪つばめよ〜地上の星は〜　『息を呑んで見守った到達点』
♪今どこに〜あるのだろう〜『2002年を我々は忘れない』

『巨大数の彼方に』〜熱き巨大数の季節を戦った男たち〜

国井アナ「今年最後のプロジェクトＸの時間です、今日は紅白で中島みゆきさんが黒部ダムからの中継
　　　　　がありますが、その2002年の最後を飾るにふさわしい、巨大数の物語を前後2回に渡って放送
　　　　　しました熱き男たちのドラマを、その後の話も含めて総集編をお送りします。
　　　　　それにしても、ついに巨大数もここまで来たかという感じですよねえ」
善場アナ「グラハム数・ふぃっしゅ数・そして新たに登場したバ−ド数、これらでさえもう
　　　　　想像不可能な領域なのに、その先の先なんて‥‥申し訳ないですが、もう想像
　　　　　さえできません。でも今回初めて嫌な展開もありましたね。」
久保ジュン「そうですよね、何か感じワル〜っていう書き込みが増えてきました。
　　　　　　でも、プロジェクトリ−ダ−の695さん始め、みなさんは本当によく辛抱しました。」
国井アナ「さあ、いよいよ計算不可能関数といわれたビジ−ビ−バ−関数の登場から話は
　　　　　再開していきます。（二人相手だと、話ずらいなあ‥‥‥‥）」

762 名前：裏番組 ：03/01/01 16:54

「ビートたけしの世界はこうしてダマサレタ」

たけし「ふぃっしゅの巨大数なんてのは、サイババの超能力と同じで
　　　　いかにも子供ダマシだよな。あんなのコロっと信じるのは
　　　　大晦日になると、何も考えずにNHKの紅白歌合戦見ちまうのと
　　　　一緒」
大竹まこと「その巨大数スレだけど、今年はお定まりの造反劇もあったね。
　　　　　　ま、オレらにいわせりゃ、なにを今更、って感じだけどさ」

763 名前：１３２人目の素数さん ：03/01/06 23:58

>>760>>761さん
毎回ご苦労様です。けっこう楽しみにしてます。

764 名前：１３２人目の素数さん ：03/01/09 00:28

保全

765 名前：１３２人目の素数さん ：03/01/10 12:57

>>699
消えた？

766 名前：１３２人目の素数さん ：03/01/11 13:38

今年も保全するぞ！
みなさん　たまには顔出して！