Turing machine

The Turing Machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or 'mechanical procedure'. The concept is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. The thesis that states that Turing machines indeed capture the informal notion of effective or mechanical method in logic and mathematics is known as the Church-Turing thesis.

Universal Turing machines

Every Turing machine computes a certain fixed partial computable function from the input strings over its alphabet. In that sense it behaves like a computer with a fixed program. However, as Alan Turing already described, we can encode the action table of any Turing machine in a string. Thus we might try to construct a Turing machine that expects on its tape a string describing an action table followed by a string describing the input tape, and then computes the tape that the encoded Turing machine would have computed.

Related Topics:
Partial - Computable function

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

As Turing showed, such a Turing machine is indeed possible and since it is able to simulate any other Turing machine it is called a universal Turing machine.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

With this encoding of action tables as strings, it becomes possible in principle

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

for Turing machines to answer questions about the behaviour of other Turing machines.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Most of these questions, however, are undecidable, meaning that the function in question cannot be calculated by any Turing machine.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

For instance, the problem of determining whether any particular Turing machine will halt on a particular input, or on all inputs, known as the Halting problem, was shown to be, in general, undecidable in Turing's original paper.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Rice's theorem shows that any non-trivial question about the behaviour or output of a Turing machine is undecidable.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

If we broaden the definition to include any Turing machine that simulates some Turing-complete computational model, not just Turing machines that directly simulate other Turing machines, a universal Turing machine can be fairly simple, using just a few states and a few symbols. For example, only 2 states are needed, since a 2×18 (meaning 2 states, 18 symbols) universal Turing machine is known.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

For some time, the smallest known universal Turing machines, which simulated a computational model called a tag system, had the following numbers of states and symbols : 2×18, 3×10, 4×6, 5×5, 7×4, 10×3, 22×2. Wolfram reports in his book, A New Kind of Science, a smaller universal Turing machine with 2 states and just 5 symbols, which emulates a cellular automaton also shown to be universal, making this the simplest known universal Turing machine.

Related Topics:
Tag system - Wolfram

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

A universal Turing machine is Turing-complete.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

It can calculate any recursive function, decide any recursive language, and accept any recursively enumerable language.

Related Topics:
Recursive function - Recursive language - Recursively enumerable language

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

According to the Church-Turing thesis, the problems solvable by a universal Turing machine are exactly those problems solvable by an algorithm or an effective method of computation, for any reasonable definition of those terms.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

An abstract version of the universal Turing machine is the universal function, a computable function which can be used to calculate any other computable function. The utm theorem proves the existence of such a function.

Related Topics:
Universal function - Utm theorem

~ ~ ~ ~ ~ ~ ~ ~ ~ ~