Turing-complete

In the theory of computers both imagined and real, of programming languages, and of other logical systems, a Turing-complete system is one which has computational power equivalent to a universal Turing machine. The concept is named in honor of Alan Turing. In other words, the system and the universal Turing machine can emulate each other. No computers completely meet this requirement, as a Turing machine has unlimited storage capacity, impossible to emulate on a real device. With this proviso, however, all modern computers are Turing-complete, as are all general-purpose programming languages.

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. Note, however, that this says nothing about the effort to write a program for the machine and the time it may take to do such a calculation.

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.

See also:

• Church-Turing thesis
• Algorithmic information theory
• Stephen Wolfram's A New Kind of Science