Turing completeness

From Wikipedia, the free encyclopedia
For the usage of this term in the theory of relative computability by Oracle machines, see Turing reduction.

In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing machine. The concept is named after Alan Turing. A classic example is lambda calculus.

Computability theory includes the closely related concept of 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; and, per the Church–Turing thesis, that any real-world computer can be simulated by a Turing machine, it is Turing equivalent to a Turing machine.

In colloquial usage, the terms "Turing complete" or "Turing equivalent" are used to mean that any real-world general-purpose computer or computer language can approximately simulate any other real-world general-purpose computer or computer language. The reason this is only approximate is that within the bounds of finite memory, they are only linear bounded automaton complete. Also, any physical computing device has a finite lifespan. In contrast, a universal computer is defined as a device with a Turing complete instruction set, infinite memory, and an infinite lifespan.

To show that something is Turing complete, it is enough to show that it can be used to simulate some Turing complete system. For example, an imperative language is Turing complete if it has conditional branching (e.g., "if" and "goto" statements, or a "branch if zero" instruction. See OISC) and the ability to change arbitrary memory locations (e.g., the ability to maintain an arbitrary number of variables). Since this is almost always the case, most if not all imperative languages are Turing complete if we ignore any limitations of finite memory.

Formal definitions

In computability theory, several closely related terms are used to describe the computational power of a computational system (such as an abstract machine or programming language):

Turing completeness
A computational system that can compute every Turing-computable function is called Turing complete (or Turing powerful). Alternatively, such a system is one that can simulate a universal Turing machine.
Turing equivalence
A Turing-complete system is called Turing equivalent if every function it can compute is also Turing computable; i.e., it computes precisely the same class of functions as do Turing machines. Alternatively, a Turing-equivalent system is one that can simulate, and be simulated by, a universal Turing machine. (All known Turing-complete systems are Turing equivalent, which adds support to the Church–Turing thesis.)
(Computational) universality
A system is called universal with respect to a class of systems if it can compute every function computable by systems in that class (or can simulate each of those systems). Typically, the term universality is tacitly used with respect to a Turing-complete class of systems. The term "weakly universal" is sometimes used to distinguish a system (e.g. a cellular automaton) whose universality is achieved only by modifying the standard definition of Turing machine so as to include input streams with infinitely many 1s.

History

Turing completeness is significant in that every real-world design for a computing device can be simulated by a universal Turing machine. The Church–Turing thesis states that this is a law of mathematics—that a universal Turing machine can, in principle, perform any calculation that any other programmable computer can. This says nothing about the effort needed to write the program, or the time it may take for the machine to perform the calculation, or any abilities the machine may possess that have nothing to do with computation.

Charles Babbage's analytical engine (1830s) would have been the first Turing-complete machine if it had been built at the time it was designed. Babbage appreciated that the machine was capable of great feats of calculation, including primitive logical reasoning, but he did not appreciate that no other machine could do better. From the 1830s until the 1940s, mechanical calculating machines such as adders and multipliers were built and improved, but they could not perform a conditional branch and therefore were not Turing complete.

In the late 19th century, Leopold Kronecker formulated notions of computability, defining primitive recursive functions. These functions can be calculated by rote computation, but they are not enough to make a universal computer, because the instructions which compute them do not allow for an infinite loop. In the early 20th century, David Hilbert led a program to axiomatize all of mathematics with precise axioms and precise logical rules of deduction which could be performed by a machine. Soon, it became clear that a small set of deduction rules are enough to produce the consequences of any set of axioms. These rules were proved to be enough to produce every theorem by Kurt Gödel in 1930. Gödel's completeness theorem of 1930 implicitly contains a definition of a universal computer, because the logical rules acting on some axioms of arithmetic will eventually prove as a theorem the result of any computation.

The actual notion of computation was isolated soon after, starting with Gödel's incompleteness theorem. This theorem showed that axiom systems were limited when reasoning about the computation which deduces their theorems. Church and Turing independently demonstrated that Hilbert's Entscheidungsproblem (decision problem) was unsolvable,[1] thus identifying the computational core of the incompleteness theorem. This work, along with Gödel's work on general recursive functions, established that there are sets of simple instructions, which, when put together, are able to produce any computation. The work of Gödel showed that the notion of computation is essentially unique.

