next up previous
Next: Deciding how computations stop Up: Contents Previous: Example of a Computation

Examples of Computations that do not halt

(B1) Find a natural number that is not the sum of four square numbers

This computation could be performed sequentially as

displaymath284

This computation appears never to stop. In fact the great French mathematician Joseph Lagrange proved that every number is the sum of four squares.

(B2) Find an odd number that is the sum of two even numbers

This computation, if performed, will never halt as even numbers (numbers that are a multiple of two) always sum to even numbers.



David T J Liley
Thu Apr 9 12:39:27 EST 1998