Turing completeness
|
|
In computability theory a programming language or any other logical system is called Turing-complete if it has a computational power equivalent to a universal Turing machine. In other words, the system and the universal Turing machine can emulate each other. The term derives from the name of mathematician Alan Turing who introduced the model of the universal Turing machine. (Under traditional hyphenation conventions, the adjective Turing-complete should be hyphenated, but the noun Turing completeness need not be.)
While such machines may be physically impossible as they require unlimited storage, Turing completeness is often loosely attributed to physical machines or programming languages that would be universal if they had indefinitely enlargeable storage. Charles Babbage's analytical engine would have been Turing-complete if it had ever been built, but the first actual implementation appeared in 1941: the program-controlled Z3 of Konrad Zuse. Its universality, however, was shown only much later, namely, by Raúl Rojas in 1998. The first machine known to be Turing-complete was ENIAC. All modern computers are also Turing-complete in this lax sense.
Turing completeness is significant in that every plausible design for a computing device so far advanced (even quantum computers) can be emulated by a universal Turing machine. Thus, a machine that can act as a universal Turing machine can, in principle, perform any calculation that any other computer is capable of (in other words, it is programmable). Note, however, that this says nothing about the effort to write a program for the machine or the time it may take to do the calculation.
It is hypothesized by some that the universe is Turing-complete (see philosophical implications in the Church-Turing thesis and digital physics).
See the article on computability theory for a long list of systems that are Turing-complete, as well as several systems that are less powerful, and several theoretical systems that are even more powerful than a universal Turing machine.
Examples
All of the general-purpose programming languages in wide use are Turing-complete. This includes conventional imperative languages such as C and object-oriented languages such as Java. Languages designed for less common paradigms including functional languages such as LISP and Haskell, and logic programming languages such as Prolog are also Turing-complete.
It is difficult to find examples of non-Turing complete languages, as these languages are very limited (see, however, machines that always halt). An example would be a series of mathematical formulas in a spreadsheet with no cycles. While it is possible to perform many interesting operations in such a system, this fails to be Turing complete as it is impossible to form loops. The macro language within Excel however is Turing-complete. Another famous example is regular expressions, which are generated by finite automata. A more powerful but still not Turing complete extension of finite automata are formal languages.
One important result from computability theory is that it is impossible in general to find if a program written in a Turing-complete language will continue executing forever or will stop within a finite period of time (see halting problem). One method of commonly getting around 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 strictly not Turing-complete.
Another curious theorem from computability theory is that there are problems solvable by Turing-complete languages that cannot be solved by languages with finite looping capabilities (i.e. languages that guarantee any program will halt). This result is derived by, for example, Brainerd and Landweber using the PL and PL-{GOTO} languages.
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.
Bibliography
Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley.
See also
- Church-Turing thesis
- Algorithmic information theory
- Machines that always halt
- Stephen Wolfram's A New Kind of Science
- c2.com (http://c2.com/cgi/wiki?TuringComplete)de:Turing-Vollständigkeit