2
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ The language $L_2$ is decidable. You can just count the number of states in the input machine. $\endgroup$ – Yuval Filmus Aug 10 '19 at 7:27
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ but why must an infinite language contain uncountable many subsets? is it some set theory basics? sorry I don't have experience in set theory $\endgroup$ – narek Bojikian Aug 10 '19 at 23:41
  • 1
    $\begingroup$ Yes, this is a set-theoretic property. You can see it in many ways. (It might be false, though, in a strange set theory world, say without AC.) $\endgroup$ – Yuval Filmus Aug 10 '19 at 23:48
  • $\begingroup$ en.wikipedia.org/wiki/Cantor%27s_theorem Found it.. thanks :) I learned a new thing $\endgroup$ – narek Bojikian Aug 10 '19 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.