math - 在 SICP 中找到函数的 "concise mathematical definition"

Question

Structure and Interpretation of Computer Programs 给出了阿克曼函数的实现:

(define (A x y) 
  (cond ((= y 0) 0)
      ((= x 0) (* 2 y))
      ((= y 1) 2)
      (else (A (- x 1) (A x (- y 1))))))

练习 1.10 要求给出以下调用 A 的函数的“简明数学定义”:

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

对于整数 1 - 4，f 和 g 的输出可识别为 2n 和 2^n。但是 h 是 2^(2^n-1)，我无法通过在输出中寻找模式来识别这个公式。如何完成这个练习？是否有推导数学符号的方法，或许基于阿克曼函数的符号？

Answer 1

书上已经介绍了替换法，用那个也没错。

以(A 0 n)开始

这是

(cond ((= n 0) 0)
      ((= 0 0) (* 2 n))
      ((= 0 1) 2)
      (else (A (- 0 1) (A 0 (- n 1)))))

这显然是 2n。

接下来，(A 1 n)是

(cond ((= n 0) 0)
      ((= 1 0) (* 2 n))
      ((= n 1) 2)
      (else (A (- 1 1) (A 1 (- n 1))))))

这是

(A 0 (A 1 (- n 1)))

或者，利用上一步，

(* 2 (A 1 (- n 1))

也就是说，

A 1 n = 2 * (A 1 (n-1))
      = 2 * 2 * (A 1 (n-2))
      = ...

因为我们知道 A x 1 = 2 对于所有 x，我们看到了

A 1 n = 2 * 2 * ... * 2

有 n 个因子，即 2ⁿ。

将类似的推理应用于最后一个案例作为练习。