# Undecidable languages

I'm confused on the definition of undecidable languages.

Definition: For an undecidable language, there is no Turing Machine which accepts the language and makes a decision for every input string w.

Can you say a language that isn't recognizable as undecidable?

If given a language like

$$L = \{\langle M \rangle \mid M$$ is a turing machine with more than 50 states i.e. $$|Q| > 50 \}$$

I have to give an undecidable language T such that $$T \subseteq L$$.

A language that is a subset I think would be

$$L_2 = \{\langle M \rangle \mid M$$ is a turing machine with more than 60 states i.e. $$|Q| > 60 \}$$
because if $$\langle M \rangle \in L_2$$, then $$\langle M \rangle \in L$$. Hence, $$L_2 \subseteq L$$

But I'm confused on the undecidable part. How do I justify if this language is undecidable or if it even is?

• The language $L_2$ is decidable. You can just count the number of states in the input machine. – Yuval Filmus Aug 10 at 7:27

Well, probably you have already heard about the halting problem. It is a well known and the most common example of an undecidable language. Let us call it $$\mathcal{H}$$.

I claim that $$\mathcal{H} \cap L$$ is an undecidable language that is a subset of $$L$$. Informally, the language of all turing machines of at least 50 states that halt after finite number of steps.

Probably you can prove it straight forward as we prove undecidability of $$\mathcal{H}$$ using diagonalization. However, a simpler (and more amusing) way of proving it is by showing that the halting problem is decidable when the number of states is constant, hence $$\mathcal{H} \cap \overline{L}$$ is decidable. The reason is that after finite number of steps we will either go through a state we already were in and hence go in infinite loop or finish.

Now that we proved $$\mathcal{H} \cap \overline{L}$$ is decidable, assuming $$\mathcal{H} \cap L$$ is decidable as well, $$\mathcal{H}$$ will be decidable, since each turing machine is either in $$L$$ or $$\overline{L}$$, which is a contradiction and hence $$\mathcal{H} \cap L$$ is undecidable.

A language $$L$$ has an undecidable subset iff $$L$$ is infinite.
For the proof, note first that if $$L$$ is finite then all its subsets are finite and so decidable. Conversely, if $$L$$ is infinite then it has uncountably many subsets. Since there are only countably many decidable languages, some subset of $$L$$ (indeed, most subsets of $$L$$) must be undecidable.