In computability theory, a collection of datamanipulation rules (an instruction set, programming language, or cellular automaton) is said to be Turing complete if and only if such system can simulate any singletaped Turing machine. Classical Turingcomplete systems include contextsensitive grammars, recursive functions and lambda calculus.
Named after Alan Turing, in practice Turingcompleteness means that the rules followed in sequence on arbitrary data can produce the result of any calculation. A device with a Turingcomplete 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 finitememory 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 closelyrelated 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 Turingcomplete 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.
Contents
Formal definitions
Full article ▸
