Information Technology Reference
In-Depth Information
Example 2
The following Turing Machine also adds a parity bit, but this time the bit is
placed at the beginning of the number. As with example 1, the machine starts in
state A, moves to state A if an even number of 1's have been processed and
moves to state B if an odd number of 1's have been processed.
Possible symbols on each location of the tape: 0, 1, space
Starting state: A
Ending state: E
Processing Table
Current State Input
Symbol
Tape Head
Next State
Written to
Movement
Tape
A
0
0
Move right 1 character
A
A
1
1
Move right 1 character
B
A
space
space
Move left 1 character
C
B
0
0
Move right 1 character
B
B
1
1
Move right 1 character
A
B
space
space
Move left 1 character
D
C
0
0
Move left 1 character
C
C
1
1
Move left 1 character
C
C
space
0
Move left 1 character
E
D
0
0
Move left 1 character
D
D
1
1
Move left 1 character
D
D
space
1
Move left 1 character
E
E
0
stop
E
1
stop
E
space
stop
Processing for this Turing Machine begins just as it did for the previous machine.
However, when the number is completely read from left to right, this machine
has to move its readwrite head to the left edge where it finds a space. Then the
parity bit can be added. To accomplish this task, states C and D allow the ma
chine to work digitbydigit to the left. State C designates that a 0 should be
added when the left edge is found, while state D designates that a 1 should be
added.
Before going on, you should check your understanding of these Turing Machines
by tracing their execution using another input string of your choice.
