巨大数生成アルゴリズム

質問

次のようなアルゴリズムで巨大数を生成していくのは効率がいいと言えますか
おそらく、いえると思いますが、これを論理的に示すにはどうしたらよいでしょうか？
1. F(a,b,0)=a+b , F(a,0,c)=a+c
　　F(a,b,c)=F(a,b-1,F(a,b,c-1))
2. F(a,b,c,0)=F(a,b,c)
　　F(a,b,0,d)=F(a,b,d)
　　F(a,b,c,d)=F(a,b,c-1,F(a,b,c,d-1))
3. F(a,b,c,d,0)=F(a,b,c,d)
　　F(a,b,c,0,e)=F(a,b,c,e)
　　F(a,b,c,d,e)=F(a,b,c,d-1,F(a,b,c,d,e-1))
・・・
おそろらく添え字か5つか6つ位でグラハム数オーダーではないかと思ったりしますが。。
いかがなものでしょうか？

回答No.3

Tacosan · ベストアンサー

そうそう, 忘れていたんだけど, 「だからどうしたの」という疑問はありますね.
Ackermann関数なら「原始帰納的でない帰納的関数を実際に作った」という意味があるんだけど, この関数はどのように意味を見出せばいいんでしょうか?単に「大きくなる」だけではちょっと....

お礼

ありがとうございます。

>この関数はどのように意味を見出せばいいんでしょうか?単に「大きくなる」だけではちょっと....
この関数を考えた経緯は、大きくなる関数を考えることに興味があることでしたが、再帰的に定義できる関数(終着できる関数)とそうでない関数の境目を考えることに繋がらないでしょうか？

回答No.5

Tacosan

重ね重ねすみません.
じっと見てみたら, Conway のチェーン記法と (境界条件が違うだけで再帰の式そのものは) 本質的に同じです.
「よく考えたら」と書いたにもかかわらず「ほとんど考えていない」ことが露見してますねぇ....

お礼

ありがとうございます。
こういうことを考えてみたのは単なる興味本位ですが
何か有用なことにつながるといいと思います。

回答No.4

Tacosan

すみません, よく考えてみたら 3引数の F(a, b, c) で Knuth の矢印記法と本質的に同じですね.
あっちは
F(a, b; k) =
1 if b = 0,
a^b if k = 1, and
F(a, F(a, b-1; k); k-1)
で定義してますから.
そこから Conway のチェーン記法にもちこむことはできるかも.

お礼

ありがとうございます。
初期条件や添え字の順番を無視したら
F(a,b,c)=a→b→cですね。
ですが、a→→bやa→→→bなどのオーダーに行くには添え字が何個くらいになればいいのかよく分かっていません。

回答No.2

stomachman

「効率がいい」がどういう意味かはともかく、添字の数を増やさないと先に行けないんじゃ、明らかにAckermann関数に負けてます。

お礼

ありがとうございます。

>添字の数を増やさないと先に行けないんじゃ、
添え字の個数が任意の場合について定義しているだけなので
添え字の数を固定しても先に進めると思います。

>明らかにAckermann関数に負けてます。
Ackermann関数の定義
http://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%83%E3%82%AB%E3%83%BC%E3%83%9E%E3%83%B3%E9%96%A2%E6%95%B0
を拝見した所、サリジェンヌ関数(質問の関数)が勝っていると思います。
ただ、本質的には同じようなものだと思います。

補足

すみません、アッカーマン関数の定義をよく確認してみると
A(m,0)=A(m-1,1)(第二添え字が増えている！)の部分はサリジェンヌ関数より強烈だったことに気付き
その点では、アッカーマンの方が勝っていると言えるように思いました。
ただ、それ以外の部分については、今でも余り差異がないと思います。

回答No.1

Tacosan

多分, 本質的に Ackermann 関数とか Knuth の矢印記法を拡張したものになってるんじゃないかな?
ちなみに「巨大数を効率的に生成する」という表現の意味は不明.

お礼

ありがとうございます。

>「巨大数を効率的に生成する」という表現の意味は不明.
少ない式や文字で大きい数を定義していくという意味です。
あるいは、増加の激しい関数を定義するということもできるかもしれません。