Turing-complete

(Redirected from Turing complete)

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

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 time it may take to do such a calculation).