Turing Complete Language

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

• Example(s):
  • C Language.
  • Python Language.
  • Scala Language.
  • …
• Counter-Example(s):
  • a Turing-Incomplete Language, such as a SQL language.
• See: Oracle Machine, First-Order Logic, Computability Theory, Instruction Set, Programming Language, Cellular Automaton, Turing Machine, Universal 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.

    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.

2004

• (Kepser, 2004) ⇒ Stephan Kepser. (2004). “A Simple Proof for the Turing-Completeness of XSLT and XQuery.” In: Extreme Markup Languages ®.
  • QUOTE: The World Wide Web Consortium recommends both XSLT and XQuery as query languages for XML documents. XSLT, originally designed to transform XML into XSL-FO, is nowadays a fully grown XML query language that is mostly suited for use by machines. XQuery on the other hand was particularly designed to be easily used by humans. Both languages are known to be Turing-complete. We provide here a very simple proof of Turing-completeness of XSLT and XQuery by coding [math]\displaystyle{ \mu }[/math]-recursive functions thereby showing that Turing-completeness is a consequence of a few basic and fundamental features of both languages.

1995

• (Nordin & Banzhaf, 1995) ⇒ Peter Nordin, and Wolfgang Banzhaf. (1995). “Evolving Turing-Complete Programs for a Register Machine with Self-modifying Code.” In: ICGA, vol. 95, pp. 318-325.

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

---