4.15 Exercise 4.15

4.1	Exercise 4.1
4.2	Exercise 4.2
4.3	Exercise 4.3
4.4	Exercise 4.4
4.5	Exercise 4.5
4.6	Exercise 4.6
4.7	Exercise 4.7
4.8	Exercise 4.8
4.9	Exercise 4.9
4.10	Exercise 4.10
4.11	Exercise 4.11
4.12	Exercise 4.12
4.13	Exercise 4.13
4.14	Exercise 4.14
4.15	Exercise 4.15
4.16	Exercise 4.16
4.17	Exercise 4.17
4.18	Exercise 4.18
4.19	Exercise 4.19
4.20	Exercise 4.20
4.21	Exercise 4.21
4.22	Exercise 4.22
4.23	Exercise 4.23
4.24	Exercise 4.24
4.25	Exercise 4.25
4.26	Exercise 4.26
4.27	Exercise 4.27
4.28	Exercise 4.28
4.29	Exercise 4.29
4.30	Exercise 4.30
4.31	Exercise 4.31
4.32	Exercise 4.32
4.33	Exercise 4.33
4.34	Exercise 4.34
4.35	Exercise 4.35
4.36	Exercise 4.36
4.37	Exercise 4.37
4.38	Exercise 4.38
4.39	Exercise 4.39
4.40	Exercise 4.40
4.41	Exercise 4.41
4.42	Exercise 4.42
4.43	Exercise 4.43
4.44	Exercise 4.44
4.45	Exercise 4.45
4.46	Exercise 4.46
4.47	Exercise 4.47
4.48	Exercise 4.48
4.49	Exercise 4.49
4.50	Exercise 4.50
4.51	Exercise 4.51
4.52	Exercise 4.52
4.53	Exercise 4.53
4.54	Exercise 4.54
4.55	Exercise 4.55
4.56	Exercise 4.56
4.57	Exercise 4.57
4.58	Exercise 4.58
4.59	Exercise 4.59
4.60	Exercise 4.60
4.61	Exercise 4.61
4.62	Exercise 4.62
4.63	Exercise 4.63
4.64	Exercise 4.64
4.65	Exercise 4.65
4.66	Exercise 4.66
4.67	Exercise 4.67
4.68	Exercise 4.68
4.69	Exercise 4.69
4.70	Exercise 4.70
4.71	Exercise 4.71

← prev up next →

4.15 Exercise 4.15

Suppose we have a procedure halts which determines whether the one-argument procedure p terminates when given the input a. Suppose we then had the given example program:

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

(define (try p)
  (if (halts? p p)
      (run-forever)
      'halted))

Now suppose we do as they suggest and evaluate (try try). This will either call run-forever if (halts? try try) returns true – that is, if (try try) does not run forever – or will halt if it does run forever. This is a contradiction, and guarantees that implementing halts? is impossible.

← prev up next →

1	Chapter 1
2	Chapter 2
3	Chapter 3
4	Chapter 4
5	Chapter 5