Let \(M\) be a TM and \(L\) a language \((L \subseteq \Sigma^∗\)) [2].
If \(M\) exists such that for all \(x \in L\), \(M\) halts and accepts \(x\), and for all \(x \notin L\), \(M\) halts and rejects \(x\), then we say that \(M\) decides \(L\) (and \(L\) is said to be “decidable”). Decidable languages are also called recursive languages.
If \(M\) exists such that for all \(x \in L\), \(M\) halts and accepts \(x\), but if \(x \notin L\), \(M\) either halts and rejects or \(M\) loops infinitely, then we say \(M\) recognizes \(L\) (and \(L\) is said to be “recognizable”). Recognizable languages are also called recursively enumerable language.
NOTE: The term “recursive” used above is not limited to the idea of recursive functions as considered in programming (a function that calls itself). In the early days any computation was viewed as a “recursion”.
Also note that:
Recursive languages are a proper subset of recursively enumerable languages.
Regular languages (languages that can be defined by a regular expression or a DFA/NFA) and context-free languages (languages that can be defined by a context-free grammar) are also proper subsets of recursively enumerable languages. See The Chomsky Hierarchy below.
An undecidable problem is a decision problem (a problem that can be posed as a yes–no question) for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer [6]. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether arbitrary programs eventually halt when run. See also a list of some known undecidable problems.
The main problem with Turing machines is that a different one must be constructed for every new computation to be performed [3]. This is why Alan Turing proposed a much more general computing device which was later known as a universal Turing machine (UTM).
Along with the input on the tape, the UTM also takes in the description of a machine \(M\). The UTM can go on then to simulate \(M\) on the rest of the contents of the input tape. A UTM can thus simulate any other machine. This principle is considered to be the origin of the idea of a stored-program computer by John von Neumann in 1946 that now bears his name: the von Neumann architecture.
The Church-Turing thesis (named after American mathematician Alonzo Church and Alan Turing) establishes that any real-world computation can be translated into an equivalent computation involving a Turing machine [5]. There has never been a proof, but the evidence for its validity comes from the fact that every realistic model of computation, yet discovered, has been shown to be equivalent.
For different tasks some computational models are more efficient than others in terms of time and memory. Yet, there exist questions (undecidable problems) which an ordinary computer cannot answer, and according to the Church-Turing thesis, no other computational device can answer such a question.
Turing completeness is a classification for a system of rules that manipulate data [1]. For instance, programming languages and CPU instruction sets are examples of formal rule systems that access and modify data. If the rules can simulate a TM, the rules are said to be Turing-complete or computationally universal. No physical system can have infinite memory, but if the limitation of finite memory is ignored, most programming languages are otherwise Turing-complete. A Turing-complete system can be proven mathematically to be capable of performing any possible calculation or computer program.
Programming languages like Java, C++, C, Rust, Go, Python and others are Turing-complete. Data languages like HTML, XML, JSON and Markdown are always non-Turing-complete as they are designed to represent data and not computation.
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 (“if” and/or “while” statements) and the ability to read and write an arbitrary amount of data items in memory.
American linguist Noam Chomsky defined in 1956 a classification of languages in terms of four levels of complexity. This four-level hierarchy, called the Chomsky hierarchy, corresponds to four classes of machines [4].
The following table summarizes each of Chomsky's four types of grammars, the class of language it generates, and the type of machine that recognizes it.
Grammar | Language | Machine |
---|---|---|
Type 0
Unrestricted grammar |
\(L_{\texttt{RE}}\) Recursively enumerable language |
Turing machine (TM) |
Type 1
Context-sensitive grammar |
\(L_{\texttt{CS}}\) Context-sensitive language |
Linear-bounded automaton (LBA) |
Type 2
Context-free grammar |
\(L_{\texttt{CF}}\) Context-free language |
Pushdown automaton (PDA) |
Type 3
Regular grammar |
\(L_{\texttt{Reg}}\) Regular language |
Finite automaton (DFA/NFA) |
Each language of type \(i\) (where \(i \ge 1\)) is a proper subset of the family of type \(i − 1\). The following diagram exhibits the relationship clearly:
[1] Computer Hope. Turing Completeness. From Computer Hope’s Free Computer Help. Accessed May 26, 2025.
[2] George, Michael. Lecture 28: Turing machines. From CS 2800: Discrete Structures. Department of Computer Science. Cornell University.Accessed May 26, 2025.
[3] Kamvysselis, Manolis. Universal Turing Machine. Accessed May 26, 2025.
[4] Linz, Peter. An Introduction to Formal Languages and Automata, 6th Edition. Jones & Bartlett Learning, 2016. ISBN: 9781284077247
[5] Rowland, Todd. Church-Turing Thesis. From MathWorld — A Wolfram Web Resource. Accessed May 26, 2025.