Jump to content

Turing completeness

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by The Anome (talk | contribs) at 04:15, 14 August 2002 (* Algorithmic information theory). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

A term applied to computers both imagined and real, programming languages, and other logical systems. A Turing-complete system is one in which the behaviour of a universal Turing machine can be completely emulated. 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 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).

Other systems that are Turing-complete:

See also:

Retrieved from "https://en.wikipedia.org/w/index.php?title=Turing_completeness&oldid=154353"