Recognizable or not?

Question

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.

Answer 1

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.

Answer 2

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