next up previous
Next: Examples of Computations that Up: Contents Previous: Example of a Turing

Example of a Computation that halts

Computations are not meant to be seen as the action of some Turing machine or UTM. For a computation to be valid it must halt. Consider the following example of a computation that halts.

(A) Find a natural number that is not the sum of three square numbers

This computation could be performed sequentially as

displaymath280

Thus our computation halts and we conclude that

tex2html_wrap282


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