**Turing Machine**

The algorithm that was used is:

**(PSEUDO CODE VERSION):**

- Assume that the two numbers to be added are placed on the tape surrounded
by * on each end and + between them;

- To create the result (which will have as many 1's as the sum of the 1's in each number) replace the + with a 1, and remove a 1 from the end of the rightmost number.

**(TURING MACHINE VERSION):**

- The two numbers to be added are placed on the tape surrounded by * on each
end and + between them;

- The start-up sets the initial state to A and the tape positioned with the
+ symbol over the read head;

- In state A, provided that the symbol under the head is +, change that
symbol to 1, change the state to B and move the tape left;

- In state B, provided that the symbol under the head is 1, leave that
symbol alone, leave the state as B and move the tape left;

- In state B, provided that the symbol under the head is *, leave that
symbol alone, change the state to C, and move the tape right;

- In state C, provided that the symbol under the head is 1, change that
symbol to *, leave the state alone and move the tape left;

**Suggested problem:** Given two characters on a
tape from the set {a, b, c} with the read/write head set on the leftmost
character, write a Turing Machine program to exchange the position of the two
characters.

When you have completed these activities, you must move on to the Turing Machine emulator:

- Samples of Turing Machine solutions
- A "free use" Turing Machine where you can test the examples given here and try out your own solutions

Last updated 2004/01/05

© J.A.N.
Lee, 2000-2004.