SICP: Exercise 1.10

アッカーマン関数

$$ A(x, y) = \begin{cases} 0 & \text{if $y = 0$} \\ 2y & \text{if $x = 0$} \\ 2 & \text{if $y = 1$} \\ A(x - 1, A(x, y - 1)) & \text{otherwise} \end{cases} $$

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

の値を求める問題。 初めに (A 1 10)、(A 2 4)、(A 3 3) の値を求めよ、となっているが、置換モデルでいくと膨大な数の置換に辟易すること間違いなしなので、しばらく置いておく。

後半に x が小さい場合の一般化を行う問題がヒントとして配置されているので、先にそちらを行う。

後半

まず、(define (f n) (A 0 n)) について

(f n)
(A 0 n)
(* 2 n)

より、\( \mathtt{(f\ n)} = 2n \) である。

次に、(define (g n) (A 1 n)) について

(g n)
(A 1 n)
(A 0 (A 1 (- n 1)))
(f (A 1 (- n 1)))
(f (A 0 (A 1 (- n 2))))
(f (f (A 1 (- n 2))))
…
(f … (f (A 1 (- n (- n 1)))) … )
(f … (f (A 1 1)) … )
(f … (f 2) … )

さて、問題は f がいくつあるかだが、これは A の 2 番目の引数である (- n a) の a と対応する。そのため、8 行目から \( n - 1 \) 個あることが分かる。したがって

$$ \begin{align*} \mathtt{(g\ n)} &= \underbrace{\mathtt{(f}\ \cdots\ \mathtt{(f}}_{n - 1}\mathtt{\ 2)}\ \cdots\ \mathtt{)} \\ &= \underbrace{\mathtt{(*\ 2}\ \cdots\ \mathtt{(*\ 2}}_{n - 1}\mathtt{\ 2)}\ \cdots\ \mathtt{)} \\ &= \underbrace{2 \cdots 2}_{n - 1} \cdot 2 \\ &= 2^n \end{align*} $$

となる。

同様に、(define (h n) (A 2 n)) について

(h n)
(A 2 n)
(A 1 (A 2 (- n 1)))
(g (A 2 (- n 1)))
(g (A 1 (A 2 (- n 2))))
(g (g (A 2 (- n 2))))
…
(g … (g (A 2 (- n (- n 1)))) … )
(g … (g (A 2 1)) … )
(g … (g 2) … )

で、g は \( n - 1 \) 個あるから、今度は 2 を肩に乗せていくような感じで

$$ \mathtt{(h\ n)} = \begin{cases} 2 & \text{if $n = 1$} \\ 2^{\overbrace{2^{\cdots^{2}}}^{n - 1}} & \text{if $n \geq 2$} \end{cases} $$

となる。

前半

さて、一般化できたので前半に手をつける。

$$ \begin{align*} \mathtt{(A\ 1\ 10)} &= \mathtt{(g\ 10)} = 2^{10} = 1024 \\ \mathtt{(A\ 2\ 4)} &= \mathtt{(h\ 4)} = 2^{2^{2^2}} = 2^{2^4} = 2^{16} = 65536 \\ \mathtt{(A\ 3\ 3)} &= \mathtt{(A\ 2\ (A\ 3\ 2))} = \mathtt{(h\ (A\ 2\ (A\ 3\ 1)))} = \mathtt{(h\ (h\ 2))} = \mathtt{(h\ }2^2\mathtt{)} \\ &= \mathtt{(h\ 4)} = 65536 \end{align*} $$

となる。