Decidability

Some problems are unsolvable. This is surprising and unintuitive. I think it’s a fascinating topic. The most straightforward examples we encounter are related to automata and machines.

To recap, a language is Turing-recognizable if there’s a Turing machine that accepts all strings in the language and rejects or loops on all other strings. A language is decidable if there’s a Turing machine that recognizes it and halts on all input.

Finite Automata

Theorem: $A_{\text{DFA}}=\{⟨B,w⟩\mid B\text{ is a DFA that accepts input string }w\}$ is decidable

We can see that simulating a DFA is fairly straightforward. Most importantly, this procedure is clearly bounded.

NFAs and regular expressions are equivalent and can be converted to DFAs

Theorem: $E_{\text{DFA}}=\{⟨A⟩\mid A\text{ is a DFA and }L(A)=\varnothing \}$ is decidable

We can use a graph fill algorithm to see if any accept states are reachable from the start

Theorem: $E{Q}_{\text{DFA}}=\{⟨A,B⟩\mid A\text{ and }B\text{ are DFAs and }L(A)=L(B)\}$ is decidable

We construct the DFA accepting $L(C)=(L(A)\cap \overline{L(B)})\cup (\overline{L(A)}\cap L(B))$ and check if it is empty

Context-Free Grammars

Theorem: $A_{\text{CFG}}$ is decidable

Convert to CNF and check all derivations with $2n-1$ steps

Theorem: $E_{\text{CFG}}$ is decidable

We recursively determine whether each variable can generate a string of terminals

Theorem: $E{Q}_{\text{CFG}}$ is not decidable

CFGs are not closed under complement or intersection so our trick above doesn’t work. In fact, $E{Q}_{\text{CFG}}$ is completely undecidable.

Undecidability

There is a specific problem that lies at the root of undecidability

Theorem: $A_{\text{TM}}=\{⟨M,w⟩\mid M\text{ is a TM and }M\text{ accepts }w\}$ is undecidable

However, $A_{\text{TM}}$ is recognizable, since we can simulate TM and forward it’s output. A Turing machine $U$ that simulates $w$ on TM $M$ is called a universal Turing machine.

Taking a step back, we prove our key result using diagonalization, a technique discovered by Georg Cantor in 1873. The initial application was in showing how the size of the set of real numbers is not countable. We take any ordering of the real numbers and construct a new real number from the diagonals (adding 1 to each digit), which definitionally cannot be in the ordering and therefore implies a contradiction.

Cardinality is an important concept; observe how the countability of Turing machines and uncountability of languages implies unrecognizable languages, since each machine recognizes one language

Assume $H$ decides $A_{\text{TM}}$. Define a machine $D$ that runs $H$ on input $⟨M,⟨M⟩⟩$ and returns the opposite result. What does $D(⟨D⟩)$ output? It definitionally must output the opposite of what $D(⟨D⟩)$ outputs… This is a contradiction! $H$ cannot exist.

Note that we’re using $⟨⟩$ to denote the encoding of an object

This is an instance of diagonalization because our definition of $D$ is the diagonalization of a table tracking the result of running $H$ on $⟨M_i,⟨M_j⟩⟩$ (since Turing machines and strings are both countable, this is equivalent to a table with the results of every string ran through every machine)

Definition: A language is co-Turing-recognizable if it is the complement of a Turing-recognizable language

Theorem: A language is decidable $⟺$ it is Turing-recognizable and co-Turing-recognizable

Observe that this means $\overline{A_{\text{TM}}}$ is not Turing-recognizable

The primary means of proving a problem is undecidable is through reducibility