sicp-4-1-5-data-as-programs

#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.