Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Turing completeness
open-in-new
<p>In <a href="/facts/Computability_theory/cqDfXwdf">computability theory</a>, a system of data-manipulation rules is said to be Turing-complete or computationally universal if it can be used to simulate any <a href="/facts/Turing_machine/ojCtglYu">Turing machine</a> (devised by English mathematician and computer scientist <a href="/facts/Alan_Turing/klov9b6g">Alan Turing</a>). This means that this system is able to recognize or decode other data-manipulation rule sets. Turing completeness is used as a way to express the power of such a data-manipulation rule set. Virtually all programming languages today are Turing-complete. </p><p>A related concept is that of Turing equivalence – two computers P and Q are called equivalent if P can simulate Q and Q can simulate P. The <a href="/facts/Church%25E2%2580%2593Turing_thesis/hDHn641f">Church–Turing thesis</a> conjectures that any function whose values can be computed by an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> can be computed by a Turing machine, and therefore that if any real-world computer can simulate a Turing machine, it is Turing equivalent to a Turing machine. A <a href="/facts/Universal_Turing_machine/2klpb1qQ">universal Turing machine</a> can be used to simulate any Turing machine and by extension the purely computational aspects of any possible real-world computer. </p><p>To show that something is Turing-complete, it is enough to demonstrate that it can be used to simulate some Turing-complete system. No physical system can have infinite memory, but if the limitation of finite memory is ignored, most programming languages are otherwise Turing-complete. </p>