Turing complete

From Wikipedia, the free encyclopedia
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.