Turing Complete Language

(Redirected from Turing-complete)

A Turing Complete Language is a computing language if it can be used to simulate any single-taped Turing machine.

References

2016

• (Wikipedia, 2016) ⇒ https://en.wikipedia.org/wiki/Turing_completeness Retrieved:2016-5-7.
• In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing machine. The concept is named after English mathematician Alan Turing. A classic example is lambda calculus.

A closely related concept is that of Turing equivalencetwo computers P and Q are called equivalent if P can simulate Q and Q can simulate P. The Church–Turing thesis conjectures that any function whose values can be computed by an algorithm can be computed by a Turing machine, and therefore that if any real-world computer can be simulated by a Turing machine, it is Turing equivalent to a Turing machine. A Universal Turing machine can be used to simulate any Turing machine and by extension the computational aspects of any possible real-world computer.[NB 1]

To show that something is Turing complete, it is enough to show that it can be used to simulate some Turing complete system. For example, an imperative language is Turing complete if it has conditional branching (e.g., "if" and "goto" statements, or a "branch if zero" instruction. See OISC) and the ability to change an arbitrary amount of memory (e.g., the ability to maintain an arbitrary number of variables). Since this is almost always the case, most (if not all) imperative languages are Turing complete if the limitations of finite memory are ignored.

1994

• (Teller, 1994) ⇒ Astro Teller. (1994). “Turing Completeness in the Language of Genetic Programming with Indexed Memory.” In: Evolutionary Computation,

1991

• (Michel, 1991) ⇒ Pascal Michel. (1991). “An NP-complete Language Accepted in Linear Time by a One-tape Turing Machine." Theoretical Computer Science 85, no. 1

1977

• (Gill, 1977) ⇒ John Gill. (1977). “Computational Complexity of Probabilistic Turing Machines." SIAM Journal on Computing 6, no. 4

Cite error: <ref> tags exist for a group named "NB", but no corresponding <references group="NB"/> tag was found