Ackermann関数より強烈に増加する関数

Fをアッカーマン関数とすると
F(m+1,0)=F(m,1) (mは0以上)が成り立ち、この関数は再帰的に定義できるようです。
これをF(m+1,0)=F(m,m)にしても再帰的に定義できるでしょうか？

No.1 ベストアンサー 回答者： Tacosan 回答日時： 2007/11/15 17:46

再帰が停止することはほとんど明らかだから, well-defined ですね.

どうしても証明したければ, 第1引数に対する数学的帰納法でどうぞ.

この回答へのお礼

ありがとうございます。
一生懸命頑張って数学的帰納法による証明を試みます。
ところでアッカーマン関数の定義で
F(m+1,0)=F(m,1) → F(m+1,0)=F(m,m) と変更することによって
増加率がよりますと思いますが、案外大した増加率の寄与ではないかもしれないと思っています。

お礼日時：2007/11/15 18:06

No.2 回答者： Tacosan 回答日時： 2007/11/19 17:28

Ackermann 関数そのものが「猛烈に増加する関数」なので, 「増加率がどのように変化するか」はわかりにくいはずです. という

か, どのように評価しましょうか.

この回答へのお礼

ありがとうございます。

>「猛烈に増加する関数」なので,
>「増加率がどのように変化するか」はわかりにくいはずです.
>というか, どのように評価しましょうか.
仰せの通り、基準がないと評価はしづらいですね。

あくまで勝手な予想なんですが、
アッカーマン関数 Ack(m+1,0)=Ack(m,1)と
サリジェンヌ関数 Sari(m+1,0)=Sari(m,m)をともに漸近展開して主要項が同じになるようにとることができるのではと思っているんです。

お礼日時：2007/11/20 22:31