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.