用 Scheme 简单解释停机问题

在「The Little Schemer」书中的第九章中给出了一个简单的为什么无法定义 will-stop? 函数的解释。

首先我们定义一个不会停机的函数：

(define eternity
  (lambda (x)
    (eternity x)))

假设我们可以定义一个函数来判断输入的函数是否会停止，当输入的函数会停止时 will-stop? 返回 #t 否则返回 #f ：

(define will-stop?
  (lambda (f)
    ...))
 
(will-stop? eternity) ;; return #f

我们试着使用定义好的 will-stop? 函数来测试如下函数是否会停止：

(define last-try
  (lambda (x)
    (and (will-stop? last-try)   ;; INNER
         (eternity x))))
 
(will-stop? last-try)            ;; OUTER

我们仔细观察函数调用 (will-stop? last-try) 就会发现其中存在悖论。

如果 last-try 会停止，那么 INNER 行的调用应该返回 #t ，意味着 and 条件中的 (eternity x)会执行，导致 last-try 函数不会停止。
如果 last-try不会停止，那么 INNER 行的调用返回 #f，意味着 last-try 函数不会执行 (eternity x)，那么 last-try 就会停止。

所以无论 last-try 是否停止都会产生悖论。will-stop? 是一个我们可以准确描述，但是无法用我们的变成语言来定义的函数。

参考连接：

🧠 Punk Records