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?は定義できない。