1. Undecidable Problems

Decidable Languages

Let us take that:

$$M(w):=\{\begin{array}{l}1\text{if }M\text{ accepts }w\\ 0\text{if }M\text{ rejects }w\\ \uparrow \text{if }M\text{ does not halt on }w\end{array}$$

A language $L$ is said to be decidable if there is some machine $M$ that is:

• Sound: if $M(w)=1$ then $w\in L$
• Complete: if $w\in L$ then $M(w)=1$
• Terminating: all inputs halt

Universal Turing Machine

We can encode tuples $(w_0,w_1,\dots ,w_n)$ of non-empty strings over an expanded alphabet $\Sigma \cup \{\#\}$ such that:

$$⟨w_0,w_1,\dots ,w_n⟩:=\#w_0\#w_1\#\dots \#w_n\#$$

We can encode finite functions $f:A\to B$, where $A$ and $B$ are finite sets as a tuple of tuples:

$$⟨f⟩:=⟨⟨a_1,f(a_1)⟩,⟨a_2,f(a_2)⟩,\dots ,⟨a_n,f(a_n)⟩⟩$$

(this is essentially a $2\times n$ matrix form of $f$)

Now we find that our Turing Machine can also be encoded as a string:

$$code(M):=⟨q_{init},q_{accept},q_{reject},⟨\delta ⟩⟩$$

With everything we’ve created so far, we can now produce a Universal Turing Machine which is a Turing Machine ${\mathcal{M}}_u$ that takes a pair $⟨code(M),w⟩$ as input with the property:

$$\begin{array}{rl}{\mathcal{M}}_u\text{ accepts }⟨code(M),w⟩& \iff M\text{ accepts }w\\ {\mathcal{M}}_u\text{ rejects }⟨code(M),w⟩& \iff M\text{ rejects }w\\ {\mathcal{M}}_u\text{ halts on }⟨code(M),w⟩& \iff M\text{ halts on }w\\ & \\ \text{essentially, }\mathcal{M}(⟨code(M),w⟩)& =M(w)\end{array}$$