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
    Thanks for the information on arithmetical hierarchy. Other than wikipedia, can you give the name of some books which would be good sources on this?2011-03-14
  • 0
    Most any graduate text on computability theory (the kind that's also called recursion theory) will have it, usually in conjunction with Post's theorem. Typical examples are Soare's book or Rogers' book, which is older but still a great textbook. Cooper's undergraduate book has a section on Post's theorem. This set of lecture notes is also nice: http://www.math.wisc.edu/~miller/old/m773-07/2011-03-14
  • 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