-
Background
07/07/2020 at 23:24 • 0 commentsNot going to go into too much detail here. I just want to provide enough Turing machine background so that the pieces being designed and built will make sense.
Turing Machines 101
The Turing machine was invented in 1936 by Alan Turing. By providing a mathematical description of a very simple device capable of arbitrary computations, he was able to prove the properties of computation in general.
A Turing machine mathematically models a mechanical machine that operates on a tape. More explicitly, a Turing machine consists of (mostly from Wikipedia):
- A tape divided into adjacent cells. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol and one or more other symbols. The tape is assumed to be arbitrarily extendable to the left and to the right, so that the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written before are assumed to be filled with the blank symbol.
- A head that can read and write symbols on the tape and move the tape left and right one (and only one) cell at a time.
- A state register that stores the state of the Turing machine, one of many. Among these is the special start state with which the state register is initialized.
- A finite table of instructions that, given the state the machine is currently in and the symbol it is reading on the tape (symbol currently under the head), tells the machine to do the following transition steps in sequence:
- Write a symbol from the finite alphabet replacing the one that was there. Note that the symbol written might be the same as before or different
- Move the head either one cell to the left or one cell to the right.
- Assume the same or a new state as prescribed by the go to state.