SICP 연습문제 1.10 친절한 풀이

문제

다음은 애커만 함수를 나타낸 프로시저이다.

(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)

다음 프로시저가 정의되어 있다고 하자.

(define (f n) (A 0 n))

(define (g n) (A 1 n))

(define (h n) (A 2 n))

(define (k n) (* 5 n n))

0보다 큰 정수n이 있을때 f,g,h 프로시저의 기능을 수학적으로 정의해 보라. 예를들어 (k n)은 $5n^2$이다.

문제로 부터 얻은 것

저는 처음에 이 문제를 풀때 어떻게 풀어야 하는 것인지 갈피를 못잡았습니다. 그런데, 머리로만 하려 하지 말고 노트를 펴고 하나 하나 계산하다 보니 의미를 알 수 있게 되었습니다. 여러분들도 노트를 펴고 차분히 계산해 보면서 수학적 의미를 파악하셨으면 좋겠습니다.

문제풀이

수식이 난해할 수 있으니 천천히 읽어주시기 바랍니다.

a. (A 0 n)

우선 (A 0 n)부터 하나 하나 계산해 보겠습니다.
(A 0 n)의 의미는 자명합니다. 항상 (* 2 y)를 반환하기 때문에, (A 0 n)은 2n입니다.

b. (A 1 n)

(A 1 1)부터 차례차례 계산해 보겠습니다.
(A 1 1) = 2
(A 1 2) = (A 0 (A 1 1)) = (A 0 2) = 4
(A 1 3) = (A 0 (A 1 2)) = (A 0 4) = 8
(A 1 4) = (A 0 (A 1 3)) = (A 0 8) = 16

규칙이 눈에 보이실 겁니다.
(A 1 n)을 g(n)이라 한다면, g(n)은 (A 0 g(n-1))이 되는 것입니다.
(A 0 n)이 2n이므로 g(n)은 결국 2g(n-1) 즉, 이전 결과를 2배하는 함수입니다.
g(1)이 2이므로 g(n) = (A 1 n) = $2^n$입니다.

c. (A 2 n)

(A 2 1)부터 차례차례 계산해 보겠습니다.
(A 2 1) = 2
(A 2 2) = (A 1 (A 2 1)) = (A 1 2) = 4
(A 2 3) = (A 1 (A 2 2)) = (A 1 4) = 16
(A 2 4) = (A 1 (A 2 3)) = (A 1 16) = $2^{16}$

규칙이 눈에 보이실 겁니다.
(A 2 n)을 h(n)이라 한다면, h(n)은 (A 1 h(n-1))이 되는 것입니다.
(A 1 n)이 $2^n$이므로 h(n) = (A 2 n) = (A 1 h(n-1)) = $2^{h(n-1)}$
h(1)이 2이므로 h(n)을 수식으로 나타낸다면, $2^{2^{2^{2^{...(n)}}}}$라고 표현할 수 있을것 같습니다.

미리보는 결론에서 말했듯이 처음에는 난감하게 보였던 이 문제는 하나하나 노트에 계산해서 풀면 쉽게 정리되는 느낌을 받을 수 있었습니다.
식을 해석하는 능력이 조금 상승한 것 같아서 기분이 좋습니다.

난해한 글 읽어주셔서 감사합니다.