Turing completeness

From Free net encyclopedia

In computability theory, an abstract machine or programming language is called Turing-complete, Turing-equivalent, or (computationally) universal if it has a computational power equivalent to a universal Turing machine (a simplified model of a programmable computer). 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.

Turing completeness is significant in that every plausible design for a computing device so far advanced 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 required to write a program for the machine, the time it may take for the machine to perform the calculation, or any abilities unrelated to computation (such as communication or randomness) which the machine may possess.

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. All modern computers are Turing-complete in this lax sense.

A thought experiment suggested that the "unlimited storage" requirement might be met by a machine connected to the Internet. Since the bandwidth of the connection will always be smaller than the growth rate of the Internet storage (considering that one has full access to it), the machine can never read or rewrite the entire tape; from the perspective of the machine, the tape size is effectively infinite.

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. Previously, the first machine known to be Turing-complete was ENIAC.

It is hypothesized by some that the universe is computable on a universal Turing machine, which would imply that no computer more powerful than a UTM can be physically built (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.

1 Related Work
2 Examples
3 Bibliography
4 See also
5 External links

[edit]

Related Work

One important result from computability theory is that it is impossible in general to determine whether 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 by design.

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.

[edit]

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:

Automata theory the standard for teaching
universal Turing machine the classic
Lambda calculus the original (Alonzo Church's paper predated Turing's, but Turing is credited for fuller explanation of the implications)
formal grammar (language generators)
formal language (language recognizers)
rewrite system
Post machine

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

All general-purpose languages in wide use.
- Procedural programming languages such as Ada and C
- Object-oriented languages such as Java.
Most languages using less common paradigms
- Functional languages such as LISP and Haskell.
- Logic programming languages such as Prolog.
- Declarative languages such as XSLT.
All or most spreadsheets, because all or most of them have more than enough logic, and can execute loops via cyclic dependencies.

The specific language 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 is an abstract statement of capability, rather than a prescription of specific language features used to implement that capability.

It is difficult to find examples of non-Turing complete languages, as these languages are very limited (see, however, machines that always halt). Example include the database language SQL, and some of the early versions of the pixel shader languages embedded in Direct3D and OpenGL extensions. Another example is a series of mathematical formulae 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; BASIC languages associated with common spreadsheet programs such as Excel and OpenOffice Calc are however Turing-complete. Another famous example is the category of 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.

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.

[edit]