SICP問題1.10
; 教科書で定義されているAkermann関数 (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 (- 1 1) (A 1 (- 10 1))) (A 0 (A 1 9)) (A 0 (A (- 1 1) (A 1 (- 9 1)))) (A 0 (A 0 (A 0 (A 1 8)))) (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 8 1)))))) (A 0 (A 0 (A 0 (A 0 (A 1 7)))))) (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 7 1))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 6)))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 6 1)))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 5 1))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 4 1)))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 3 1))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 2 1)))))))))))) (A 0 (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 (A 0 2)))))))))) (A 0 (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 (A 0 8)))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32)))))) (A 0 (A 0 (A 0 (A 0 (A 0 64))))) (A 0 (A 0 (A 0 (A 0 128)))) (A 0 (A 0 (A 0 256))) (A 0 (A 0 512)) (A 0 1024) 2048 ; => 2^11
(A 2 4)の値
(A 2 4) (A (- 2 1) (A 2 (- 4 1))) (A 1 (A 2 3)) (A 1 (A (- 2 1) (A 2 (- 3 1)))) (A 1 (A 1 (A 2 2))) (A 1 (A 1 (A (- 2 1) (A 2 (- 2 1))))) (A 1 (A 1 (A 1 (A 2 1)))) (A 1 (A 1 (A 1 2))) (A 1 (A 1 (A (- 1 1) (A 1 (- 2 1))))) (A 1 (A 1 (A 0 (A 1 1)))) (A 1 (A 1 (A 0 2))) (A 1 (A 1 4)) (A 1 (A (- 1 1) (A 1 (- 4 1)))) (A 1 (A 0 (A 1 3))) (A 1 (A 0 (A (- 1 1) (A 1 (- 3 1))))) (A 1 (A 0 (A 0 (A 1 2)))) (A 1 (A 0 (A 0 (A (- 1 1) (A 1 (- 2 1)))))) (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) (A (- 1 1) (A 1 (- 16 1))) (A 0 (A 1 15)) (A 0 (A (- 1 1) (A 1 (- 15 1)))) (A 0 (A 0 (A 1 14))) (A 0 (A 0 (A (- 1 1) (A 1 (- 14 1))))) (A 0 (A 0 (A 0 (A 1 13)))) (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 13 1)))))) (A 0 (A 0 (A 0 (A 0 (A 1 12))))) (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 12 1))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 11)))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 11 1)))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 10))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 10 1))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 9)))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 9 1)))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 8))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 8 1))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 7)))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 7 1)))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 6))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 6 1))))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5)))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 5 1)))))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4))))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 4 1))))))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3)))))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 3 1)))))))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2))))))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A (- 1 1) (A 1 (- 2 1))))))))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (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 (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 (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 (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 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16)))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32))))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 64)))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 128))))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 256)))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 512))))))) (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1024)))))) (A 0 (A 0 (A 0 (A 0 (A 0 2048))))) (A 0 (A 0 (A 0 (A 0 4096)))) (A 0 (A 0 (A 0 8192))) (A 0 (A 0 16384)) (A 0 32768) 65536 ; 2^16
(A 3 3)の値
(A 3 3) (A (- 3 1) (A 3 (- 3 1))) (A 2 (A 3 2)) (A 2 (A (- 3 1) (A 3 (- 2 1)))) (A 2 (A 2 (A 3 1))) (A 2 (A 2 2)) (A 2 (A (- 2 1) (A 2 (- 2 1)))) (A 2 (A 1 (A 2 1))) (A 2 (A 1 2)) (A 2 (A (- 1 1) (A 1 (- 2 1)))) (A 2 (A 0 (A 1 1))) (A 2 (A 0 2)) (A 2 4) => 以下2問目と同じとなる。よって 65536 ; 2^16
(define (f n) (A 0 n))
の数学的定義
(f 0) ; => 0 (f 1) ; => 2 (f 2) ; => 4 (f 3) ; => 6 (f 4) ; => 8
となるので n > 0 の時 f は n*2を計算する関数
(define (g n) (A 1 n))
の数学的定義
(g 0) ; => 0 (g 1) ; => 2 (g 2) ; => 4 (g 3) ; => 8 (g 4) ; => 16 (g 5) ; => 32
となるので、 n > 0 の時 g は 2^n を計算する関数
(define (h n) (A 2 n))
の数学的定義
(h 0) ; => 0 (h 1) ; => 2 (h 2) ; => 4 (h 3) ; => 16 (h 4) ; => 65536 (h 5) ; => なんかえらいでかい数値…
n > 0 の時 h(n) = 2^h(n-1)
数学的に簡潔な書き方が分からないなぁ。
^2 | これがn個続く感じです。 ^2 | ^2 | 2 |
