Recognizable or not? This is related to a homework question for a class that I am TAing for. I'm using Sipser terminology here (recognizable for computably enumerable, decidable for computable). 
Given that $w^r$ is the reverse of $w$, and that
$$T = \{ \langle M\rangle \mid \mbox{if $M$ accepts $w$ then $M$ accepts $w^r$}\}.$$
Now here are the questions:
Clearly $T$ is undecidable. Is $T$ unrecognizable? My intuition tells me yes it's unrecongnizable. Since we have to confirm that $w^r$ is accepted for all $w$, this seems to be a good sign that it is unrecognizable.
Is $\overline{T}$ recognizable? This also seems unrecognizable as we would have no way to tell if the machine is looping on a particular input.
 A: The first thing to do when you get a problem like this is to try what Rogers calls the "Tarski-Kuratowsi algorithm" to estimate the complexity. Your problem 
$$T = \{ \langle M\rangle \mid \mbox{if $M$ accepts $w$ then $M$ accepts $w^r$}\}.$$
can be written equivalently as
$$T = \{ \langle M\rangle \mid (\forall w)( (\exists t)(\mbox{$M$ accepts $w$ in $t$ steps}) \Rightarrow (\exists s)(\mbox{$M$ accepts $w^r$ in $s$ steps}))\}.$$
Because "$M$ accepts $w$ in $t$ steps" can be written with only bounded quantifiers, the quantifier pattern for the formula defining $T$ is $(\forall)((\exists)\to(\exists))$, so the prenex normal form has quantifier pattern $(\forall)(\exists)$. Hence the problem is definable by a $\Pi^0_2$ formula in the arithmetical hierarchy. This means that 


*

*The problem is computable from $0''$, the jump of the halting problem.  In fact it is many-one reducible to any $\Pi^0_2$ hard problem, such as the complement of the set $0''$. 

*Heuristically, the problem should compute $0''$.  There is a phenomenon that most problems are at exactly the level of the arithmetical hierarchy that the Tarski-Kuratowski algorithm assigns.  This heuristic suggests you should be able to many-one reduce some $\Pi^0_2$ complete problem to your problem.


One example of a $\Pi^0_2$ complete problem is 
$$\{e : \mbox{$e$ halts on every input}\}$$
In this case, there is a many-one reduction of that problem to yours, which I will let you work out, since it's a nice exercise in computability. The answer of Yuval Filmus gives a hint. 
In summary: the precise answer in terms of the arithmetical hierarchy is that your problem is $\Pi^0_2$ complete. 
A: You can reduce both the halting problem and its complement to $T$.
The easier part is reducing the halting problem. Given a machine $M$, construct a new machine $M'$ that usually just accepts, but on input $01$, say, runs $M$, and then accepts. Now $M$ halts iff $M' \in T$.
Now let's reduce the converse. Given a machine $M$, construct a new machine $M'$ that usually just accepts, but on input $0^n1$ runs $M$ and accepts iff $M$ has not halted within the first $n$ steps. Now $M$ halts iff $M' \notin T$.
