Determining whether a language belongs to R or RE (Turing Machines)

Question

Let $$ L = \{ \langle M\rangle \mid \text{$M$ is a Turing machine that accepts a string $w$ if and only if it accepts $w^R$}\} $$ Does the language $L$ belong to R, RE or neither? In each case, why?

Thanks a lot!

Answer 1

First of all, $L$ is not recursive because of Rice theorem.

It is not in RE, and its complement is not in RE either, because in both cases the proof that you are in the language contains assertions like "the machine does not halt on $w$". More formally, you could reduce to both $L$ or its complement from the complement of the Halting problem, which is not in RE.

Answer 2

Let $\overline{H}$ be the complement of the halting problem; that is, $e \in \overline{H}$ if and only if $\phi_e(e)$ diverges.

Given $e$, let $f$ be computable such that $\phi_{f(e)}$ is the function which accepts on input $10$ (nothing special about $10$; this is just some arbitrary string that is not equal to its reverse) if and only if $\phi_e(e)$ converges (diverging if $\phi_e(e)$ diverges), and diverges on any other input. There is such a computable $f$ because we can give code for a machine that does this: run an infinite loop if the input is not $10$, and if the input is $10$, run the computation $\phi_e(e)$, then accept when this finishes (if it does).

Then $f(e) \in L$ if and only if $e \in \bar{H}$, so this means that $\overline{H}\leq_m L$ (in fact $\overline{H}\leq_1 L$). We know that $\overline{H}$ is not many-one reducible to $H$, so neither is $L$, but a set is r.e. if and only if it is many-one reducible to $H$. So $L$ is not r.e. (and hence not recursive either).

In fact, one can show that $L$ is $\Pi^0_2$ complete. It's not too difficult to write out a $\Pi^0_2$ statement for $L$: $\forall w (\phi_e(w)\downarrow=1\ \leftrightarrow\ \phi_e(w^R)\downarrow=1)$ works since $\phi_e(w)\downarrow=1$ is $\Sigma^0_1$. (Here $\phi_e(w)\downarrow = 1$ means that $\phi_e$ halts and accepts on input $w$.) On the other hand, let $f(e)$ be computable such that $\phi_{f(e)}(1w0)$ accepts if and only if $\phi_e(w)$ halts (not halting if it doesn't), and $\phi_{f(e)}(z)$ accepts for all $z$ that don't begin with a $1$ and end with a $0$. Then $e \in \text{TOT}$ (the set of indices of total computable functions) if and only if $f(e) \in L$, so we have a 1-reduction from $\text{TOT}$, which is $\Pi^0_2$ complete.