Turing machines, decidability and undecidability

A deterministic Turing machine (TM) has a finite control and an infinite tape divided into cells. The input $w\in {\Sigma }^{\ast }$ is written on the tape, the rest of the tape holds blanks, and the head starts on the leftmost input symbol in the start state. In each step the machine reads the cell under the head, writes a symbol, moves the head one cell left or right, and changes state.

Formally $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,B,F)$. Here $Q$ is the finite set of states, $\Sigma$ the input alphabet, $\Gamma \supseteq \Sigma \cup \{B\}$ the tape alphabet, $B$ the blank (not in $\Sigma$), $q_0$ the start state and $F$ the set of accepting states. The transition function is $\delta :Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$, and it may be partial: if $\delta$ is undefined the machine halts. We assume no transition leaves an accepting state, so entering a state of $F$ halts the machine.

Notation. $\Sigma$ is the input alphabet, $\epsilon$ the empty string, $|w|$ the length of $w$, $\overline{L}$ the complement of $L$ with respect to ${\Sigma }^{\ast }$, and $⟨M⟩$ a string encoding of the machine $M$; $⟨M,w⟩$ encodes the pair of a machine and an input.

Convention used below. In transition tables a cell $(p,c,D)$ means: go to state $p$, write $c$, move in direction $D$. An empty cell means $\delta$ is undefined, so the machine halts and rejects (unless the state is accepting). The start state is marked →, the accepting state *.

Design idea for $L=\{a^n{b}^n\mid n\ge 1\}$. Repeatedly mark the leftmost unmarked $a$ as $X$, run right to the leftmost unmarked $b$ and mark it $Y$, then return to the leftmost unmarked $a$. When no $a$ is left, check that only $Y$'s remain.

Trace on $aabb$: $q_0$ marks the first $a$; $q_1$ skips the second $a$ and marks the first $b$; $q_2$ walks back to the $X$ and returns to $q_0$; $q_0$ marks the second $a$; $q_1$ skips the $Y$ and marks the second $b$; $q_2$ walks back; $q_0$ sees $Y$ and goes to $q_3$; $q_3$ skips the $Y$'s and reads a blank, so the machine enters $q_4$ and accepts. On $aab$ the machine gets stuck in $q_1$ at the blank and rejects. On $\epsilon$ it rejects at once ($q_0$ on blank is undefined), and on $abab$ it rejects in $q_3$ on reading $a$.

Several changes to the basic model do not add power: each variant can be simulated by a standard single-tape deterministic TM, so the class of languages is the same.

The Church-Turing thesis says that anything computable by an algorithm in the intuitive sense is computable by a Turing machine. It is a thesis, not a theorem, because 'algorithm' has no formal definition to prove it against. It is why 'there is an algorithm' and 'a TM halts on every input' are used interchangeably when arguing about decidability.

Every recursive language is RE, and every context-free language is recursive. A language $L$ is RE exactly when some machine can list its members, in some order and possibly with repetitions, without necessarily ever stopping.

Consequences of this theorem for a language $L$ and its complement $\overline{L}$: exactly one of four cases holds. (1) Both are recursive. (2) Neither is RE. (3) $L$ is RE but not recursive, and then $\overline{L}$ is not RE. (4) The mirror image of (3). It is never possible for $L$ to be RE but not recursive while $\overline{L}$ is also RE.

Each class properly contains the next: $\text{Regular}\subset \text{CFL}\subset \text{CSL}\subset \text{Recursive}\subset \text{RE}$, and the deterministic CFLs sit in between: $\text{Regular}\subset \text{DCFL}\subset \text{CFL}$. Examples that separate them: $\{a^n{b}^n\}$ is a DCFL but not regular; $\{w{w}^R\mid w\in \{a,b{\}}^{\ast }\}$ is a CFL but not a DCFL; $\{a^n{b}^n{c}^n\}$ is context-sensitive but not context-free; $HAL{T}_{TM}$ (defined below) is RE but not recursive.

A linear bounded automaton is a non-deterministic TM whose head never leaves the cells holding the input (the input is delimited by end-markers). Its language class is exactly the context-sensitive languages; whether deterministic LBAs are equally powerful is an open question. Membership for an LBA is decidable: on an input of length $n$ the number of configurations is finite, so whether an accepting configuration is reachable can be checked. Emptiness and equivalence for LBAs are undecidable. Context-sensitive languages are closed under complement, and every one of them is recursive.

Two standard languages: the acceptance problem $A_{TM}=\{⟨M,w⟩\mid M\text{ accepts }w\}$ and the halting problem $HAL{T}_{TM}=\{⟨M,w⟩\mid M\text{ halts on }w\}$. Both are RE: a universal TM $U$ takes $⟨M,w⟩$ and simulates $M$ on $w$, and $L(U)=A_{TM}$. Both are undecidable, so their complements are not RE.

Why $A_{TM}$ is undecidable (diagonal argument). Suppose a decider $H$ for $A_{TM}$ exists. Build $D$ that on input $⟨M⟩$ runs $H$ on $⟨M,⟨M⟩⟩$ and accepts if and only if $H$ rejects, so $D$ accepts $⟨M⟩$ exactly when $M$ does not accept $⟨M⟩$. Taking $M=D$: $D$ accepts $⟨D⟩$ if and only if $D$ does not accept $⟨D⟩$, a contradiction.

Non-RE languages exist. Every TM is a finite string, so there are countably many TMs and hence countably many RE languages, while a non-empty $\Sigma$ has uncountably many languages. A concrete example is the diagonal language $L_d=\{⟨M⟩\mid M\text{ does not accept }⟨M⟩\}$: if $L_d=L(M_d)$, then $⟨M_d⟩\in L_d$ if and only if $⟨M_d⟩\notin L(M_d)=L_d$. So $L_d$ is not RE.

Examples undecidable by Rice's theorem: is $L(M)$ empty, finite, regular, context-free, equal to ${\Sigma }^{\ast }$, does it contain a given string, does it contain at least two strings. Rice's theorem does NOT apply to properties of the machine's description or of bounded runs (the number of states, whether its transition table contains a left move, whether it halts within 100 steps on $\epsilon$): these are decidable by inspection or bounded simulation. 'Rice does not apply' does not mean decidable, though: 'does $M$ halt on the blank tape' is a property of the machine's behaviour, not of $L(M)$, and it is still undecidable (by reduction from $HAL{T}_{TM}$).

Inputs are descriptions of a DFA $A$, a context-free grammar $G$, or a Turing machine $M$. 'Decidable' means a TM always halts with the right yes/no answer.

Post correspondence problem (PCP), in brief. Given two lists of strings $x_1,\dots ,x_k$ and $y_1,\dots ,y_k$ over the same alphabet, does a sequence of indices $i_1,\dots ,i_m$ ($m\ge 1$) exist with $x_{i_1}\cdots x_{i_m}=y_{i_1}\cdots y_{i_m}$? PCP is undecidable over any alphabet of two or more symbols (over a one-symbol alphabet it is decidable). It is RE, since matches can be searched for in order of length. Reductions from PCP prove CFG universality, CFG equivalence, intersection emptiness of two CFLs, and CFG ambiguity undecidable.

Semi-decidable summary. Positive-witness problems are RE but undecidable: membership for a TM, 'does $M$ accept some string', 'does $M$ halt on $w$', 'does $M$ halt on the blank tape', and PCP. Their complements are not RE. Problems with no finite witness for either answer are in neither RE nor co-RE: TM equivalence, 'is $L(M)$ finite', 'is $L(M)={\Sigma }^{\ast }$', and totality ('does $M$ halt on every input').