Undecidable languages

Question

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?

Answer 1

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.

Note Link for more information about halting problem.

Answer 2

Here is a more general statement:

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.