Turing Machine

Work through this and the next page.

Assumptions:

• Two numbers are represented in monadic form;
• Separated by + symbol;
• With * on each side to mark ends of numbers;
• Initial state A;

That is: *111+11* => *111111* => *11111**

Method:

1. Change the + symbol to 1; and
2. Remove the rightmost digit of the right-hand number.

Before After Move
Tape
State Character State Character
A
+
B
1
L
B
1
B
1
L
B
*
C

R
C
1
D
*
R

Explanation of states:

• A - the starting state; change the + to 1;
• B - move the tape left until the end is found;
• C - delete the last 1 in the right-hand representation;
• D - the ending state.

Algorithm for Subtraction

Assumptions:

• Two numbers are represented in monadic form;
• The smaller number is on the right;
• Separated by - symbol;
• With * on each side to mark ends of numbers;
• Initial state A;

Method:

1. Remove matching pairs of 1s from both numbers;
2. Until the right-hand number is eliminated;
3. Replace the - by an end marker (*).

That is: *111-11* => **11-1** => ***1-*** => ***1****

Before After

Move
Tape

State Character State Character
A
-
B
-
L
B
1
B
1
L
B
-
B
-
L
B
*
C
*
R
C
1
D
*
R
D
1
D
1
R
D
-
D
-
R
D
*
E
*
L
E
1
B
*
L
C
-
F
*
L

Explanation of states:

• A - the starting state; move onto the right-hand number;
• B - move the tape left until the end is found and then change the direction of the tape movement;
• C - delete the 1 in the right-hand number; unless the right-hand character is - which means that the right-hand number has been eliminated; go to the ending state;
• D - move the tape right until the left-hand end is found;
• E - remove the leftmost 1 in the left-hand number and start to move the tape left again;
• F - the ending state.

Last updated 2000/04/03