Turing-complete

Sponsorship the way you would do it

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 (named in honor of Alan Turing). In other words, the system and the universal Turing machine can emulate each other.

While such machines may be physically impossible as they require unlimited storage and zero crashing probability, the attribute Turing-complete is sometimes also used in a lax sense for physical machines that would be universal if they had infinite storage and were absolutely reliable. The first such machine 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. 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. 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.

It is hypothesized by some that the universe is Turing-complete.

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.