John von Neumann was inspired by these results to design actual working universal computing machines. The first formal programming languages of the 1930s demonstrated that such a computer would be useful. The first actual implementation of a Turing-complete machine appeared in 1941: the program-controlled Z3 of Konrad Zuse, but the first machine explicitly designed to be Turing complete and widely appreciated as being universal was the 1946 ENIAC.[citation needed] This machine was able to solve a wide range of effective problems in the 1940s, many related to atomic bomb design.

Computability theory

The first result of computability theory is that it is impossible in general to predict what a Turing-complete program will do over an arbitrarily long time. For example, it is impossible to determine for every program-input pair whether the program, operating on the input, will eventually stop or will continue forever (see halting problem). It is impossible to determine whether the program will return "true" or whether it will return "false". For any characteristic of the program's eventual output, it is impossible to determine whether this characteristic will hold. This can cause problems in practice when analyzing real-world computer programs. One way to avoid this is to cause programs to stop executing after a fixed period of time, or to limit the power of flow control instructions. Such systems are not Turing complete by design.

Another theorem shows that there are problems solvable by Turing-complete languages that cannot be solved by any language with only finite looping abilities (i.e., any language that guarantees every program will eventually finish to a halt). Given a guaranteed halting language, the computable function which is produced by Cantor's diagonal argument on all computable functions in that language is not computable in that language.

Turing oracles

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.

Digital physics

All known laws of physics have consequences that are computable by a series of approximations on a digital computer. A hypothesis called digital physics states that this is no accident, that it is because the universe itself is computable on a universal Turing machine. This would imply that no computer more powerful than a universal Turing machine can be built physically (see Church–Turing thesis – Philosophical implications).

Examples

The computational systems (algebras, calculi) that are discussed as Turing complete systems are those intended for studying theoretical computer science. They are intended to be as simple as possible, so that it would be easier to understand the limits of computation. Here are a few:

Most programming languages, conventional and unconventional, are Turing-complete. This includes:

Turing completeness is an abstract statement of ability, rather than a prescription of specific language features used to implement that ability. The features used to achieve Turing completeness can be quite different; Fortran systems would use loop constructs or possibly even goto statements to achieve repetition; Haskell and Prolog, lacking looping almost entirely, would use recursion.

Turing completeness in SQL is implemented through advanced standard features,[citation needed] illustrating one reason relatively powerful non-Turing-complete languages are rare: the more powerful the language is initially, the more complex are the tasks to which it is applied and the sooner its lack of completeness becomes perceived as a drawback, encouraging its extension until it is Turing complete.

The untyped lambda calculus is Turing complete, but many typed lambda calculi, including System F, are not. The value of typed systems is based in their ability to represent most typical computer programs while detecting more errors.

Rule 110 and Conway's Game of Life, both cellular automata, are Turing complete.

Non-Turing-complete languages

Many computational languages exist which are not Turing complete. One such example is the set of regular languages, most commonly regular expressions, which are generated by finite automata. A more powerful but still not Turing-complete extension of finite automata is the category of pushdown automata and context-free grammars, which are commonly used to generate parse trees in an initial stage of program compiling. Further examples include some of the early versions of the pixel shader languages embedded in Direct3D and OpenGL extensions [citation needed].

In total functional programming languages, all functions are total, and must terminate, such as Charity and Epigram. Charity uses a type system and control constructs based on category theory, whereas Epigram uses dependent types. The LOOP language is designed so that it computes only the functions that are primitive recursive. All of these compute proper subsets of the total computable functions, since the full set of total computable functions is not computably enumerable.

Data languages

The notion of Turing-completeness does not apply to languages such as XML, HTML, JSON, YAML and S-expressions, because they are typically used to represent structured data, not describe computation. These are sometimes referred to as markup languages, or more properly as "container languages" or "data description languages".

See also

References

  1. ↑ Hodges, Andrew (1992) [1983], Alan Turing: the enigma, London: Burnett Books, p. 111, ISBN 0-04-510060-8 
  2. ↑ "Universal Turing Machine in XSLT". unidex.com. Retrieved 2010-07-05. 

External links

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.