在 SICP 中查找函数的 "concise mathematical definition"

Question

计算机程序的结构和解释给出了阿克曼函数的实现：

(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 的以下函数的 "concise mathematical definitions"：

(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

已经计算出 (f n) = (* 2 n) 和 (g n) = (expt 2 n) 我们可以使用该信息以及 A 的定义来计算 (A 2 n) 将是：

输入 x=2:

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

输入事实 (A 1 n) = (expt 2 n)

(define (A2 y) 
  (cond ((= y 0) 0)
        ((= y 1) 2)
        (else (expt 2 (A2 (- y 1))))))

从这里你可以更清楚地看到递归模式，A2 给出了两个的嵌套幂，如 2^(2^(2^2))。我认为你的答案 2^(2^n-1) 可能是错误的。

Answer 2

您可以使用方案本身来帮助找到这个问题的答案：

(define (*^ x y) `(* ,x ,y))

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

;> (A 0 100)
;'(* 2 100)
;> (A 0 234)
;'(* 2 234)

建议 (A 0 n) = (* 2 n)。

(define (*^ x y) `(* ,x ,y))

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

;> (A 1 10)
;'(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 2)))))))))
;> (A 1 5)
;'(* 2 (* 2 (* 2 (* 2 2))))

重新排序规则以避免错误。我们可以看到它执行 *2 n 次，所以 2^n.

(define (*^ x y) `(* ,x ,y))

(define (A x y)
  (cond ((= x 0) (*^ 2 y))
        ((= x 1) `(expt 2 ,y))
        ((= y 0) 0)
        ((= y 1) 2)
        (else (A (- x 1) (A x (- y 1))))))

;> (A 2 5)
;'(expt 2 (expt 2 (expt 2 (expt 2 2))))
;> (A 2 6)
;'(expt 2 (expt 2 (expt 2 (expt 2 (expt 2 2)))))

这证实了我们得到指数塔的想法。

Answer 3

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

从 (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ⁿ.

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

在 SICP 中查找函数的 "concise mathematical definition"

Find the "concise mathematical definition" of a function in SICP

math

scheme

sicp