Show that it is impossible to write a procedure halts?
Given a one-argument procedure
and an object
is said to ''halt'' on
if evaluating the expression
returns a value (as opposed to terminating with an error message or running forever). Show that it is impossible to write a procedure
that correctly determines whether
for any procedure
. Use the following reasoning: If you had such a procedure
, you could implement the following program:
(define (run-forever) (run-forever)) (define (try p) (if (halts? p p) (run-forever) 'halted))
Now consider evaluating the expression
and show that any possible outcome (either halting or running forever) violates the intended behavior of
There are no comments yet.
You must log in to post a comment.Login