The Turing Machine was first described in a paper published in 1936 on computable numbers, by English mathematician Alan Turing, who called it an a-machine and presented it as a thought experiment.
What is a Turing Machine?
A Turing Machine is a theoretical computing machine with an infinitely long tape upon which it manipulates symbols according to the mathematical model that defines it.
This machine is made up of:
- A line of cells (“tape”) that can move back and forth
- An active element (“head”) that has a property (“state”) and that can change the property (“colour”) of the active cell underneath it
- A set of instructions for how the head should modify the active cell and move the tape.
Depending on the symbol and its position on the finite table – represents an algorithm that is necessarily finite – the machine:
- Writes a symbol (eg. a number) in the cell
- Either moves the tape one cell left or right
- Either continues or stops the computation.
With this hypothetical machine, Turing was able to prove properties of computation, and in particular, the uncomputability of Hilbert’s Entscheidungsproblem, also known as the decision problem.
Universal Turing Machine
Alan Turing was able to show that:
- if there is a table U such that the head of a Turing machine is programmed in accordance with U;
- and if any table P is translated and written out on the machine’s tape;
- then the machine will behave as if its head had been programmed in accordance with P.
A Universal Turing Machine is an Turing machine whose head has been programmed in accordance with U.
There are many distinct Universal Machines, all with equivalent computational power, due to the fact that there are many tables that will act like U.
Turing Machines to Computers
The model of the Universal Turing Machine is considered to be the origin of the stored program computer (stores program instructions in electronic memory), which was used by John von Neumann in 1946 for the von Neumann architecture.
However, Turing’s greatest contributions to the development of the digital computer was his establishment of the idea of controlling the function of a computing machine by storing a program of instructions in the machine’s memory, and also his proof that a single, universal machine can carry out every computation.