Turing Machine
Work through this and the next page.
Algorithm for Monadic Addition
Assumptions:
- Two numbers are represented in monadic form;
- Separated by + symbol;
- With * on each side to mark ends of numbers;
- Initial state A;
- Read/Write Head over the +.
That is: *111+11* => *111111* => *11111**
Method:
- Change the + symbol to 1; and
- 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;
- Read/Write Head over the -.
Method:
- Remove matching pairs of 1s from both numbers;
- Until the right-hand number is eliminated;
- 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
© J.A.N. Lee, 2000