A Turing machine (TM) is a hypothetical machine (computing device) first conceived by the English mathematician Alan Turing in 1936 to help solve a specific question in mathematical logic. Despite its simplicity, the machine can simulate any computer algorithm, no matter how complicated it may be.
We may visualize a TM as follows [3]:
The machine consists of a finite control (equivalent to a CPU in modern day computers), which can be in any of a finite set of states. There is a tape divided into squares or cells ; each cell can hold any one of a finite number of symbols.
Initially the input, which is a finite-length string of symbols chosen from the input alphabet, is placed on the tape. All other tape cells, extending infinitely to the left and right, hold a special symbol called the blank. The blank is a tape symbol but not an input symbol.
There is a tape head that is always positioned at one of the tape cells. The TM is said to be scanning that cell. Initially the tape head is at the leftmost cell that holds the input.
A move of the TM is a function of the state of the finite control and the tape symbol scanned. In one move the TM will:
Change state. The next state optionally may be the same as the current state.
Write a tape symbol in the cell scanned. This tape symbol replaces whatever symbol was in that cell. Optionally, the symbol written may be the same as the symbol currently there.
Move the tape head left or right.
Formally, a TM is defined by the 7-tuple \(M = (Q, \Sigma, \Gamma, \delta, q_0, B, F) \), where:
\(Q\) : The finite set of states of the finite control.
\(\Sigma\) : The finite set of input symbols.
\(\Gamma\) : The complete set of tape symbols \((\Sigma \subset \Gamma)\).
\(\delta\) : \((Q - F) \times \Gamma \rightarrow Q \times \Gamma \times \{ L, R \} \) is the transition function.
The arguments of \(\delta(q, X)\) are a state \(q\) and a tape symbol \(X\). The value of \(\delta(q, X)\), if it is defined, is a triple \((p, Y, D)\), where:
\(p\) is the next state \((p \in Q)\).
\(Y\) is the symbol \((Y \in \Gamma)\), written in the cell being scanned, replacing whatever symbol was there.
\(D\) is a direction, either \(L\) or \(R\), standing for “left” or “right”, respectively, and telling us the direction in which the head moves.
Note that if \(\delta(q, X)\) is not defined, then the machine halts and the input is rejected.
\(q_0\) : The start state \((q_0 \in Q)\), in which the finite control is found initially.
\(B\) : The blank symbol, which is not an input symbol \((B \in \Gamma , B \notin \Sigma)\). The blank appears initially in all but the finite number of initial cells that hold input symbols.
\(F\) : The set of final or accepting states \((F \subseteq Q)\). A TM always halts when it is in an accepting state.
Let \(M\) be a TM and \(w\) a string.
\(M\) accepts \(w\) if it enters an accept state when run on \(w\).
\(M\) rejects \(w\) if it enters the reject state when run on \(w\).
\(M\) loops infinitely on \(w\) if when run on \(w\) it never enters the accept or reject states.
\(M\) halts on \(w\) if it accepts or rejects \(w\).
Let’s define a TM that accepts the language \(\{ a^n \; | \; n \ge 0, n \bmod 2 = 0\}\). In other words, the TM should accept strings that contain a sequence with an even number of \(a\)’s.
The formal specification of this Turing machine \(M\) is:
$$ M = (\{q_0, q_1, q_2 \}, \{ a \}, \{ B, a \}, \delta, q_0, B, \{ q_2\} ) $$where \(\delta\) is given by the following table:
State | Symbol | |
---|---|---|
\(a\) | \(B\) | |
\(q_0\) | \((q_1, a, R)\) | \((q_2, B, L)\) |
\(q_1\) | \((q_0, a, R)\) | |
\(q_2\) |
We can alternatively represent \(\delta\) using a state diagram as shown below [3]:
The diagram consists a set of nodes corresponding to the states of the TM. An arc from state \(q\) to state \(p\) is labeled by one or more items of the form \(X/Y;D\), where \(X\) and \(Y\) are tape symbols, and \(D\) is a direction, either \(L\) or \(R\). That is, whenever \(\delta(q,X) = (p, Y, D)\), we find the label \(X/Y;D\) on the arc from \(q\) to \(p\). Also, in the above diagram the blank symbol \(B\) is represented with an underscore (_).
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.
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 [4]. 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.
[1] Computer Hope. Turing Completeness. From Computer Hope’s Free Computer Help. Accessed June 2, 2022.
[2] George, Michael. Lecture 28: Turing machines. From CS 2800: Discrete Structures. Department of Computer Science. Cornell University.Accessed June 2, 2022.
[3] Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey. Introduction to Automata Theory, Languages, and Computation, 3rd. Edition. Pearson Education, 2007. ISBN: 9780321455369
[4] Kamvysselis, Manolis. Universal Turing Machine. Accessed June 2, 2022.
[5] Rowland, Todd. Church-Turing Thesis. From MathWorld — A Wolfram Web Resource. Accessed June 2, 2022.
[6] Wikipedia. Undecidable Problem. Accessed June 2, 2022.