1.10

Exercise 1.10.  The following procedure computes a mathematical function called Ackermann's function.

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

What are the values of the following expressions?

(A 1 10)

(A 2 4)

(A 3 3)

Consider the following procedures, where A is the procedure defined above:

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

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

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

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

Give concise mathematical definitions for the functions computed by the procedures f, g, and h for positive integer values of n. For example, (k n) computes 5n².

(A 1 10 ) 풀이

( A 1 10 )  = > 1024

( A 1 ( A 1 9) )  = 512

( A 1 ( A 1 (A 1 8 ) )  = 256

( A  1 ( A 1 ( A 1 (A 1 7 ) ) ) = 128

( A  1 ( A  1 ( A 1 ( A 1 (A 1 6 ) ) ) ) )

....

( A 1 .... ( * 2 1 ) )

(A 2 4 ) 풀이

( A 2 1 )  = > 1

( A 2 2 ) = >  4 -> 2^2

( A 2 3 ) = >  16 -> 2^(2^2)

( A 2 4 ) = >  65536 -> (2^(2^(2^2)))

1. f => 2n

(define (f n) (A 0 n)) 일때 A 함수를 따르면

x = 0 이므로 ( * 2 y )  이다.

답은 f(n) = 2n

2. g => 2^n

3. h => if n = 0 :  f(x) = 0

            if n = 1 :  f(x) = 2^1

            if n >= 2 : f(x) = 2^f(x-1)

 나오는 순서도는 생략 ㅡㅡ 너무 쓰기 힘듬 ...