# Can a Turing Machine decide only non-regular languages?

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.

• 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$? Nov 5, 2013 at 17:58
• L such language that any infinite subset of L is non-regular! Nov 5, 2013 at 18:09
• So a Turing machine which decides $a^{2^n}$ would answer your question? Nov 5, 2013 at 18:11
• 0.0 you're right Nov 5, 2013 at 18:27
• Or for example, it could be a machine that decides $0^n1^n$? Nov 5, 2013 at 18:32

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).
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.