Turing completeness

related topics
{math, number, function}
{system, computer, user}
{theory, work, human}
{company, market, business}
{group, member, jewish}

In computability theory, a collection of data-manipulation rules (an instruction set, programming language, or cellular automaton) is said to be Turing complete if and only if such system can simulate any single-taped Turing machine. Classical Turing-complete systems include context-sensitive grammars, recursive functions and lambda calculus.

Named after Alan Turing, in practice Turing-completeness means that the rules followed in sequence on arbitrary data can produce the result of any calculation. A device with a Turing-complete instruction set, and an infinite memory and infinite lifespan, is the definition of a universal computer. To be Turing complete, it is enough to have conditional branching (an "if" and "goto" statement), and the ability to change arbitrary memory locations.

To show that something is Turing complete, it is enough to show that it can be used to simulate the most primitive computer, since even the simplest computer can be used to simulate the most complicated one. All general purpose programming languages and modern machine instruction sets are Turing complete, up to relatively trivial finite-memory issues. Turing complete machines are defined as having unlimited amounts of memory, while machine instruction sets are usually designed only to work with a certain limited amount of RAM.

In computability theory, there is a closely-related concept known as Turing equivalence. Two computers P and Q are called Turing equivalent if P can simulate Q and Q can simulate P. Thus, a Turing-complete system is one that can simulate a Turing machine, but the term is most often used to mean Turing equivalent to a Turing machine. The reason is that any real world computer can be simulated by a Turing machine, an observation codified as the Church–Turing thesis.

A computer with access to an infinite tape of data is sometimes more powerful than a Turing machine, because the tape can in principle contain the solution to the halting problem, or some other undecidable problem. An infinite tape of data is called a Turing oracle. Even a Turing oracle with random data is not computable (with probability 1), since there are only countably many computations but uncountably many oracles. So a computer with a random Turing oracle can compute things that a Turing machine cannot. A machine which is universal, except for having access to some Turing oracle is called weakly universal.


Formal definitions

Full article ▸

related documents
Basic Encoding Rules
Mercury (programming language)
Interchange File Format
MOO (programming language)
Blowfish (cipher)
Code refactoring
Java applet
Dynamic HTML
Rich Text Format
Search engine (computing)
Range encoding
Dublin Core
Java API for XML Processing
GNU Octave
Universal Product Code
Lex programming tool
C shell
Occam (programming language)
Wikipedia:Free On-line Dictionary of Computing/O - Q
ANSI escape code
Abstract factory pattern