# How to start solving this type of exercise: Determine if $L$ is in $RE\setminus coRE$ or $coRE\setminus RE$ or $R$ or not in $RE\cup coRE$?

I'm asking this, because in every exercise I check if I can relate it to one of the things I know,

like:$A_{TM}$, $\overline{A_{TM}}$, ${HALT_{TM}}$,$\overline{HALT_{TM}}$, $E_{TM}$, $\overline{E_{TM}}$, $ALL_{TM}$

But in many cases I can not find the connection and then get stuck with the question.

For example:$$L = \big\{ \langle M \rangle \mid M \text{ is TM and }M \text{ accepts only palindromes}\big\}$$ I know the solution to this question, I am not asking for a solution to this.

I want to understand the line of thought so that I will begin to solve questions like this. What are the guidelines?

What is the first thing that should come to my mind with such questions?

My initial thought was always to look for words like accepts to associate it to $A_{TM}$, $\overline{A_{TM}}$ or halts to associate it to ${HALT_{TM}}$,$\overline{HALT_{TM}}$ but that does not help me so much.

My questions are not only related to the example but to the questions in general of this kind, that I need to determine.

Thanks.

With a bit more work, you can show that your problem is $\Pi_1$-complete, that is, every problem in co-r.e. can be (effectively) reduced to it. To show this, it suffices to show a reduction from the non-halting problem to your problem. In this problem, given a machine $M$ and an input $x$, the goal is to determine whether $M$ does not halt on $x$. Given an instance $\langle M,x \rangle$ of this problem, construct a machine $M’$ which goes into an infinite loop (or rejects) unless the input is $10$ (an arbitrary non-palindrome), in which case it simulates $M$ on $x$, and then accepts (if $M$ ever halts). The new machine $M’$ accepts only palindromes if and only if $M$ doesn’t halt on $x$.
• Because it is possible to check whether a TM will receive a non-palindrome string by simulate the TM $M$ on all non-palindrome strings and disqualifying the TM that accept one of them, so this mean this TM is $M \in \overline{L}$ then all these TM $M$ that $M \in \overline{L}$ can be enumerate. Such testing can not be done to test the machines which accept only palindromes because I'll need to check TM $M$ by running it on all palindrome strings, infinite amount of them and to check if the TM accepts them all, this is impossible so I don't have an algorithm, therefore $L$ is unrecognizable? – Asaf Jul 31 '18 at 16:55