0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 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$ – Karolis Juodelė Nov 5 '13 at 17:58
  • $\begingroup$ L such language that any infinite subset of L is non-regular! $\endgroup$ – Felix D. Nov 5 '13 at 18:09
  • 2
    $\begingroup$ So a Turing machine which decides $a^{2^n}$ would answer your question? $\endgroup$ – Karolis Juodelė Nov 5 '13 at 18:11
  • $\begingroup$ 0.0 you're right $\endgroup$ – Felix D. Nov 5 '13 at 18:27
  • $\begingroup$ Or for example, it could be a machine that decides $0^n1^n$? $\endgroup$ – Felix D. Nov 5 '13 at 18:32
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$

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.