I have an assignment where i need to create a Turing machine that decides an infinite language $L\subset \{0,1\}^*$ for which all $L'\subseteq L$, if $|L'|=\infty$, then $L'$ is not a regular language.

I think this is not possible due to Rice's Theorem. It's not possible to tell for a Turing Machine if a language is regular or not.

Moreover, on any given input, the machine can loop so it cannot decide an infinite language $L$.

Is this the right answer? It seems too easy to be the answer... Any input would be appreciable. Thanks in advance.

  • 1
    $\begingroup$ The condition is not clear. Is $L$ such language that any infinite subset of $L$ is non-regular. Or is $L$ such that if some $L'$ is non regular, then $L'\subset L$? $\endgroup$ Nov 5, 2013 at 17:58
  • $\begingroup$ L such language that any infinite subset of L is non-regular! $\endgroup$
    – Felix D.
    Nov 5, 2013 at 18:09
  • 3
    $\begingroup$ So a Turing machine which decides $a^{2^n}$ would answer your question? $\endgroup$ Nov 5, 2013 at 18:11
  • $\begingroup$ 0.0 you're right $\endgroup$
    – Felix D.
    Nov 5, 2013 at 18:27
  • 1
    $\begingroup$ Or for example, it could be a machine that decides $0^n1^n$? $\endgroup$
    – Felix D.
    Nov 5, 2013 at 18:32

1 Answer 1


@Karolis Juodele already gave the answer, and your answer is also correct.

Another thing to keep in mind is although infinite languages can be undecidable, some of them are regular.. ex. $\{0\}^* \subset \{0,1\}^*$ is an infinite language but is regular (you can construct a FSM, with a single state, that accepts it).

Basically any undecidable language is infinite, but any infinite language is not necessarily undecidable.

Also, for a language like $L = \{w \mid m \text{ halts on the input } w\}$, there exists a Turing Machine for which $L$ is undecidable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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