SICP

20ページ

Ackermann関数の数学的用途って要するになんなんだ?と自力で考えようとして頭がこんがらがる。Webで調べたら「無価値なのに知名度は高い」とのこと。フィボナッチ数みたいなものか?

;; 問題1.10 Ackermann関数

;; この関数って意味あんの？
(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

(print (A 1 10)) ; -> 1024

(print (A 2 4))  ; -> 65535

(print (A 3 3))  ; -> 65535

;; out of memory で nice aboat.
;(print (A 10 3))

;; これも out of memory で nice aboat.
;(print (A 2 10))

(define (f n) (A 0 n))
;; -> 2n
(print (f 3)) ; -> 6
(print (f 4)) ; -> 8
(print (f 5)) ; -> 10

(define (g n) (A 1 n))
; (A (- 1 1) (A 1 (- y 1)))
; (A 0 (A 1 (- y 1)))
; (* 2 (A 1 (- y 1)))
; (* 2 (* 2 (A 1 (- (- y 1) 1))))
; (* 2 (* 2 (* 2 (A 1 (- (- y 1) 1)))))
;; -> 2 の n乗
(print (g 3)) ; -> 8
(print (g 4)) ; -> 16
(print (g 5)) ; -> 32

(define (h n) (A 2 n))
;(A (- 2 1) (A 2 (- y 1)))
;(A 1 (A 1 (A 2 (- (- y 1) 1))))
;(A 1 (A 1 (A 1 (A 2 (- (- y 1) 1))))
;; -> 2 の (2 の n乗)乗
(print (h 2)) ; -> 4      2の2乗
(print (h 3)) ; -> 16     2の(2の2乗)乗
(print (h 4)) ; -> 65536  2の(2の(2の2乗)乗)乗