Problem Detail: I have an assignment where i need to create a Turing machine that decides an infinite language $Lsubset {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.
Asked By : Felix D.
Answered By : Subhayan
@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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/16745
