Unrecognisable Language

Some languages are not recognisable by any Turing machine. Such languages are known as unrecognisable languages, and challenge the limits of computational power, since any real world computer is equivalent to a TM (by the Church-Turing thesis), so if a TM cannot recognise a language, we have no means of ‘computing’ it, no matter how powerful our computers get.

The proof that there exists an unrecognisable language hinges around the fact that languages can be infinite, while any model of computation is finite. More specifically, it depends on the fact that the set of languages are uncountable, while Turing machines are countable.

Proof (By Uncountability) §

Firstly, note that there is a one-to-one correspondance between a Turing machine and the language it recognises. That is, a Turing Machine can accept only one language, not multiple (a language can be accepted by multiple Turing machines). Mathematically, the relation between a TM and a language is a#todo (What is it? injective? surjective?)

If we can show that there are more languages than Turing machines, then by the pigeonhole principle, there must be some languages that are not recognisable by any Turing machine (because, like we said, a Turing Machine cannot accept multiple languages). Mathematically, we need to show that the cardinality(size) of the set of all languages is greater than the cardinality of the set of all TMs.

The Set of Turing Machines is Countable §

Firstly, we know that Turing machines have a finite set of states, and so their transition function must be finite. This means that their TM Encoding, $⟨T⟩$ is a finite string. If we take every single one of these strings, we now have a infinite set of finite strings. This means TMs are countable. Intuitively, it means we can make a list of every single Turing Machine, arranged by sorting $⟨T⟩$ (a string) in lexographical order:

1. $⟨T_1⟩$
2. $⟨T_2⟩$
3. And so on,

In a more programmer-oriented approach, the set of all Turing Machines is enumerable. Mathematically, we have constructed a bijection to the natural number, given by the function $f(n)=⟨T_n⟩,n\in \mathbb{N}$. This function gives a unique Turing machine encoding for every natural number. Thus, by definition, the set of Turing Machines are countable.

%%🖋 Edit in Excalidraw, and the dark exported image%%

The Set of Languages is Uncountable §

However, we will now show that such a list cannot be constructed for all languages. More specifically, we will show that we can construct a language that does not appear in the list, making the list incomplete. Firstly, we take the theorem that

#todo lecture 22

Proof (By Self-Referencing Diagonalisation) §

Let’s start by looking at the set of all Turing machines, which we know to be countable. Then, this means the set of all Turing machine encodings are also countable. Also, given a Turing machine $M$, it accepts some strings and does not accept (runs forever or rejects) other strings. This includes machine codes (that is, encodings of other Turing machines), including $⟨M⟩$. So we could construct an entry for a machine $M_1$:

	$⟨M_1⟩$	$⟨M_2⟩$	$⟨M_3⟩$	$⟨M_4⟩$	…
$M_1$	Does not accept	Accepts	Does not accept	Does not accept
Equivalently, if we take the associated language (which is the set of strings that $M_1$ accepts), we have:

	$⟨M_1⟩$	$⟨M_2⟩$	$⟨M_3⟩$	$⟨M_4⟩$	…
$\in L(M_1)$	No	Yes	No	No
That is, $⟨M_i⟩$ has a ‘yes’ in the table iff $M_1$ accepts $⟨M_i⟩$.

Extending this table gives us:

	$⟨M_1⟩$	$⟨M_2⟩$	$⟨M_3⟩$	$⟨M_4⟩$	…
$\in L(M_1)$	No	Yes	No	No
$\in L(M_2)$	Yes	Yes	Yes	No
$\in L(M_3)$	No	No	No	Yes
…

Now consider the language:

$$L_S=\{⟨M⟩|M\text{ does not accept }⟨M⟩\}$$

This language corresponds to taking the diagonal of the table above, and only adding machines which have a ‘No’ in the diagonal entry %%🖋 Edit in Excalidraw, and the dark exported image%%

For the example table above, it would be $L_s=\{⟨M_1⟩,⟨M_3⟩\}$

This language is unrecognisable (will be shown by contradiction):

1. Assume $L_s$ is recognisable. Then, by definition, there exists a Turing machine, $T$ that recognises it i.e. $L(M)=L_s$
2. That is, $T$ accepts some machine code $⟨M⟩$ only if its associated machine $M$ does not accept $⟨M⟩$. In our example above, $T$ accepts $⟨M_1⟩$ and $⟨M_2⟩$ only.
3. Since $M$ is a Turing machine, it must appear somewhere in our table (due to TMs being countable).
4. Does $⟨T⟩$ belong in $L_s$? Remember, $L_s$ is a set, so any string either belongs in $L_s$ or it does not.
   1. Assume $⟨T⟩$ does belong in $L_s$
      • Then (by definition of being in $L_s$), $T$ must not accept $⟨T⟩$
      • But, then, $⟨T⟩\in L_s$ and we assumed by construction that $T$ accepts $L_s$. So $T$ must accept $⟨T⟩$
      • This is a contradiction
   2. Assume $⟨T⟩$ does not belong in $L_s$
      • Then (by not being in $L_s$), $T$ must accept $⟨T⟩$
      • But $T$ is a recogniser for $L_s$, so it will only accept strings if they belong in $L_s$. Since $⟨T⟩$ does not belong in $L_s$, $T$ does not accept $⟨T⟩$
      • Contradiction
5. Since we have a contradiction in both cases, it must mean $L_s$ is not recognisable!