アッカーマン関数とは？

アッカーマン関数の意味

2つの非負整数を引数に取り、再帰の深さが爆発的に増える関数。Ack(0,n)=n+1、Ack(m,0)=Ack(m-1,1)、Ack(m,n)=Ack(m-1,Ack(m,n-1)) と定義され、内側の呼出しの結果が外側の引数になる入れ子構造をもつ。原始再帰では表せない全域関数の例として知られ、値の増え方が極端に速いことから、再帰の理解を試す題材として繰り返し出題される。値を求めるときは定義の3本の式を機械的に当てはめ、内側から順に展開していくのが確実である。

アッカーマン関数の具体例

Ack(1,3) を求めるには、Ack(1,0)=Ack(0,1)=2 → Ack(1,1)=Ack(0,Ack(1,0))=Ack(0,2)=3 → Ack(1,2)=Ack(0,3)=4 → Ack(1,3)=Ack(0,4)=5 と、mが小さいほうから順に確定させていく。Ack(4,2) は既に2万桁近い値になり、素直に計算することはできない。

アッカーマン関数は試験でどう引っ掛けられる？

外側から展開しようとして途中で行き詰まる誤りが定番で、内側の Ack(m,n-1) を先に確定させるのが正しい順序である。Ack(m,0) の場合に Ack(m-1,0) としてしまう誤りも多い（正しくは Ack(m-1,1)）。定義の3本目だけを見て「必ず引数が1つずつ減る」と考えないこと。

アッカーマン関数と関連する用語

• 再帰
• スタック
• 計算量

アッカーマン関数が出た過去問

• 非負の整数m、nに対して次のとおりに定義された関数Ack(m, n)がある。Ack(1, 3)の値はどれか。 Ack(m, n) = Ack(m-1, Ack(…

  正解：5

  要点：アッカーマン関数は定義に従い内側から順に展開する

  m=0のときAck(0,n)=n+1であることを使って内側から順に展開する。Ack(1,0)=Ack(0,1)=2、Ack(1,1)=Ack(0,Ack(1,0))=Ack(0,2)=3、Ack(1,2)=Ack(0,Ack(1,1))=Ack(0,3)=4、よってAck(1,3)=Ack(0,Ack(1,2))=Ack(0,4)=5となる。

  出典：平成30年度 春期 高度共通_午前I試験 am1 問2（IPA）