[Solved]: Proving Infinite Turing Machine Language (with finite subset) is Recursively Enumerable

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

1. Is $P$ RE?

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