Turing machine
- Not to be confused with Turing-machine.
A Turing machine is an imaginary machine devised by Alan Turing which performs computations. It consists of a finite-state automaton (often called its "control mechanism") hooked up to an unbounded tape which can be moved to the left and right, from which symbols can be read, and onto which symbols can be written.
A universal Turing machine is a Turing machine with a control mechanism constructed in such a way that it can simulate any other Turing machine's control mechanism, if that mechanism is encoded on the tape before execution begins. (In a way, the universal Turing machine is just a shorthand for having an arbitrary Turing machine available for the particular problem you are addressing.)
Turing machines are computationally significant because, while many systems of computation have been shown to be able to solve only a subset of computation problems that a given Turing machine can solve, no system of computation has ever been shown to be able to solve a computation problem that a Turing machine cannot.
In addition, no well-defined algorithm has yet been devised that a universal Turing machine is demonstrably incapable of executing. This has led to the Church-Turing thesis, which states (roughly) that Turing machines are mechanical embodiments of (what we think of intuitively as) effectively computable algorithms. That is to say, a Turing machine can make any sort of calculation that it is possible to precisely define an algorithm for.
Since the invention of Turing machines in Alan Turing's paper, many other systems have been shown to be equivalent to them. (In fact, several of these systems, such as the lambda calculus, combinatory logic, and Post canonical systems, predate the Turing machine.) In this way, Turing machines define a computational class of equivalent systems; these systems are termed Turing-complete.
For all these reasons, it is often an interesting and/or valuable task to show that an esoteric programming language is (or is not) equivalent to a Turing machine.
External resources
- See Turing machine on Wikipedia
- Turing Machine Language - A Turing Machine interpreter in python
- Visual Turing Machine - animated Turing machine simulator
- On Computable Numbers, With an Application to the Entscheidungsproblem - the paper in which Turing introduces his machine
- Boolos, G. and Jeffrey, R., Computability and Logic, 2nd ed., Cambridge: Cambridge University Press, 1980.
- Online Turing Machine Simulator
- Another simulator
- Yet another simulator