«
»

Exercise 1.10

Given the following implementation of the Ackermann’s Function:

1
2
3
4
5
6
(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 evaluations of these expressions:

1
(A 1 10)

Value: 1024

1
(A 2 4)

Value: 65536

1
(A 3 3)

Value: 65536

What are the mathematical counterparts of these procedures:

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

corresponds to: f(n)=2n

1
2
3
4
5
6
7
8
(define (g n) (A 1 n))

(A 0 (A 1 (- n 1))
(A 0 (A 0 (A 1 (- n 2))))
(A 0 (A 0 (A 0 (A 1 (- n 3)))))
.
.
.

corresponds to:

g(n) = \begin{cases}0 & \mbox{if }n=0 \\ 2^n & \mbox{if }n \ge 1\end{cases}

1
2
3
4
5
6
7
8
9
(define (h n) (A 2 n))

(A 2 n)
(A 1 (A 2 (- n 1)))
(A 1 (A 1 (A 2 (- n 2))))
(A 1 (A 1 (A 1 (A 2 (- n 3)))))
.
.
.

At some step i, the most inner combination in the form (A 2 (- n i)) will evaluate to 2 cause n-i=1. (A 1 x) is 2^x by the definition of g(n), and there will be n evaluations of such combination, resulting in:

2^{2^{2^{\dots}}}

This can be also expressed as a recurrence:

h(n) = \begin{cases}0 & \mbox{if }n=0 \\ 2 & \mbox{if }n=1 \\ 2^{h(n-1)} & \mbox{if }n \ge 2\end{cases}

Creative Commons License
This work, unless otherwise expressly stated, is licensed under a Creative Commons Attribution 2.0 UK: England & Wales License.

This entry was posted on Tuesday, December 29th, 2009 at 9:50 PM and is filed under Computer Science. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply

CAPTCHA Image

Powered by WP Hashcash

Please wrap all source codes with [code][/code] tags.