Not 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.

## Discussions

## Become a Hackaday.io Member

Create an account to leave a comment. Already have an account? Log In.