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

187 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/10/29 11:11

ご無沙汰です。日本語の打てる環境がみつかりました。

Robertさんにふぃっしゅ数バージョン３を送ってみました。
Robertさんによれば、ふぃっしゅ数はビジービーバー関数を除けば、
彼のホームページに出現するいかなる数よりも大きいと述べた上で、
ビジービーバー関数がふぃっしゅ関数よりも大きいことを説明して
もらいました。

関数の大きさではかなわないものの、ふぃっしゅ数(バージョン３）
の大きさがどの程度のものなのかが分からなかったので聞いてみた
ところ、ビーバー関数f(x)のx=100から1000000くらいではなかろうか、
とのことでした。

やはり、ふぃっしゅ数は完敗のようです。
「ちゅーりんぐましーん」を使わずにビーバー(100)を超える数を
作った、というだけでもたいしたものだとは思いますが。

もちろん、ふぃっしゅ数定義の最初の関数をビジービーバー関数に
すれば、簡単にビジービーバー関数を超える関数を作ることは可能
ですが、それはあまり意味はないですね。

188 名前：& ◆UN5NpU6XaM ：02/10/29 11:17

ロバートさんからの返答を書く前に、ロバートさんに送ったふぃっしゅ数
バージョン３をそのままのせておきます。

********** Definition of Fish number and function **********

(1) First step: definition of s(1) mapping

S(1) mapping is a mapping from a pair of a natural number
and a function to a pair of a natural number and a function.
One of S(1) mapping, s(1), is defined by the following rule:

s(1):[m,f(x)] --> [g(m),g(x)]

where

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)

When I denote mapping in general, I use large letter S as
in S(1) mapping, and when I denote a special mapping, I use
small letter s as in s(1). This distinction will follow.

s(1):[m,x+1] --> [g(m),g(x)] gives the Ackermann function
g(x)=ac(x,x). Applying s(1) mapping to the Ackermann function
itself will yield even larger function.

189 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/10/29 11:19

(2) Second step: definition of s(2) mapping

S(2) mapping is a mapping from a set of a natural number and
a function and an S(1) mapping to a set of a natural number and
a function and an S(1) mapping. The mapping rule of s(2), one
of the S(2) mapping, is defined by:

