Turing Machine

The following sequence of frames shows the steps through the execution of the algorithm to add two "monadic" numbers. NOTE: During the running of the program the diagram highlights the instruction just executed and resulting machine configuration.

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.

Solution.

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

Last updated 2001/12/03