Exercise 4.15 · 习题

Exercise 4.15: Given a one-argument procedure
p and an object a, p is said to “halt” on a if
evaluating the expression (p a) returns a value (as opposed to
terminating with an error message or running forever). Show that it is
impossible to write a procedure halts? that correctly determines whether
p halts on a for any procedure p and object a. Use
the following reasoning: If you had such a procedure halts?, you could
implement the following program:

(define (run-forever)
(run-forever))

(define (try p)
(if (halts? p p)
(run-forever)
'halted))

Now consider evaluating the expression (try try) and show that any

possible outcome (either halting or running forever) violates the intended

behavior of halts?.

练习 4.15：给定一个单参数过程 p 和一个对象 a，如果对表达式 (p a) 求值会返回一个值（而不是以错误信息终止或永远运行下去），则称 p 在 a 上"停机 (halt)"。请证明，不可能写出一个过程 halts?，能对任意过程 p 和对象 a 正确判断 p 是否在 a 上停机。请用以下推理：如果你有这样一个过程 halts?，就可以实现如下程序：

(define (run-forever)
(run-forever))

(define (try p)
(if (halts? p p)
(run-forever)
'halted))

现在考虑对表达式 (try try) 求值，并证明任何可能的结果（停机或永远运行）都与 halts? 预期的行为相矛盾。