I know that $L=\{<M>|\; L(M) \;has \;finite \;strings \}$ is not decidable ( by Rice theorem or using reduction, I followed it from $L$ not being decidable ). But is $L$ recognizable ?
What I tried is, let $L$ have a machine that recognizes it, let it be called $H$. Then given an input $<M>$ I would start enumerating all strings in $L$ by using $H$. As $L$ has infinite many strings at some point the string being enumerated will be equal or larger than $<M>$ ( in lexicological order ), thus using $H$ I am able to decide $L$ which I know is not possible.
Is my method correct ? In either case is there a better method for example is there a general way for proving that a language is not recognizable like for undecidability we try to reduce an undecidable problem to the current problem ?
Is the language $L=\{<M>|\; L(M) \;has\; finite\; strings \}$ Turing recognizable?
advocateofnone
- 3k
- 1
- 26
- 44