s(2):[m,f(x),s(1)] --> [n,g(x),s'(1)]

where

s'(1)=s(1)^f(m)
s'(1):[m,f(x)] --> [n,p(x)]
s'(1)^y:[m,f(x)] --> [q(y),r(x,y)]
g(x)=r(x,x)

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

(3)が２重かきこで書き込めない。ちょっと一休み。

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

(3) Third step: definition of s(n) mapping (n>1)

In fact (2) is included here, when n=2.

S(n) mapping (n>1) is a mapping from a set of a natural
number and a function and S(1),S(2),...,S(n-1) mappings to a
set of a number and a function and S(1),...,S(n-1) mappings.
The s(n) mapping, one of the S(n) mapping, is defined by:

s(n):[m,f(x),s(1),s(2),...,s(n-1) -->
[n,g(x),s'(1),s'(2),...,s'(n-1)]

where

s'(n-1)=s(n-1)^f(m)
s'(n-1):[m,f(x),s(1),s(2),...,s(n-2) -->
[n,p(x),s'(1),s'(2),...,s'(n-2)]
s'(n-1)^y:[m,f(x),s(1),s(2),...,s(n-2) -->
[q(y),r(x,y),s''(1)(y),s''(2)(y),...,s''(n-2)(y)]
g(x)=r(x,x)

192 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/10/29 11:24

(4) Forth step: definition of ss(1) mapping

ss(1) mapping is a kind of S(1) mapping and defined by

ss(1):[m,f(x)] --> [n,g(x)]

where

s(m+1)^f(m):[m,f(x),s(1),s(2),...,s(m)] -->
[n,g(x),s'(1),s'(2),...,s'(m)]

g(x) is a function obtained by applying s(m+1) mapping to
[m,f(x),s(1),s(2),...,s(m)] f(m) times.

(5) Last step: definition of Fish number and Fish function:

Apply s(2) mapping 63 times to [3,x+1,ss(1)]:

S(2)^63:[3,x+1,ss(1)] --> [F,F(x),ss'(1)]

We get the Fish number F and the Fish function F(x).

193 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/10/29 11:26

ビーバー関数との比較については、後日また書き込みます。

194 名前：旧695 ：02/10/29 12:48

なんてこったいヽ(´ー｀;)ノ

195 名前：１３２人目の素数さん ：02/10/29 21:27

何という急展開
ふぃっしゅさんが来るといつも、一気にスゴイ展開になってしまうなあ
バ−ド数の全貌さえまだおぼろげなのに
ビジ−ビ−バ−関数‥‥‥言葉も無い‥‥。
ヴァ−ジョン３がｆ(x)のx＝100〜1000000なんて‥‥‥。

196 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/10/30 01:52

http://home.earthlink.net/~mrob/pub/math/ln-notes1.html#beaver
によれば、Ray Kurzweilが1999年にThe Age of Spiritual Machines
という本の中でビジービーバー関数について言及していて、その中で
the limits of human intelligence are reached well before BB(100)
「人間の知能の限界はBB(100)にも達しないだろう」と述べていますから、
BB(100)を超える数をチューリングマシンを使わずに定義したという
だけでも、実はたいしたことなのでしょう。

さて、新しい展開をしてみたくなってきたので、ロバートさんに
Going beyond Busy Beaver function というタイトルのメールを
送りました。

話の流れが一気にとんでしまうようなので、ビーバーに入る前に、
ふぃっしゅ数バージョン２がバード数よりも大きいことの説明から
入る方がいいのかもしれない。というか、バージョン２はバード数
を超えるために作ったものです。バージョン３はなんとなくバージョン
２をさらに拡張しただけです。本当はビーバー超えを密かにねらっても
いたのですが、それは無理でした。

197 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/10/30 08:24

いやはや、面白いことになってきました。ビジービーバー関数を超える
関数に関する考察をしてロバートさんに送ったところ、ロバートさん
からは「そんな関数はできない」との返事。

そんなはずはないので、いろいろと調べてまわったところ、どうやら
チューリングがすでにそのアイディアを提唱していたことがわかりました。

つまり、長年の間、多くの学者たちがチューリングマシンではあらわ
せないような関数を「チューリングの限界を超える」などとうたって
きたものの、実はチューリング自信がすでにチューリングマシンを
超える、ビジービーバーを超える関数についてはすでに提唱していた
ということです。そして、そのチューリングの考えと同じ考えに、
私が至ったわけです（考察そのものは非常に粗雑なものですが）。

チューリングの仕事を知らずして、チューリングと同じ考えにいたった
ことは、我ながらすごいことだと思います。

ちなみに、ふぃっしゅ数がBB(100)〜BB(1000000)であるという
ロバートさんの発言も、実はあまり信憑性がないようです。
>>196の前半に相当することをメールで書いたら、「やはり
ふぃっしゅ数はBB(100)よりも小さいのではないか」と言い出す
始末なので、その可能性もありますが、実はBB(10000000)を
超えている可能性も、BB(Graham)を超えている可能性も、
まだ完全に否定しきれないと思います。そのあたりを検証
するところまで、このスレがすすむかどうか。

ええと、まずはバード数の解析からでしたね。
まあ、のんびりといきましょう。

198 名前：旧695 ：02/10/30 09:22

ラスボス登場って感じですね。倒すのはともかく、また何か面白い展開が
あるといいんじゃないでしょうか。
あと、そろそろ巨大数サイトを作ってみたいところです。
悶々と資料をまとめようと思います。

199 名前：名無しのような物体 ◆plq.mziK0E ：02/10/30 12:18

ふぃっしゅっしゅさん、お久しぶりです。・・・Global IMEのインストールが無事に済んだ様で(ﾎﾞｿｯ

いよいよver．3のお目見えですね。ver．2と比べても格段に難解になっていますが、
何とか理解してみようと思います。(ところでver．2の解釈は上のやつであってますか？)

計算不可能な関数のはずであるBB（ｘ）と比較すると言うのも途方も無い話ですが、
それよりチューリングが提唱したと言うアイデアと言うのも気になります。探して見つかるかな？

200 名前：名無しのような物体 ◆plq.mziK0E ：02/10/30 12:19

ところで、皆さんにつかぬ事をお伺いしますが、皆さんの中で
数学を専門とされている方はどれくらいいらっしゃるのでしょうか？

･･･私？　いいえ、違います。何せ化学科の出なものでして･･･

201 名前：旧695 ：02/10/30 13:37

僕は魚介類をやってます。たまに絵を描きます。センター数学は30点でした(藁

202 名前：１３２人目の素数さん ：02/10/30 14:17

魚でも鳥でも全然構わんが、センターはもう少し取りなよ

203 名前：名無しのような物体 ◆plq.mziK0E ：02/10/30 17:28

>>188-192を和訳してみましたので、ご参考に。

（１）　s(1)写像の定義

S(1)写像は、自然数と関数のペアから自然数と関数のペアへの写像です。
S(1)写像のひとつであるs(1)写像は次のように定義されます。

s(1):[m,f(x)] --> [g(m),g(x)]　ただし

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)

以下、一般の写像を表すときは大文字のSを用い、
特定の写像を表すときは小文字のsを用いることにします。

s(1):[m,x+1] --> [g(m),g(x)] はアッカーマン関数を与えます。アッカーマン関数自身を
s(1)写像に適用することによって、さらに大きな関数が得られます。


（２）　s(2)写像の定義

S(2)写像は、自然数、関数、s(1)写像の組から自然数、関数、s(1)写像の組への写像です。
S(2)写像のひとつであるs(2)写像は次のように定義されます。

s(2):[m,f(x),s(1)] --> [n,g(x),s'(1)]　ただし

s'(1)=s(1)^f(m)
s'(1):[m,f(x)] --> [n,p(x)]
s'(1)^y:[m,f(x)] --> [q(y),r(x,y)]
g(x)=r(x,x)

204 名前：名無しのような物体 ◆plq.mziK0E ：02/10/30 17:28

（３）　s(n)写像の定義

S(n)写像(n>1)は、自然数、関数、s(1)、s(2)、･･･、s(n-1)の組から
自然数、関数、s(1)、s(2)、･･･、s(n-1)の組への写像です。
S(n)写像のひとつであるs(n)写像は次のように定義されます。

s(n):[m,f(x),s(1),s(2),...,s(n-1) -->[n,g(x),s'(1),s'(2),...,s'(n-1)]　ただし

s'(n-1)=s(n-1)^f(m)
s'(n-1):[m,f(x),s(1),s(2),...,s(n-2) -->[n,p(x),s'(1),s'(2),...,s'(n-2)]
s'(n-1)^y:[m,f(x),...,s(n-2) -->[q(y),r(x,y),...,s'(y)'(n-2)]
g(x)=r(x,x)


（４）　ss(1)の定義

ss(1)写像はs(1)写像の一種であり、次のように定義されます。

ss(1):[m,f(x)] --> [n,g(x)]　ただし

s(m+1)^f(m):[m,f(x),s(1),s(2),...,s(m)] -->[n,g(x),s'(1),s'(2),...,s'(m)]

g(x)は、s(m+1)写像をf(m)回適用して得られる関数です。


（５）　ふぃっしゅ数及びふぃっしゅ関数の定義

[3,x+1,ss(1)]にS(2)写像を63回適用した[F,F(x),ss'(1)]より、
ふぃっしゅ数Fとふぃっしゅ関数F(x)が得られます。

205 名前：１３２人目の素数さん ：02/10/30 19:02

206 名前：１３２人目の素数さん ：02/10/30 20:03

最高におもしろい展開になってきた！！！　　これからがこのスレの真骨頂でしょうね
「695さん」や「名無しの物体さん」やその他の「名無しさん達」が、がんばって解析してた甲斐があったすね。
にしても「ふぃっしゅさん」はやはりｽｺﾞｽｷﾞ、いったいどこまで行ってしまうのでしょう。
　実を言うと私はずっとスレ楽しんできましたがバード数の理解あたりでもう精一杯です。
ＢＢ関数はとてもじゃないけどふぃっしゅさん達の説明が無いと理解不可能です。


　ﾄｺﾛで上記のふぃっしゅさんの提唱したVer３ふぃっしゅ数はＳＳ‥‥‥ＳＳ変換の
形を取っているんでしょうか？（それすらわからなくなってきてる）
>>41>>42のﾚｽと>>73のﾚｽでVer３を他の人が提唱してますが、このあたりのやり方とは違うのでしょうか？　

特に>>73についてはふぃっしゅさん自身が>>78で「関数になりますね」と言ってるので‥‥。
この>>73のｱﾌﾟﾛｰﾁの説明文だと何とか理解できるのですが‥‥‥。

207 名前：１３２人目の素数さん ：02/10/30 20:52

まず、ふぃっしゅ数ｳﾞｧｰｼﾞｮﾝ２とバード数の対決詳細に期待

208 名前：旧695 ：02/10/31 02:56

強力無比のVer.3を、いじりながら理解してみます。第一段階の

　s(2)：[3,x+1,ss(1)] --> [n,g(x),ss'(1)]　を考えると、

　s'(1)＝s(1)^f(m)
　s'(1):[m,f(x)] --> [n,p(x)]
　s'(1)^y:[m,f(x)] --> [q(y),r(x,y)]
　g(x)＝r(x,x)　より　s'(1)の部分はここではss'(1)だから

　ss'(1)＝ss(1)^f(m)＝ss(1)^4　
　ss(1)^4:[m,f(x)] --> [n,p(x)]
　ss(1)^4y:[m,f(x)] --> [q(y),r(x,y)]
　g(x)＝r(x,x)

となり、まずはss(1)^4：[m,f(x)]から n が得られるようです。(添字をつけるとしたらn[1])

　ss(1)：[3,x+1]　を考えると、

ss(1):[m,f(x)] --> [n,g(x)]　ただし
s(m+1)^f(m)：[m,f(x),s(1),s(2),...,s(m)] -->[n,g(x),s'(1),s'(2),...,s'(m)]
g(x)は、s(m+1)写像をf(m)回適用して得られる関数　より、

　s(m+1)^f(m)＝s(4)^4　から
　s(4)^4：[3,x+1,s(1),s(2),s(3)]

この写像で得られる関数は、s(4)写像を4回適用して得られる関数とのことです。

209 名前：旧695 ：02/10/31 02:57

ここでs(4)写像はs(n)写像のn＝4のケースなので
　s(4)：[3,x+1,s(1),s(2),s(3)]　を考えると、

　s(4):[3,x+1,s(1),s(2),s(3)] --> [n,g(x),s'(1),s'(2),s'(3)]　ただし

　s'(3)＝s(3)^4
　s(3)^4：[3,x+1,s(1),s(2)] --> [n,p(x),s'(1),s'(2)]
　s(3)^4y：[3,x+1,s(1),s(2)] --> [q(y),r(x,y),s''(1)(y),s''(2)(y)]
　g(x)＝r(x,x)　となり、

　s(3)：[3,x+1,s(1),s(2)] --> [n,g(x),s'(1),s'(2)]　ただし
　s'(2)＝s(2)^4
　s(2)^4：[3,x+1,s(1)] --> [n,p(x),s'(1)]
　s(2)^4y：[3,x+1,s(1)] --> [q(y),r(x,y),s''(1)(y)]
　g(x)＝r(x,x)　からまた

　s(2)：[3,x+1,s(1)] --> [n,g(x),s'(1)]　ただし
　s'(1)＝s(1)^4
　s(1)^4:[3,x+1] --> [n,p(x)]
　s(1)^4y:[3,x+1] --> [q(y),r(x,y)]
　g(x)＝r(x,x)　そんで

　s(1)：[3,x+1] --> [g(m),g(x)]　ただし
　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)

210 名前：旧695 ：02/10/31 02:57

と、このようにどんどん下ってs(1)の計算に還元されてからまた昇って
いく模様です。これ以上はなんともならんので割愛。この後の流れは、
・s(1)^4　とs(1)^4y　で数と関数が得られる
・ここまで4回繰り返す(s(2)完了)
・ここまで4回繰り返す(s(3)完了)
・ここまで4回繰り返す(s(4)完了)
・ここまで4回繰り返す(ss(1)完了)
・ここまで4回繰り返す(第一段階完了)
みたいな感じですか(;´Д`)やばすぎ

211 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/10/31 05:55

それでは、バード数とふぃっしゅ数バージョン２の比較から。
バージョン３で表記を変えてしまったので混乱しますが（すみません）、
ここでは今までなれているバージョン２の表記をしておきます。

まずは、>>46 >>87 >>89 >>114 あたりを理解する必要があります。

>>87
Ｓ変換1回で 3→ がひとつ延長されるようです

>>89
SS1回で、だいたい矢印を1回転させるだけの効果があって、
SS2回で、矢印を回転させる回数を変数とするだけの効果があって、
SS3回で、さらに上の関数領域に到達する、というところでしょうか？

つまり、>>87によればS変換をm回繰り返すことで、f(x)=x→(m回)x
が生成されることになります。SS変換1回で、S変換をｘ回繰り返す
操作をしていますから、g(x)=x→(x回)x（実際にはこれよりも
大きい）という関数が生成されることになります。言い換えれば、
g(x)=x(↑1)[x]x程度の関数が生成できたわけです。というか、
このあたりのチェーンの計算は名無しのような物体さんが得意と
しているところですので、厳密な検証はお願いしたいところです。

212 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/10/31 05:59

さて、このg(x)にS変換をほどこすということは（実際にはＳ変換
そのものが大きくなっていますが、それを考えるとわけわからなく
なってくるので、最初のＳ変換で当面は考えてもいいでしょう）、
今度は(↑2)を使わないと表記できないような関数ができます。
ということは、g(x)にS変換をｘ回繰り返すことで、少なくとも
h(x)=x(↑x)[x]x 程度の関数ができます。

213 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/10/31 06:06

このように、SS変換２回にして、すでにx(↑x)[x]xができて
しまいましたから、後はバード数の表記を順に追っていけば
いいことになります。初期値の N = 3(↑G)[4]3 については、
SS変換２回でそれよりも大きな数ができています。

ひとたび関数 X(N) = N(↑N)[N]N （よりも大きな関数）が
できてしまえば、あとは X(N) から X_1(N) を生成させる
過程は、初期のＳ変換よりもずっと小さいＳ変換です（しょせん
は原始帰納的な定義なので、Ackermann にはかなわない）。
X_N(N)までの拡張も、原始帰納的な拡張なので、すべては
Ｓ変換１回にも満たない拡張です。

入れ子操作をX_H(N)回行った結果生まれる巨大数

とありますが、大きな関数ができてしまえば、あとはX_H(N)などと
いう数もすぐにできますし、その回数だけS変換を繰り返す操作も
SS変換に内包されていますから、せいぜいSS変換を３回も繰り返せ
ば、バード数を超えることは確実です。

214 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/10/31 06:08

バード数のようなあらゆる「表記法」をＳ変換で一般化したものが
ふぃっしゅですから、ひとたびチェーン回転関数よりも大きな
関数が生成されてしまえば、バード数のような表記法をいくら
繰り返しても、ふぃっしゅ数には追いつかないしくみになって
いるのです。

215 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/10/31 06:12

>>199
チューリングのアイディアはここです。
http://www.alanturing.net/turing_archive/pages/Reference%20Articles/hypercomputation/Intro%20to%20Hypercomputation.html
http://www.alanturing.net/turing_archive/pages/Reference%20Articles/hypercomputation/Turing's%20O-Machines.html

ふぃっしゅ数バージョン３の定義で、（１）s(1)写像の定義を、

s(1):[m,f(x)] --> [g(m),g(x)]
ここで、g(x)はf(x)を導入したO-machinesによって生成される
ビジービーバー関数

と変えれば、バージョン４ができるわけですが、これはもはや
解析しようとかなんとかいう範囲を飛び越えてしまいますね。

216 名前：名無しのような物体 ◆plq.mziK0E ：02/11/01 11:50

ビジービーバー関数について調べようと、ここしばらくぐぐっているのですが、
英語のサイトはうんざりするほどかかるのに、日本語のサイトは皆無に近いですね。
チューリングマシン(機械)でぐぐると両言語ともよくかかるのに･･･。

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

あんたら、すごすぎ。
695さんのおかげでなんとか、ついていってます。
数学がこんなにエキサイティングに感じたのは始めてです

218 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/02 02:12

いきなりバージョン４を見せても、たいていの人はなにが
どうすごいのかわからないでしょうから、巨大数のサイトを
作るとしたら、

グラハム数、バージョン１、チェーン関数、バード数、
バージョン２、バージョン３、ビジービーバー関数、
バージョン４、（はたしてバージョン５はできるのか？）

といった具合に、だんだんと数を大きくしていくように
説明を進めていくのがいいでしょうね。
このスレの流れがそうなっているわけですが。

普通の人が考えられるだけ大きな数を考えて、それよりも
グラハム数が大きい、ということにびっくりして、ところが
それよりもバージョン１が大きいというところでさらに
びっくりして、という風に、順々により大きいものを見せら
られれば、とりあえずバージョン２までは理解したが
バージョン３以降はわからない、という人も、なんだか
すごい数なんだな、ということは感じることができるでしょう。

私は、数学にとってもっとも重要なことは、役立つかどうか
ではなく、面白いかどうかだと思います。

大きな数を作ることに意味がなかったとしても、それに
面白さを感じる人がたくさんいれば、そのことに意味が
あるのでしょう。そして、私も多くの人が面白いと
感じているのを見て、より大きな数を作ろうという
気になり、結局バージョン４まで作ってしまいました。
なかなか楽しいです。

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

グーグルで「グラハム数」を検索すると、３番目にこのスレが。
グラハム数スレじゃないところが面白い。

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

http://www.google.co.jp/search?hl=ja&lr=&ie=UTF-8&q=+site:science.2ch.net+%E3%82%B0%E3%83%A9%E3%83%8F%E3%83%A0%E6%95%B0
どうやら、前スレはかからなかったけどこのスレはかかって、
しかもかなり上位にランクされているらしい。
グーグルのロボットが、このスレを面白いと感じて上位に
したのだろうか（ｗ

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

「ふぃっしゅ数」で検索したところ､このページがみつった。
http://hccweb1.bai.ne.jp/~hcd43301/sbbkle/read.cgi?thread=3-1&file=current
ここで紹介されているのがかかった原因か。
それにしても、この紹介文

14. 　名無しさん 　　投稿日： 10/7/2002 22:39
【ふぃっしゅ数】巨大数の探索スレ【ばーど数】
http://science.2ch.net/test/read.cgi/math/1033320305/

2chですが、もしかしたらここから世界最大の「意味の有る」数が
見つかるかもしれません。
外人さんも書きこんだりしてます。面白い。
というか初っ端のグラハム数で既に圧倒されます。


ふぃっしゅ氏が外人さんになっている（ｗ

222 名前：１３２人目の素数さん ：02/11/02 07:39

ふぃっしゅさんへ　695さんに代わって聞きます

＞＞S[3]＝((B^4)^(B^4･(B^4f[0](B^3f[0](B^2f[0](Bf[0](m[0])))))．
　　　　　　　f[0](B^4f[0](B^3f[0](B^2f[0](Bf[0](m[0])))))))^
　　　　((B^4)^(B^4･(B^4f[0](B^3f[0](B^2f[0](61)))))．
　　　　f[0](B^4f[0](B^3f[0](B^2f[0](61))))))^(((B^4)^
　　　　(B^4･(B^4f[0](B^3f[0](B^2f[0](61)))))．
　　　　f[0](B^4f[0](B^3f[0](B^2f[0](61))))))．
　　　　f[1](…(Bf[1](B^4f[0](B^3f[0](B^2f[0](61)))))…))．
　　　　(B^4(((B^4)^(B^4･(B^4f[0](B^3f[0](B^2f[0](61)))))．
　　　　f[0](B^4f[0](B^3f[0](B^2f[0](61))))))．
　　　　f[1](…(Bf[1](B^4f[0](B^3f[0](B^2f[0](61)))))…))．
　　　　f[0](((B^4)^(B^4･(B^4f[0](B^3f[0](B^2f[0](61)))))．
　　　　f[0](B^4f[0](B^3f[0](B^2f[0](61))))))．
　　　　f[1](…(Bf[1](B^4f[0](B^3f[0](B^2f[0](61)))))…))))

　S[3]＝B^k　とおくと(kが何を示すかは面倒なので割愛)、
　m[3]＝B^k．f[2](B^(k-1)．f[2](…(B^2f[2](Bf[2](m[2]))…)
となります。多分。これでいくと一般に
　m[n]＝S[n-1]^(f[n-1](m[n-1]))．f[n-1](S[n-1]^((f[n-1](m[n-1]))-1)．f[n-1]
　　　　(…(B^2f[n-1](Bf[n-1](m[n-1]))…)
〜中略
　m[63]＝S[62]^(f[62](m[62]))．f[62](S[62]^((f[62](m[62]))-1)．f[62]
　　　　(…(B^2f[62](Bf[62](m[62]))…)
がふぃっしゅ数Ver.2ということでよろしいでしょうか？

223 名前：旧695 ：02/11/03 01:53

http://mathworld.wolfram.com/BusyBeaver.html
ここではビジービーバーのn＝2，3，4の場合について視覚的に表現してますね。
意味はよくわかりませんが。

224 名前：名無しのような物体 ◆plq.mziK0E ：02/11/03 02:18

さらにオラクル+チューリングでぐぐっても結果は芳しからず。つーか、オラクル社ウザイ。
こうなったら図書館に行って･･･と思ったけど、そもそもこういう話って、数学のどの分野？

>>218
グラハム数から始まる巨大数サイトって･･･怖すぎ。

225 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 03:34

>>222
たぶん正しいと思いますが、時間をかけて考えてみたものの
正直よく分かりません。作成者本人も混乱するほどの関数を
解析していただき、ありがとうございます。

どうも、私は具体的な計算を苦手としているようです。
バージョン１のＳ変換を２回繰り返すあたりで、息切れです。
具体的な計算方法については私よりも695さんや名無しのような
物体さんが深く理解しているように思いますので、お２人が
納得したところで、正しいとしてください。私は、一般化した
話に的をしぼっていきたいと思います。

さて、これだけでは寂しいので、私なりにふぃっしゅ数の
大きさを説明しようと思います。長文です。

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

まずはふぃっしゅ数バージョン１の制作過程について。
これは、定義を書くときにかなり（私的には）わかりやすく
書いたつもりなのですが、もう一度説明を試みます。

ここでは「原始帰納的な定義」というのがキーワードに
なろうかと思います。

Ackermann関数のすごさがどこにあるかというと、加減乗除、
べき乗といった関数を使って「原始帰納的に」定義した
いかなる関数よりも、Ackermann関数が大きいことです。
２項漸化式は、１項漸化式よりも偉いということです。

# ３項以上については、前スレで予想を書いたように２項の
# 繰り返しで表現できてしまうような気がしていて、１項から
# ２項へ増えたような「革命的な」増加は期待できないのでは
# ないのかと思っています。検証は難しそうですが。

227 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 03:37

前スレの最初ではべき乗がもてはやされていましたが、
「ｘにｘ乗をｘ回繰り返して、それにｘ乗をｘ回繰り返して、
…といった操作をｘ回繰り返して、…」といった方法が、
関数を大きくし、そして大きな数を作るメインの手法でした。

ところが、Ackermann関数はこういった「原始帰納的に」
定義されたいかなる関数よりも大きいのです。

さて、グラハム数はAckermann関数を下敷きに定義された数
ですが、その定義はAckermann関数をもとに原始帰納的に
定義しています。ということは、Ackermann関数をもとに
Ackermann関数的な拡張をほどこせば、グラハム数を超えて
しまうということです。

この「Ackermann関数的な拡張」を一般化したものが初期の
Ｓ変換です。

228 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 03:39

言葉というのは面白いもので、ひとたびAckermann関数的な
拡張をＳ変換として定義してしまえば、Ackermann関数を
使って原始帰納的な表記をいくら繰り返しても表現できない
ような数を、Ｓ変換を２回する、といった簡単な表記で
あらわせてしまいます。

ある一定の表記法の元でがんばって大きな数を作ろうと
しても、それよりも上位の表記法を使って簡単に表せる
数よりも大きくはなりません。ちょうど、グラハム数が
チェーン回転関数でいとも簡単に追い越されてしまったように。

そして、私の思考は常に「いかにして上位の表記を作るか」
というところにあります。

229 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 03:39

さて、チェーン回転関数の定義は、Ｓ変換１回がチェーンを
１回転させることに相当するような関数です。ということは、
チェーン回転関数は、Ｓ変換Ｘ回分の関数になります。

このチェーン回転関数をみたときに、バージョン１は敗れたと
思いました。敗れたというのは「いかに上位の表記を作るか」
という点で、Ｓ変換の数をふやしていくだけのバージョン１
よりも上位の表記を作成されてしまった点です。

230 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 03:40

バード数の作成過程を見ると、チェーン回転関数を定義した
あとは、原始帰納的な拡張の繰り返しなので、このあたりは
正直稚拙だなと感じましたが、「Ｓ変換をＸ回繰り返すことに
相当する関数」を定義する操作を一般化すればバード数は
簡単に超えることに思い至りました。この操作を一般化して
しまえば、チェーン回転関数は「序盤の通過点」になって
しまいます。

231 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 03:41

バージョン２がバード数を遙かにしのぐ関数であることは、
すでに説明した通りですが、バージョン２の大きさについては、
「Ｓ変換をＸ回繰り返す操作」を定義してしまったことの
すごさを理解すれば、少しは感じることができると思います。

ＳＳ変換２回で、チェーン回転関数の領域に到達しますが、
ＳＳ変換３回で、どんな関数が生成されるのでしょうか。

まずはＳＳ２回＋Ｓ１回を考えます。実は、この時点で
すでに通常の表記では表記不能な関数になっています。

それはそうです。なにしろ、チェーン回転関数から原始
帰納的に定義できるあらゆる関数よりも大きな関数なの
ですから。チェーン回転関数よりも上の次元の関数を定義
しない限り、その大きさはあらわせません。

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

ここまでの考察より、ＳＳ変換を３回繰り返すことで、
今まで多くの人が巨大数や巨大関数を作ろうとしたで
しょうが、それらのどれよりも大きな数が生成されるで
あろうことが予想されます。ビジービーバー関数とか
チューリングマシン、O-machinesといった特殊な概念を
使った関数や数を除きます。

逆に、ＳＳ変換３回分よりも大きな数や関数が定義されて
いるとしたら、ぜひ知りたいところです。

233 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 03:43

さて、バージョン２ではこの「ＳＳ変換を何回繰り返す」
という操作によって、大きな数を作りました。この「何回」
の部分を大きな数（たとえばグラハム数）にすれば、
どんどん大きな数ができますが、それではより一般化した
段階に到達したことにはなりません。ふぃっしゅ数回
繰り返す、といった表記でさえも、不十分です。

ＳＳ変換を何回繰り返す、という操作を一般化してはじめて、
次の一般化の段階に到達します。

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

そこで、ＳＳＳ変換を定義することになります。
すなわち、ＳＳ変換をｎ回繰り返させるわけです。
そうすると、ＳＳＳ変換を何回か繰り返した数はとてつも
なく大きな数になっていますから、それにＳＳＳ変換を
繰り返すということは、ＳＳ変換を繰り返させる数が
ふぃっしゅ数よりも遙かに大きいため、「ＳＳ変換を
ふぃっしゅ数回繰り返す」といった表記でも到達しえ
なかった領域に、いとも簡単に到達してしまいます。

さらに、関数についてはＳＳ変換をＸ回繰り返す、
という操作を加えることで、ＳＳ変換を一定回数繰り返す、
といった操作では実現できないような大きな関数ができます。
そこで、この概念も取り入れてしまいます。

235 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 04:02

このようにして、Ｓ変換、ＳＳ変換、ＳＳＳ変換といった
定義ができれば、SSS...S変換を定義することは簡単です。
ではいったい何回繰り返させればいいでしょうか。
SSS...（ふぃっしゅ数回）.Sというのでは、不十分です。
なぜならば、その回数はたかがふぃっしゅ数だからです。
回数そのものが増えるしくみをつくれば、さらに大きな
数の領域に突入します。

それがバージョン３です。ここでは、SS..(n回)..Sといった
表記が醜いため、表記を変えてしまいました。
SS..(n回).S変換をs(n)変換と表記します。

236 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 04:02

このs(n)のnを、種となる数から持ってくるようにして
新しい変換を定義すれば、その変換を何回か繰り返すことで、
nの数が爆発して、

「SS..(ふぃっしゅ数回)..Sでできた数の分だけ、SS..Sを
繰り返した変換の…」

といった表現では追いつかない数を定義することができます。
かくしてss(1)変換を定義したわけですが、これにs(2)変換
（旧SS変換）を63回繰り返す、とすることで、バージョン２と
同じような表記法できれいにバージョン３を定義することが
できました。

237 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 04:03

ここから先、定義を拡張するとすれば、s(1)変換からss(1)
変換を生成した過程をss(2)変換とみなして、同様にして
ss(n)変換を定義し、その定義が確定すればsss(1)変換、
sss(n)変換が定義できて、ss..(n回)..s(n)変換が定義
できて、この際だからss..(n回)..s(n)変換でできる数を
関数f(n)で定義してしまうか…という感じで続いていく
ことでしょう。

こういった一般化の手法は、バージョン３で道筋をつける
ことができたと考えています。ためしに、この先どうやって
一般化するのかを考えてみるのも一興でしょう。ここまで
くると、あとは「演習問題」のようなものです。したがって、
こういった手法を爆発的に凌ぐような手法が開発されない
限り、バージョン５を定義する価値はないと思っています。

238 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 04:04

上位の概念を導入することで、はじめて爆発的な数の増加が
得られる、といったことを素直に定義として表現したものが
ふぃっしゅ数です。バージョンがあがるにつれて、その
概念が上位になっていきます。

239 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 04:05

続いて、ここから先バージョン４へ進むためには、ビジー
ビーバー関数に関する理解が避けて通れないわけですが、
そもそもビジービーバー関数ってバージョン３と比べて
どうなの？という疑問があります。

ビジービーバー関数については、いろいろと考えるところ
があって、ふぃっしゅ関数バージョン３よりもビジービーバー
関数が大きい、という点についても、まだ完全に納得でき
ないでいます。

240 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 04:06

ロバートさんの説明は、おおまかにいって

(1) ふぃっしゅ数（バージョン３）を計算するプログラムを
LISPまたはSmall Talkで書くことができる。
(2) (1)で書いたプログラムを、一定数Ｓの状態数を持つ
　チューリングマシンであらわすことが可能である。
(3) したがって、ふぃっしゅ関数はBB(S)程度の大きさだろう。
(4) Sの値は、100〜1000000程度でないか？（その後、100
　以下に格下げ）

といった感じです。私の疑問は、(1)(2)(4)にあります。

241 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 04:07

(2)の疑問は

　「プログラミング可能であれば、必ず一定の状態数を持つ
　チューリングマシンで表現できる」というのは早計ではないか？
　もしそうだとすれば、ビジービーバー関数をシミュレーション
　で求めるプログラムを一定の状態数を持つチューリングマシンで
　表現できることになり、矛盾を生じないか？」

というものです。

この点については、かなり本質的な疑問であるように感じます。
ひょっとすると、少なくともふぃっしゅ数分の１以上の確率で、
計算理論を揺るがすような疑問かもしれませんが、私が根本的な
勘違いをしている可能性の方が大きいです。なにしろ、なにも
勉強していませんから。

本格的に勉強をしないとなんとも分からないので、ひとまず
おいておきます。

242 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 04:09

そうすると、(1)(4)の疑問が残ります。

(1)(2)が示されれば、少なくともふぃっしゅ関数よりも
ビジービーバー関数が大きいことが示されるわけですが、
関数が大きいことが必ずしも大きい数を生み出すとは
いえません。そのあたりが(4)のようにSを小さく見積もって
いることに対する疑問になるわけですが、(4)の疑問に
関しては、どうも(1)で具体的にプログラムを作って
みないことには、なかなか議論できないように感じます。

243 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 04:46

そこで、まずは(1)の疑問、はたして本当にふぃっしゅ数を
計算するプログラムを書くことができるのだろうか、
といった点がポイントになります。ロバートさんによれば、
LISPやSmall Talkには、自分自身をコンパイルする能力が
あるから、プログラム可能になるそうです。本当なのか。

LISPもSmall Talkも知らないので、私は全くのお手上げ状態
です。プログラムには詳しいであろうロバートさんが「できる」
といっているのですから、できるのだろうと最初は思って
いましたが、やはりここは現物を見せてもらって「ほら、
できたよ」と言われないと、なんとなくすっきりしない
ものです。

244 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 04:48

プログラム言語は問わないので、どなたかふぃっしゅ数
バージョン３のプログラムを書ける人はいますか？
もちろん、メモリや計算時間の制約は無視します。

いわゆるs(n)変換のようなものを、いかにしてプログラムで
記述するか。入力、出力ともに数、関数、複数の写像となって
います。関数を定義するだけのプログラム言語では、けっこう
難しいはずです。

実際に走らせて検証することができない（いつまでたっても
計算が終わらない）プログラムなので、かなり特殊かも。

というよりも、ビジービーバーをシミュレートさせる
プログラムよりも、書くのが難しくないですか？

245 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 04:49

いろいろと分からないなりにも、ビジービーバー関数の
定義を見て、なんだ、チューリングマシンにビジービーバー
関数を取り込めば新しいビジービーバー関数ができて、
これはビジービーバー関数からformal systemで定義できない
ほどの大きさの関数になるんじゃないのか？
と思って、ロバートさんにメールを送ったのですが、
ロバートさんは「そんなことはできない」と簡単に否定
しました。それどころか、その前ふりとしてx+1のかわりに
BB(x)を初期値としたビーバーふぃっしゅ数を示した段階で、
すでにそれは不可能だとしてしまったのです。

「そんなはずはなかろう、同じ発想をしている人はいるん
じゃないのか？」と思い、よく調べてみると、それがまさに
O-machinesだったわけです。

どうも、ロバートさんは「ビジービーバー関数よりも大きな
関数は定義できない」という風に思いこんでしまっていた
ようです。それとも、プログラムで書けるものだけが関数だ、
と考えているのがプログラム屋さんなのでしょうか。
数学的な目から見ると、プログラムで書けようが書けまいが、
明確に定義されていれば関数なのですが。

246 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 04:50

ちなみに、バージョン４のＳＳ変換で生成される関数は、
O-machines的な拡張を何回繰り返しても到達しえない関数
なので、最強です。ビーバー君がいくら走り回っても
届きません。比較するとすれば、チューリングに対抗した
いくつかの論文があるので（アナログシフトとか）、
そういったものと比較することになりそうですが、
そこまでいくと専門家に登場してもらわないと無理そうです。

ところが、この最強関数にさらにO-machines拡張を繰り返す
のが、ＳＳ１回＋Ｓ１回だったりするわけで、そうなると
どう表現していいのやら。

結局、ふぃっしゅ数バージョン４はどの程度の大きさ
なのかというと、まあ要するにわけがわからないと、
そういうことです。面白いのは、わけがわからないほど
大きい数ですが、それはきちんと定義されたある１つの
自然数にすぎない、ということです。大きさは見当もつか
ない。だけど明確に定義はできる。面白いですね。

247 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 04:50

最後に、雑感を一つ。アレフ０，１，２のように、無限集合の
密度を増やしていく理論とか、関数の大きさを大きくする
理論（計算可能であるとか不可能であるとか）には、多くの
数学者たちがおもしろがって研究しているのに、大きな有限の
数を作ることに関しては、おもしろいと感じる人は少ないの
でしょうか、数学者は誰もまともに取り組んでいないように
感じます。まともに取り組めば、私が発想するようなことは
簡単に思いつくでしょうから。ここで「関数」ではなくて
あくまでも「数」を問題にしているところに注意してください。
巨大数を作る過程においては、関数はあくまでも手段にすぎ
ないのです。

248 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 04:51

そして、それがこのスレに数学を専門としている人が居着か
ないか、来てもきっと「意味がない、くだらない」程度の認識
しかしないで去っていく一因ともなっているのでしょう。
つまり、数学者は大きな自然数を作ることには魅力を感じて
いない、と私は感じるのです。

# その前に、そもそも数学板にどの程度の数学者がいるのか、
# といった疑問はありますが。

249 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 04:52

私としては、有限の範囲内で大きな数を作る、ということは、
たとえそれがグラハム数のように意味のある数ではないと
しても、非常に面白いことだと感じます。いえ、当初は
それほどでもありませんでしたが、皆さんが楽しんでいるのを
見て、より面白いと感じてきた、というのが正直なところで
しょうか。

皆さんも、面白いと感じていただけたら、せいぜい「大きな数」
をあらわすたとえとしてでも使ってください。それくらいしか
使い道はないでしょうから。たとえとして使う分には、バージョン
１でも４でも同じことなので、バージョンは意識しないでいい
と思います。

　「ふぃっしゅ数回お願いされてもだめといったらだめだ！！」
　「じゃあ、ふぃっしゅ数＋１回お願いします。」

２ちゃんねるではやらせるのは、さすがに無理がありそうですが。

250 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 04:53

私が考えていることを分かりやすく表現したつもりですが、
ビジービーバー関数以降に関しては、かなりちんぷん
かんぷんかもしれません。なにしろ、私自身がすっきり
していないのですから、当然ですね。英語で書いても
日本語で書いても、結局誰かの翻訳がないと理解されないの
だろうか。

長文失礼しました。

251 名前：１３２人目の素数さん ：02/11/04 08:27

いやいや、ご苦労様でした
みんな、ふぃっしゅさんの書き込みをわくわくしながら
待ってると思いますよ

252 名前：１３２人目の素数さん ：02/11/04 08:57

これがヴァ−ジョン４なんでしょうか？
『ＳＳ‥‥とＳの数を爆発的に増やすのがヴァ−ジョン３
　これで拡張のステ−ジ（次元）がワンランク上がったわけで
　それをｎランク上げていき、そのｎを拡張するのがヴァ−ジョン４』？

237 ：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/04 04:03
＞＞ここから先、定義を拡張するとすれば、s(1)変換からss(1)
　　変換を生成した過程をss(2)変換とみなして、同様にして
　　ss(n)変換を定義し、その定義が確定すればsss(1)変換、
　　sss(n)変換が定義できて、ss..(n回)..s(n)変換が定義
　　できて、この際だからss..(n回)..s(n)変換でできる数を
　　関数f(n)で定義してしまうか…という感じで続いていく
　　ことでしょう。

スマソ、ヴァ−ジョン４がどれなのか明確に書かれてないので
ただ、上文の流れからいくとこれしか思いつかないのですが……。

253 名前：旧695 ：02/11/04 10:27

>>252
Ver.4の定義は>>215のものになるかと思われます。
Ver.3の根っ子がアッカーマンじゃなくてビジービーバーになるやつ。

>>ふぃっしゅ氏
お疲れ様です。数学屋から見てくだらない、価値がないなんてものに
ますます魅かれる自分がいます。技量や嗜好が合っているんだと思います。
それはさておき、今の自分の関心事としては、

・チューリングマシンの持つ一定の状態数とは？
・ビジービーバーは要するにどんな関数？
・Ｏ-マシーンはビジービーバーとは違うもの？

てな具合です。英語が苦手なので。
あとサイトについては、年内をメドにできれば(;´Д`)

254 名前：名無しのような物体 ◆plq.mziK0E ：02/11/04 15:05

>>211
> このあたりのチェーンの計算は名無しのような物体さんが得意と
> しているところですので、厳密な検証はお願いしたいところです。


いやあ・・・( ;´Д`)　私はただ規則にのっとって地道に計算しているだけですよ？
厳密さも保証できませんし。･･･ほんと、他にもやってみてくださる人、いませんか？
とりあえず、当方の理解が間違っていないことを前提に検証しておりまふ。
亀レス御免

>>253
チューリングマシンのサイトでしたら、日本語のものもいくつかあります。
ttp://kitchom.ed.oita-u.ac.jp/~jyo/proh09/mkiribu/erabi.html
ここなら実際に動いている様子が観察できるので、わかりやすいでしょう。

さて、N個の状態からなるチューリングマシンには、例えば次のような「プログラム」が施されます。

状態Aで0を読み取り⇒状態をDにして1を上書き、左に移動
　〃　　　1を読み取り⇒状態をBにして0を上書き、右に移動
状態Bで0を読み取り⇒状態をAにして1を上書き、右に移動
　〃　　　1を読み取り⇒状態をCにして1を上書き、右に移動
・・・・・・・・

「入力」は2N種類、対して「出力」は停止状態も考慮に入れますので4(N+1)種類が考えられます。
したがって、N個の状態からなるチューリングマシンは4(N+1)^2N種類存在するわけです。
この全てのチューリングマシンに0だけかかれたテープを挿入して動かしたとき、
あるマシンは永久に止まりませんが、あるマシンは有限個の1を書いて止まります。
このとき、一番多く1を書いたマシンが書いた1の数がBB(N)となるのです。

おまけ(レゴブロックでできたチューリングマシン)
ttp://member.nifty.ne.jp/mindstorms/gallery/k025.html

255 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/05 07:29

http://home.earthlink.net/~mrob/pub/math/largenum-5.html

ここのビジービーバーのところに書いてあるところを理解しようと
しているのだけど、ここで解説されているformal systemって、
要するに記号(symbol)や関数(function)定義していく過程を言って
いるわけですよね。

はたして、関数よりも上位の概念であるs(n)変換のようなものまでも
formal systemの仲間入りをするものなのかどうか。
s(n)変換こそが、まさに

Attempts to go beyond the Busy Beaver function, by necessity,
have to go beyond functions, algorithms and formal systems.

ここで言われている function を超えた概念なのではないのか、
などと妄想したりしていますが、はたしてどうなんでしょう。

formal system を和訳するとどうなるんだろう？

256 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/05 07:46

というか、ふぃっしゅ数バージョン３を求めるプログラムを、
LISPその他のプログラム言語でどうやって書けるのかを知りたいの
だけど、プログラム系の板で聞かないとわからないかな？

かといって、プログラム系の板ではふぃっしゅ数の定義を理解され
ないで終わってしまうという罠もあるかもしれない。

257 名前：１３２人目の素数さん ：02/11/05 08:00

たぶん大丈夫。別に大きさの評価をしているわけじゃないし

258 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/05 08:08

>>257
では、後日またプログラム系の板を見てまわって、ふわさしいスレを
みつけて聞いてこようと思います。

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

prologとかどうでしょか

260 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/06 11:37

prologだと、たとえば>>203のs(1)写像やs(2)写像は
どのように記述できますか？

261 名前：１３２人目の素数さん ：02/11/06 18:46

>>260

>>203 を参考にして elisp で s(1) を書いてみた。
f はひとまずアッカーマンになるのをデフォルトに。

再帰が深くなってすぐ使い物にならなくなるんで、実際に計算やらすなら
ループに書き直さないといけないな。

(defvar f (lambda (n) (1+ n))
"Define f(n).")

(defun g (x)
"Return g(x)."
(B x x))

(defun B (m n)
"Return B(m,n)."
(cond
;; B(0,n) = f(n)
((= m 0)(funcall f n))
;; B(m,0) = B(m-1,1)
((= n 0)(B (1- m) 1))
;; B(m,n) = B(m-1, B(m, n-1))
(t(B (1- m) (B m (1- n))))))

262 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/07 03:01

>>261
さっそく書いていただきありがとうございます。
f(x)からg(x)を計算するところはわかりました。

# elisp は知りませんが、見ればだいたい雰囲気は
# つかめます。

一番上の２行がよくわかりませんが、これはf(n)=n+1
と定義していることに相当するのでしょうか？

s(1)変換は、関数から関数への写像ではなく、
「数と関数の組」から「数と関数の組」への写像です
ので、まずは「数と関数の組」を変数の型のとして
定義し、その変数に対して行う演算をs(1)として
定義する必要があります。そうすれば、たとえば
[3,f(x)=x+1]に対してs(1)を計算させる、といった
演算を簡単に記述できるはずです。

このように定義に沿ってプログラムしていかないと、
とてもs(n)の計算まで拡張はできないと思います。

s(n)の定義を記述しようとすると、「数と関数と
複数の写像」の組を一つの変数の型として定義し、
それに対する演算を定義する、といった記述が
必要になってくるはずです。このあたりを見て
みたいのです。

263 名前：ふぃっしゅっしゅ ◆/T2GtW187g ：02/11/07 03:02

これから先、s(n), ss(1)と進むと、実際に計算を終了
させるのは不可能になりますので、計算時間とかメモリ、
スタックなどの制約は一切考えずに、定義をそのまま
きれいにプログラムに書く、という方向で最初は考えて
いければと思います。

そして、プログラムができれば、あとは実際にその
プログラムをelispがどう解釈して実行していくの
だろうか、といった考察に入ることができます。

とりあえずこのスレッドでいけるところまでいってみて、
行き詰まるようでしたらプログラム技術板で聞いてみようと
思います。行き詰まった個所が明確になれば、質問も
しやすいですし。