|
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. (Under traditional hyphenation conventions, the adjective Turing-complete should be hyphenated, but the noun Turing completeness need not be.)
The term derives from the name of mathematician Alan Turing who introduced the model of the universal Turing machine.
While such machines may be physically impossible as they require unlimited storage and zero crashing probability, Turing completeness is often loosely attributed to physical machines or programming languages that would be universal if they had indefinitely enlargeable storage and were absolutely reliable. 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
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, as contained in languages such as Perl. A list of Turing-complete languages is contained under computability theory.
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 | 
Feeds |
Contact