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
© J.A.N. Lee, 2000-2001.
