Turing Machine
A Turing machine (TM) is a tuple \(M=(Q, \Sigma, \delta)\) where
- \(Q\) is a finite set of states, containing a start state \(q_0\), an accepting state \(q_{y}\), and a rejecting state \(q_{n}\). The states \(q_{y}\) and \(q_{n}\) are distinct.
- \(\Sigma\) is the alphabet which is a collection of symbols, containing a special blank symbol \(\bot\). The input does not contain the blank symbol \(\bot\).
- \(\delta\) is a transition function from \(Q\times \Sigma\) to \(Q\times \Sigma \times \{\leftarrow,\rightarrow, -\}\).
In its physical implementation, a Turing machine has a tape, a cursor, a state register, and a lookup table for transitions. The tape is divided into cells and initialized with blank symbols; we assume it extends infinitely at both ends. At the beginning, the tape contains the input string, the cursor locates at the first input symbol, and the machine starts with state \(q_0\). At each step, given the current state \(q\) and the symbol \(a\) at the cursor, the machine follows the transition rule \(\delta(q, a) = (q’, b, d)\) by changing to state \(q’\), overwriting the cell at the cursor with \(b\), and moving the cursor in the direction \(d\).
Given a TM and an input string, a configuration describes the running context of the machine. Formally, a configuration is a tuple \((q, u, w)\), where \(q\) is the current state, \(u\) is the string to the left the cursor, and \(w\) is the string to the right of the cursor.
We say a configuration \(c\) yields another configuration \(c’\) if the machine moves one step from \(c\) to \(c’\). A TM \(M\) accepts an input string \(x\) if and only if there exists a sequence of configurations \(c_0, c_1, \ldots, c_n\) such that \(c_0\) is the start configuration, \(c_i\) yields \(c_{i+1}\) for \(0 \leq i \leq n-1\), and \(c_n\) is a configuration with the accepting state.
The language of a Turing machine \(M\) is \(L(M)= \{w\in\Sigma^\star \mid M \hbox{ accepts } w\}\). Given an input, a TM may accept it, reject it, or run forever.
A language \(L\) is recursively enumerable (Turing-recognizable) if there is a Turing machine \(M\) recognizes it, that is, \(M\) accepts strings in \(L\), but either rejects or runs forever for strings not in \(L\). A language \(L\) is recursive (Turing-decidable) if there is a Turing machine \(M\) decides it, that is, \(M\) accepts strings in \(L\) and rejects strings not in \(L\) (it halts on every input).
The running time of a TM \(M\) on input \(x\), denoted by \(t_M(x)\), is the number of steps \(M\) takes on input \(x\) before halting (\(M\) may not halt). A TM \(M\) is time bounded by \(f\colon N \to N\) if \(M\) halts within \(f(|x|)\) steps for any input \(x\), that is \(\forall x [ t_M(x)\leq f(|x|)]\).
A multitape Turing Machine extends a TM with multiple tapes and the input is on the first tape, with others blank. The transition function \(\delta\) is defined from \(Q\times \Gamma^k\) to \(Q\times \Gamma^k \times \{\leftarrow, \rightarrow, -\}^k\), where \(k\) is the number of tapes. Every multi-tape TM can be simulated by an equivalent single tape TM with quadratic slowdown. For any \(k\)-tape Turing machine running in time \(t(n)\), there is an equivalent one-tape Turing machine running in time \(O(t(n)^2)\).
A nondeterministic Turing Machine extends a TM with several possibilities in each step of computation.
The transition function \(\delta\) is defined from \(Q\times \Gamma\) to \(2^{Q\times \Gamma \times \{\leftarrow, \rightarrow, -\}}\). Every nondeterministic Turing Machine has an equivalent deterministic Turing machine.
The Church-Turing thesis says that there exists languages that are not Turing-recognizable. This is because the set of all TMs is countable, but the set of all languages is uncountable.
The halting problem is to decide whether a TM accepts an input.
\[
HALT = \{(M, w) \mid M \hbox{ is a TM and } M \hbox{ accepts } w \}.
\]
HALT is undecidable, but Turing-recognizable.
A language \(L\) is decidable if and only if both \(L\) and its complement \(\overline{L}\) are Turing-recognizable.
The complement language of HALT is not Turing-recognizable.