The Turing Machine
The Turing machine is a theoretical computing machine designed by Alan Turing. It was designed to determine whether every problem is computable.
The Turing machine has a read/write head that can read from and write to an infinitely long tape which can be used as memory. Any language can be defined for the Turing machine e.g. binary with characters of 0, 1 and space
The operation of the Turing machine is determined by a finite state diagram.
Turing machine example
The example below shows the changing state of the Turing machine as defined by the finite state machine and the inputs on the tape. This example finite state machine looks along a tape of binary numbers each separated by
a space and finds the end of the current row and stops in the right cell to add the next number.
State transition tables
A finite state machine for a Turing machine can be shown as a state transition table.
Transition functions
As well as being represented by a state transition table the finite state machine for the Turing machine could also be described using transition functions in the form of:
δ (current state, input symbol) = (New state, output symbol, movement)