SICP問題4.15

Turingの停止問題(Halting Theorem)です。
任意の手続きp が オブジェクトa で停止するかどうか判定する

(halts? p a)

がある。
オブジェクト a で停止する場合は真, 停止しない場合は偽を返す場合、これを使用して以下の手続きが定義できる。

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

上記のプログラムで(try try)を評価した場合
(halts? try try)が停止する場合、(try try)は停止しない。(run-foreverが実行されるため)
(halts? try try)が停止しない場合、(try try)は停止する。('haltedが実行されるため)
となり、矛盾する。
よって、上のような手続きhalts?は定義できない。