乐正

Actions speak louder than words.

Sicp-ex4-15

问题

给定一个单参数的过程p和一个对象a,称p对a“终止”,如果对于表达式(pa)的求值能返回一个值(与得到一个错误信息而终止或者永远运行下去相对应)。请证明,我们不可能写出一个过程halts?,使它能正确地对任何过程p和对象a判定是否p对a终止。请采用下面的推理过程:如果你能有这样一个过程,你就可以实现下述程序:

1
2
3
4
5
6
(define (run-forever) (run-forever))

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

现在考虑求值表达式(try try),并说明任何可能的结果(无论终止或者运行下去)都将违背所确定的halts?的行为。

解答

这里的halts?的返回值有两种情况:真或者假。

假设其返回值为真,那么程序执行(run-forever)会永远执行下去,与halts得到的结果相悖。如果其返回值为假,则程序又返回了值'halted从而终止,也违背halts?的行为。

所以,不会有这样的一个过程halts?

draft

« sicp-ex4-14 平凡与永恒 »

Comments