18. Undecidability

Mar 3/8, 2022

Turing-acceptable and undecidable

Undecidable languages has no decider: any TM that accepts $L$ does not halt on some input string.

We will show that there exists is a language $L$ which is Turing-acceptable and undecidable:

$L$ is Turing-acceptable
$\overset{―}{L}$ is not Turing-acceptable
(the complement of a decidable language is decidable)
therefore $L$ is undecidable

           ╭————————————————————————————————————————╮
           │       Non-Turing-acceptable      -----------  ¬L
           │   ╭———————————————————————————————╮      │
           │   │      Turing-acceptable     ------------  L
           │   │  ╭—————————————————————————╮  │    │
           │   │  │      Decidable          │  │    │
           │   │  ╰—————————————————————————╯  │    │
           │   ╰———————————————————————————————╯    │
           ╰————————————————————————————————————————╯

Consider alphabet ${a}$ . Strings of ${a}^{+}$ : $a = a^{1}$ , $a a = a^{2}$ , $a a a = a^{3}$ , $a a a a = a^{4}, \dots$

Consider TMs that accept languages over alphabet ${a}$ :

They are countable $M_{1}, M_{2}, M_{3}, M_{4}, \dots$ (there is an enumerator that generates them).

Each machine accepts some language over ${a}$ : $M_{1}$ accepts $L (M_{1})$ , $M_{2}$ accepts $L (M_{2})$ , etc. Note that it is possible $L (M_{i}) = L (M_{j})$ for $i \neq j$ , since a language could be accepted by more than one Turing machine.

Example language accepted by $M_{i}$ : $L (M_{i}) = {a a, a a a a, a a a a a a} = {a^{2}, a^{4}, a^{6}}$ .

Consider the language $L = {a^{i} : a^{i} \in L (M_{i})}$ where $L$ consists of the 1s in the diagonal: $L = {a^{3}, a^{4}, \dots}$ . Also consider the language $\overset{―}{L} = {a^{i} : a^{i} \notin L (M_{i})}$ , which consists of 0s in the diagonal: $\overset{―}{L} = {a^{1}, a^{2}, \dots}$ .

       | a1 a2 a3 a4  ...
-------------------------           
L(M1)  |  0  1  0  1  ...
L(M2)  |  1  0  0  1  ...
L(M3)  |  0  1  1  1  ...
L(M4)  |  0  0  0  1  ...
...    |  ...

Proof. There exists is a language $L$ which is Turing-acceptable and undecidable.

Theorem: language $\overset{―}{L}$ is not Turing-acceptable.

Proof: Assume for contradiction that $\overset{―}{L}$ is Turing-acceptable. Let $M_{k}$ be the Turing machine that accepts $\overset{―}{L}$ : $L (M_{k}) = \overset{―}{L} = 1100 \dots$ . Which $M_{i}$ is $M_{k}$ ?

$M_{k} \neq M_{i}$ for any $i$ , because either:

$(a^{i} \in L (M_{k})$ and $a^{i} \notin L (M_{i}))$ or $(a^{i} \notin L (M_{k})$ and $a^{i} \in L (M_{i}))$

The machine $M_{k}$ cannot exist. Therefore $\overset{―}{L}$ is not Turing-acceptable.

Next will prove that language $L = {a^{i} : a^{i} \in L (M_{i})}$ is:

Turing-acceptable - there is a TM that accepts $L$ , and
undecidable - each machine that accepts $L$ does not halt on some input

Theorem: $L$ is Turing-acceptable.

Proof: give a TM that accepts L. For any input string $w$ : suppose $w = a^{i}$ . Find Turing machine $M_{i}$ (using the enumerator for TMs). Simulate $M_{i}$ on input string $a^{i}$ . If $M_{i}$ accepts, then accept $w$ .

Therefore, $L = {a^{i} : a^{i} \in L (M_{i})}$ is Turing acceptable, $\overset{―}{L} = {a^{i} : a^{i} \notin L (M_{i})}$ .

Theorem: $L$ is undecidable.

Proof: if $L$ is decidable, the complement of decidable language is decidable, then $\overset{―}{L}$ is decidable. However, $\overset{―}{L}$ is not Turing-acceptable, contradiction.