Redirected from Turing complete
Turingcompleteness 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 Turingcomplete, 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:
Search Encyclopedia

Featured Article

