The Turing Machine is one of the most beautiful and intriguing discoveries of the 20th century.
The Turing Machine is simply a DFA, with memory attached to it. It is a simple and useful abstract model
of computation that is general enough to embody any computer program. It forms the foundation of theoretical
computer science.
For a brief history lesson into the world of Computer Science, Alan Turing, father of
theoretical Computer Science and artificial intelligence, introduced the Turing Machine
in 1936. His work was utilized during WW2, as his machine was utilized to compute and decipher the encrypted messages of German ciphers.
The components of a Turing Machine are:
1. The Ticker Tape: Like a DFA, a Turing Machine has an alphabet with symbols to follow,
however, its input is infinite in length, and the Turing Machine can go left and right of its input.
2. The Tape Head: The Tape Head keeps track of the current location the Turing Machine is reading,
and it can move left or right, a stark difference compared to a DFA. However, the real strength of a Turing Machine
is that the Tape Head can alter the input that it is reading. It can overwrite the current symbol
with another symbol from the alphabet, which is how the Turing Machine implements 'memory'.
3. The Control Unit: This looks a lot like a DFA, and it behaves exactly like a DFA, with some added functionality.
It encodes information on the tape head moving left or right, the point at which the algorithm “stops” or “halts”, and overwriting information.
Each sate is labeled with one of three designations: Y (a “True” is returned, or the tape input is “accepted”),
N (“False” or “not accepted), and H (halt – this allows the altered state of the tape to be the “output”).
The alphabet for this example is {a, b, #}
In the Turing Machine above, the starting state is indicated by the “in arrow”. The “steps” for progressing through the Turing Machine are as follows:
1. Read the current symbol from the tape head.
2. Move along the appropriate arrow and change the symbol accordingly: “b:#” means that a “b” was read and will be replaced by a “#”,
and “a:a” means that an “a” was read and will be replaced by an “a” (i.e. left alone).
3. Move the tape head according to the new state. If “Y”, “N”, or “H” are found, the Turing Machine stops.
For “Y” the string is accepted (just like a DFA), for “N” the string is not accepted,
and for “H” the purpose is likely more about what was left on the tape due to overwrites.
What does the above Turing Machine accomplish? If an “a” is read, is leaves it alone and returns “Y”. If a “b” is read, it changes it to a “#” and moves right. It keeps doing this until it finds an “a” or a “#”. Upon finding an “a”, it stops with a “Y”. Upon finding a “#”, it stops with a “N”.
Example problem to try out:
