Problem Detail: I’m trying to answer this question:
Let $S$ be the strings $langle P rangle$ accepted by the Turing Machine $P$ with input alphabet ${a,b}$, where $P$ accepts an infinite number of strings beginning with $a$ and a finite number of strings beginning with $b$.
- Is $P$ RE?
- Is $P$ co-RE?
Asked By : Orbitz233
Answered By : Yuval Filmus
Regarding your first question, a reduction from the halting problem only shows that a problem is hard, not that it’s easy. If the halting problem reduces to some problem $P$, then you know that $P$ isn’t co-computably enumerable. So if you manage to reduce the halting problem to $L$, then this shows that $L$ is not co-computably enumerable. Perhaps that can inform your guess on the answer. Regarding your second question, if you show that $L$ is c.e. but not computable, then indeed it follows directly that $L$ is not co-c.e. This is because a language that is both c.e. and co-c.e. is computable. Let me give you a hint. Every Turing machine can be modified so that it accepts only strings beginning with 0: the new machine accepts $0x$ iff the old machine accepts $x$. Such a Turing machine belongs to $L$ iff it accepts infinitely many strings. Similarly, a machine which only accepts strings beginning with 1 belongs to $L$ iff it accepts finitely many strings.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/35749
