next up previous
Next: Example of a Computation Up: Contents Previous: Universal Turing Machine (UTM)

Example of a Turing machine that adds 1 to an Unary number (UN+1)

A sequence of n 1's are used to represent the natural numbers (a Unary number) e.g

tex2html_wrap_inline272 , tex2html_wrap_inline274 , tex2html_wrap_inline276

A specification of UN+1 could be something like

displaymath266

tabular59

The non-bold numbers indicate the current internal state (0 or 1), the bold numbers indicate the current token being read and the boldface letters indicate the action to be taken (move one token to the right (R), one token to the left (L) or to stop (STOP)).

To see that this Turing ``machine'' does add 1 to an Unary number imagine that it is applied to the number 4 i.e

displaymath267

If the Turing machine is initially in the internal state 0 and is far off to the left of the 1's the following sequence of events will occur



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