Skip to content

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:

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

Consider alphabet \(\{a\}\). Strings of \(\{a\}^+\): \(a=a^1\), \(aa=a^2\), \(aaa=a^3\), \(aaaa=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) = \{aa, aaaa, aaaaaa\} = \{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 \(\overline{L} = \{a^i : a^i \notin L(M_i)\}\), which consists of 0s in the diagonal: \(\overline{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 \(\overline{L}\) is not Turing-acceptable.

Proof: Assume for contradiction that \(\overline{L}\) is Turing-acceptable. Let \(M_k\) be the Turing machine that accepts \(\overline{L}\): \(L(M_k) = \overline{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 \(\overline{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, \(\overline{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 \(\overline{L}\) is decidable. However, \(\overline{L}\) is not Turing-acceptable, contradiction.