2009年2月7日土曜日

計算機プログラムの構造と解釈　問題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 1 10)
(A 0 (A 1 9))
(A 0 (A (0 A(1 8))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
(A 0 (A 0 (A 0 (A 0 (A 0 32)))))
(A 0 (A 0 (A 0 (A 0 64))))
(A 0 (A 0 (A 0 128)))
(A 0 (A 0 256))
(A 0 512)
1024

(A 2 4)

(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 4))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
(A 1 (A 0 (A 0 (A 0 (A 1 1)))))
(A 1 (A 0 (A 0 (A 0 2))))
(A 1 (A 0 (A 0 4)))
(A 1 (A 0 8))
(A 1 16)

65536

(A 3 3)

(A 3 3)
(A 2 (A 3 2))
(A 2 (A 2 (A 3 1)))
(A 2 (A 2 2))
(A 2 (A 1 (A 2 1)))
(A 2 (A 1 2))
(A 2 (A 0 (A 1 1)))
(A 2 (A 0 2))
(A 2 4)

65536

Aを上で定義した手続きとして、次の手続きを考える。
(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
(define (k n) (* 5 n n))

5n^2を計算する。

(A 0 n) は2*n
(A 1 n) は2^n
(A 2 n) は・・・・・なんだ・・・・あー・・・プロセスの4行目、ここだ。
(A 1 (A 1 (A 1 (A 2 1))))
y=1 だから次のプロセスは
(A 1 (A 1 (A 1 2)))となって、(A 1 n)は2^nだから、
(A 1 (A 1 2^2))
(A 1 2^2^2)
2^2^2^2

つまり、(A 2 n)は2^2^2^2^…^2 = $2 ￥uparrow￥uparrow n$
テトレーション (tetration)

アッカーマン関数
テトレーションでもなかなか表現できないくらい大きな数を生成する関数。