Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
22 lines (15 sloc) 708 Bytes

该题目问的是

是否存在一个过程 halted?,使它能正确对任何过程 p 和对象 a 判定是否 p 对 a 中止。

如果有的话,那么下面的程序是能够运行的

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

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

(try try)    

这个是著名的“停机问题”,上面的try是自相矛盾的,因为:

  1. 假设try能够中止的,那么(halts? p p)true,那么会执行(run-forever),这时陷入死循环,与一开始的假设矛盾
  2. 假设try能不够中止的,那么(halts? p p)false,那么会执行'halted,这时try运行结束,与一开始的假设矛盾