Encyclopedia > Turing complete

  Article Content

Turing-complete

Redirected from 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:



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Optical waveguide

... component in integrated optical circuit[?] or as a transmission medium in local or long haul communication systems. Optical waveguides can be classified according to ...