2. The Halting Problem

Theorem: There is some language that is undecidable

Theorem: there is some language $L$ that is undecidable Proof:

1. Note that we can enumerate all words over the chosen alphabet $ϵ,1,0,00,01,\dots$ which can be denoted as $w_0,w_1,w_2,\dots ,w_n$
2. We can also enumerate every possible Turing Machine. $M_0,M_1,M_2,\dots ,M_n$ We can now construct an infinite table with each Turing Machine for each row, and each word for each column. We inspect the diagonal entries in this table which gives us a new infinite sequence.
3. Let $L$ be the set of words $w_i$ which are not accepted by the corresponding machine $M_i$. $L=\{w_i\in {\Sigma }^{\ast }:M_i\text{ does not accept }{w}_i\}$
4. If $L$ were decidable then it would be the language of some terminating machine $M_j$ from our list. But we know that: $\begin{array}{rl}{w}_j\in \text{Language}(M_j)& \iff w_j\notin L\\ \text{Language}(M_j)\ne L& \end{array}$ Hence, it must be that $L$ is undecidable as required.

The Halting Problem

The Halting Problem

We define formally the Halting Problem, ${\text{HALT}}_{TM}$, with:

• An input of an encoding of a Machine $code(M)$ and an input word $w\in {\Sigma }^{\ast }$.
• An output of true iff $M$ terminates on input $w$.

$${\text{HALT}}_{TM}=\{⟨code(M),w⟩:M\text{ terminates on input }w\}$$Link to original

Theorem: Halting Problem is undecidable

We can prove that the Halting Problem is undecidable by contradiction:

1. Suppose that (to the contrary) there is some sound, complete and terminating algorithm $\text{halt}$ such that: $\text{halt}(⟨M,w⟩)=\{\begin{array}{ll}1& \text{if }M(w)=1\text{ or }M(w)=0\\ 0& \text{if }M(w)=\uparrow \end{array}$
2. Start by constructing a computable function $\text{clone}$ that takes a single input $w$ and outputs the encoding of the pair $⟨w,w⟩$ containing two copies of the input word.
3. We construct a new machine $M^{\ast }$ which:
   1. Takes some input $w$
   2. Uses the function $\text{clone}$ on the input to produce $⟨w,w⟩$
   3. Uses the function $\text{halt}$ on the pair we just created
      1. If $\text{halt}$ accepts, then we go into a purpose-built loop
      2. If $\text{halt}$ rejects, we accept $M^{\ast }(w)=1\iff \text{halt}(\text{clone}(w))=0$
4. We look at the case where we use $\text{code}(M^{\ast })$ as the input string in place of $w$. $$\begin{array}{rl}{M}^{\ast }(code(M^{\ast }))=1& \iff \text{halt}(⟨code(M^{\ast }),code(M^{\ast })⟩)=0\\ M^{\ast }(code(M^{\ast }))=1& \iff M^{\ast }(code(M^{\ast }))=\uparrow \end{array}$$
5. Which is a contradiction, hence our assumption that $\text{halt}$ exists must be wrong.

Other Undecidable Problems

Other problems include:

• The Accepting Problem: true if and only if a given machine accepts.
• The Rejecting Problem: true if and only if a given machine rejects.
• The Emptiness Problem: true if and only if the language of a given machine is $\varnothing$.
• The Equivalence Problem: true if and only if two given machines accept the same lang.
• The Regular Language Problem: true if and only if a given language is regular.