Turing complete

From Wikipedia, the free encyclopedia
(Redirected from Turing completeness)
Jump to navigation Jump to search

Turing complete is a term used in computability theory to describe abstract machines, usually called automata. Such an automaton is Turing complete, if it can be used to emulate a Turing machine. It is also called computationally universal.

Most modern programming languages are Turing-complete. There are languages that are used to classify and describe the contents of documents; for example HTML. HTML is not Turing complete, because it cannot actively change the state of the system. HTML can be combined with a technology such as JavaScript; both together can be made Turing complete. The standard regular expressions, which most programming languages use are not Turing complete either. Most regular expression engines have been adapted to include back-references. The problem with this is that a finite automaton cannot handle back references.