理系学生日記

おまえはいつまで学生気分なのか

忍者TOOLS

問題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)

1024

(A 2 4)

65536

(A 3 3)

む、これも65536か。

(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))

f(n)=2n
g(n)=2^n
h(n)は数式としてどうやって書けばいいのかいまだにわからないのですが、2^2^2^2^…^2と2がn個連なる値です。