2
$\begingroup$

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.

2 Answers 2

6

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.

  • 0
    ok will look at those. thanks.2011-03-15
4

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.

  • 1
    An easier way of doing the same thing is: 1. run M, if halts accept 01, reject the rest. 2. accept 01, run M, if halts accept.2011-03-14