**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
- The Turing Machine Assessment Activity and Quiz (this is a scored activity)

Last updated 2001/12/03

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