Turing Machine

Work through this and the next page.

Algorithm for Monadic Addition

Assumptions:

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:


Algorithm for Subtraction

Assumptions:

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:


Last updated 2000/04/03
© J.A.N. Lee, 2000