SICP Exercise 4.15 halts?

Exercise 4.15.  Given a one-argument procedure p and an object a, p is said to ``halt'' on a if evaluating the expression (p a) returns a value (as opposed to terminating with an error message or running forever). Show that it is impossible to write a procedure halts? that correctly determines whether p halts on a for any procedure p and object a. Use the following reasoning: If you had such a procedure halts?, 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 (try try) and show that any possible outcome (either halting or running forever) violates the intended behavior of halts?.23

R E A S O N I N G

The following is a simple zero-argument procedure that runs forever:

(define (run-forever) (run-forever))

The following is a hypothetical procedure that checks if procedure p halts on input a:

(define (halts? p a)

(if <p halts on a>

true

false

)

)

Assuming that the "halts?" procedure above exists and works, we should be able to write 

another procedure:

(define (try p)

(if (halts? p p)

(run-forever)

'halted

)

)

The "try" procedure takes a procedure as its argument and checks if that procedure halts

on itself. If true, then try runs forever. If false, then try returns.

If p halts on itself, then try runs forever.

If p runs forever, then try halts on p.

So "try" behaves oppositely to the procedure supplied. 

Now if we evaluate (try try), then the logic would work like this:

If try halts on itself, try runs forever.

If try runs forever, try halts on itself.

In both cases, the behaviour of "try" violates the intended behavior of "halts?"

Comments

Post a Comment

Popular posts from this blog

SICP Exercise 4.18 a alternative strategy for interpreting internal definitions

Exercise 4.18.   Consider an alternative strategy for scanning out definitions that translates the example in the text to (lambda < vars >   (let ((u '*unassigned*)         (v '*unassigned*))     (let ((a < e1 >)           (b < e2 >))       (set! u a)       (set! v b))     < e3 >)) Here  a  and  b  are meant to represent new variable names, created by the interpreter, that do not appear in the user's program. Consider the  solve  procedure from section  3.5.4 : (define (solve f y0 dt)   (define y (integral (delay dy) y0 dt))   (define dy (stream-map f y))   y) Will this ...
Read more

SICP Exercise 3.11 make-account internal definitions with local state

Image
Exercise 3.11.    In section  3.2.3  we saw how the environment model described the behavior of procedures with local state. Now we have seen how internal definitions work. A typical message-passing procedure contains both of these aspects. Consider the bank account procedure of section  3.1.1 : (define (make-account balance)   (define (withdraw amount)     (if (>= balance amount)         (begin (set! balance (- balance amount))                balance)         "Insufficient funds"))   (define (deposit amount)     (set! balance (+ balance amount))     balance)   (define (dispatch m)     (cond...
Read more

SICP Exercise 3.13 make-cycle

Image
Exercise 3.13.    Consider the following  make-cycle  procedure, which uses the  last-pair  procedure defined in exercise  3.12 : (define (make-cycle x)   (set-cdr! (last-pair x) x)   x) Draw a box-and-pointer diagram that shows the structure  z  created by (define z (make-cycle (list 'a 'b 'c))) What happens if we try to compute  (last-pair z) ? SOLUTION The code is here: Exercise 3.13 make-cycle The box-and-pointer diagrams are here:
Read more