A Turing Machine (TM) is a state machine which consists of two memories: an unbounded tape and a finite state control table. The tape holds data as symbols. The machine has a very small set of proper operations, 6 at all (read, write, move left, move right, change state, halt) on the tape. Of course, it is an abstract machine and nothing is said in terms of its material implementation.
The “parity check” is a common algorithm used to detect if data has been corrupted during the transmission of a message. It allows to understand how a TM works and keeps information in its memories and why a second memory is mandatory in addition to the tape (note that the tape, containing initial data, can be written by the head).
The problem the machine has to solve is to indicate if a given string of 1s and 0s has an odd or an even number of 1s. It is asked the TM to keep the string intact but to append a 1 to the end of the string if there is an odd number of bits, otherwise append a 0, and halt. For instance, a string …BBB0010011…01BBB… is rewritten …BBB0010011…011BB… (odd number of 1s) or …BBB0010011…010BB (even number of 1s).
The string to check is: …BBB0101BBB… where B stands for the Blank symbol.
This can be done in a left-to-right scan of the square, one at a time, with 3 states:
State 0 (S0): An even number of ‘1’s have been scanned so far (“so far”: the TM remembers!)
State 1 (S1): An odd number of ‘1’s have been scanned so far
State 2 (S2): Halt
The alphabet is (0, 1, B) where B stands for Blank symbol. This TM is therefore a 3-states, 3-symbols TM capable of the following “what I know – what I do” instructions:
If in state 0 and the input is 0, then write a 0, transition to state 0, and move right.
If in state 0 and the input is 1, then write a 1, transition to state 1, and move right.
If in state 0 and the input is B, then write a 0, transition to state 1, and halt.
If in state 1 and the input is 0, then write a 0, transition to state 1, and move right.
If in state 1 and the input is 1, then write a 1, transition to state 0, and move right.
If in state 1 and the input is B, then write a 1, transition to state 2, and halt.
This is the job of the programmer of the Turing machine to establish these instructions in order to solve a given problem, exactly as when one has to write a program in the C language.
By convention, the TM is positioned on the first symbol to be read and is in State 0 (equivalent to an “even” result in the given problem since it has not meet any 1 yet).
Alan Turing expressed such instructions in a table and simply used the term « table » or « table of behaviours » instead of « algorithm » in his 1936 paper:
|
What the TM knows |
What the TM does |
|||
|
Current state |
Symbol |
Write |
Move |
Resulting state |
|
S0 S0 S1 S1 S0 S1 |
0 1 0 1 B B |
0 1 0 1 0 1 |
R (right) R R R Halt Halt |
S0 S1 S1 S0 S2 S2 |
These instructions are carried out in an order that depends on the string to check. “…BBB0101BBB…” and “…BBB1100BBB…” requires the machine to execute the instructions in two different sequences.
The existence of a State Halt does not guarantee the machine to halt. The unfolding of the algorithm, i.e. the successive transition from one state to another state can make the machine enter in a loop and never stop.
The illustration below visually recaps the whole sequence of operations.
