#lang racket
;;;;;;;;;;
;; 4.15 ;;
;;;;;;;;;;
;; Suppose we had such a program 'halts?', such that (halts? p a) always returns true
;; when p halts on a, or false if p does not halt on a.
;; Consider:
;; (define (try p)
;; (if (halts? p p)
;; (run-forever)
;; 'halted))
;; and
;; (halts? try try)
;; If (halts? try try) is true, then, by the definition of try, (try try) would run
;; forever, a contradiction. And, if (halts? try try) is false, then (try try) would
;; return 'halted and thus halt, another contradiction. Either way, we get a
;; contradiction, so the premise, that a function like halts? exists, is impossible.
Comments
0 B
|👍
/👎
0 B
|👍
/👎