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

質問

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

回答No.1

Tacosan · ベストアンサー

再帰が停止することはほとんど明らかだから, well-defined ですね.
どうしても証明したければ, 第1引数に対する数学的帰納法でどうぞ.

お礼

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

回答No.2

Tacosan

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

お礼

ありがとうございます。

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

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