Decidability and Undecidability

A language is decidable (recursive) if some TM halts on every input and accepts exactly the strings in the language. It is undecidable if no such TM exists. Many natural questions about automata and grammars are decidable for regular languages, partly decidable for CFLs, and undecidable for Turing machines. The core is the standard decision table, the halting problem, reductions at a qualitative level, and Rice's theorem as a named hammer for nontrivial semantic properties of r.e. languages.

To prove $L$ undecidable, reduce a known undecidable problem $A$ to $L$: give a computable map $f$ such that $x \in A \Leftrightarrow f(x) \in L$. If $L$ were decidable, composing with $f$ would decide $A$.

Direction matters: reduce from the known hard problem to the new problem.

Every nontrivial semantic property of r.e. languages is undecidable. More precisely: if $P$ is a set of r.e. languages that is nonempty and not all r.e. languages, then $\{ \langle M\rangle \mid L(M) \in P \}$ is undecidable. Use it to dismiss questions like "does $L(M)$ contain $000$?" without a custom reduction.

(D = decidable.) The finer table below adds DCFL and CSL columns and the standard problems.

Ambiguity of a CFG is undecidable; for a right-linear grammar it is decidable (look for two accepting paths on one string in the matching NFA). Two rows are easy to confuse: DCFL equivalence is decidable, but DCFL containment is not; CFL emptiness is decidable, but CFL universality is not.

Assume a decider $H$ for $A_{\mathrm{TM}}$. Build $D$ that on $\langle M\rangle$ runs $H(\langle M,\langle M\rangle\rangle)$ and does the opposite. Then $D$ on $\langle D\rangle$ contradicts. Hence $H$ cannot exist. $A_{\mathrm{TM}}$ is still r.e. via a universal simulator that accepts when the simulated machine accepts.

Reduce: given $\langle M,w\rangle$, build $M'$ that runs $M$ on $w$ and accepts if that accepts; if $M$ would reject, $M'$ loops. Then $M$ accepts $w$ iff $M'$ halts on $w$.

Deciders exist for regular and many CFL problems (earlier notes). For TMs, the "algorithm" is often a proof that none exists. A recognizer for $A_{\mathrm{TM}}$:

$L$ decidable $\Leftrightarrow$ $L$ and $\overline{L}$ both r.e. Consequently, $A_{\mathrm{TM}}$ r.e. and undecidable implies $\overline{A_{\mathrm{TM}}}$ is not even r.e.

For a TM $M$, write an accepting computation as $C_1 \# C_2^R \# C_3 \# C_4^R \cdots$. The set of strings that are not such a history for $M$ on blank input is a CFL: a PDA guesses one local defect (wrong start, no accept at the end, or one pair $C_i, C_{i+1}$ that does not follow by $\delta$; the reversal of every second configuration lets the stack compare them). This CFL is $\Sigma^*$ iff $M$ has no accepting computation. So CFG universality is undecidable, and equivalence follows by comparing with a fixed grammar for $\Sigma^*$.

An instance is a list of dominoes $(t_1, b_1), \ldots, (t_k, b_k)$ of strings; a solution is a nonempty index sequence $i_1 \ldots i_m$ with $t_{i_1} \cdots t_{i_m} = b_{i_1} \cdots b_{i_m}$. PCP is undecidable (it encodes TM computations), but it is RE: try all sequences in order of length. PCP over a one-letter alphabet is decidable. PCP reduces to CFG ambiguity and to CFG intersection-emptiness, which is how those two problems are shown undecidable.

Emptiness of DFA: decidable. Emptiness of TM: undecidable. Equivalence of CFG: undecidable. Membership in CFG: decidable.

"Does $L(M)$ contain at least one even-length string?" Nontrivial semantic property $\Rightarrow$ undecidable by Rice.

"Does $M$ have more than 10 states?" is a syntactic property of the description, decidable by reading $\langle M\rangle$. Rice does not apply.

Wrong: "reduce HALT to my easy problem." Right: reduce HALT (hard) to the problem you claim is hard. For a mapping reduction $A \le_m B$:

Nothing follows from "$A$ decidable" or "$B$ undecidable". Since $\overline{A_{\mathrm{TM}}}$ is not RE, any $B$ with $\overline{A_{\mathrm{TM}}} \le_m B$ is not RE; this is how $E_{\mathrm{TM}}$ and $EQ_{\mathrm{TM}}$ are shown not RE.

Some questions about TMs are decidable because they bound the run or ignore the language:

Rice's theorem says only "undecidable"; the finer question is whether the set of machine codes is RE, co-RE, or neither.

A test for "not RE" (Rice-Shapiro theorem): if the set is RE, then (a) whenever $L$ has the property so does every RE superset of $L$, and (b) $L$ has the property only if some finite subset of $L$ has it. "$L(M) = \emptyset$" fails (a), since $\emptyset$ has it and $\{\varepsilon\}$ does not; "$L(M)$ is infinite" fails (b). Both sets are therefore not RE.

Dominoes $1 = (b, ca)$, $2 = (a, ab)$, $3 = (ca, a)$, $4 = (abc, c)$. The sequence $2, 1, 3, 2, 4$ gives top $a \cdot b \cdot ca \cdot a \cdot abc = abcaaabc$ and bottom $ab \cdot ca \cdot a \cdot ab \cdot c = abcaaabc$, a solution, and no shorter sequence works. The instance $(a, aa), (b, bb)$ has no solution: every top is shorter than its bottom, so the top string can never catch up.

Common misconceptions.