4
$\begingroup$

I have the following two languages, which are languages of TM descriptions:

$$INFINITE = \{ \langle M \rangle | \mbox{M is a TM and L(M) is infinite} \}$$

$$A_{ALL} = \{ \langle M \rangle | \mbox{M is a TM and } L(M) = \Sigma^* \}$$

Neither of these languages are decidable, recognizable, or co-recognizable.

However, I believe they're in $\Pi_2$, since a TM belongs to $INFINITE$ iff for every $x$, there is a string $y$ and computation history $H$ where $y$ has length greater than $x$ and $H$ is a history that shows that $M$ accepts $y$. And a TM belongs to $A_{ALL}$ iff for every $w$, there is a computation history $H$ that shows that $M$ accepts $w$. (I'm not sure if this reasoning is correct or not, though).

I have been wondering for a while whether either of these languages are mapping reducible to one another. I don't see a quick way to prove that the languages are not reducible to one another, but I similarly can't see a simple reduction in either direction.

Are either of these languages reducible to the other? If so, how?

$\endgroup$
2
$\begingroup$

I'll assume that by $L(M)$ you mean the set of strings on which $M$ halts.

Hints:

  1. INFINITE to AALL: Given a Turing machine $M$, construct a Turing machine $M'$ that on input $x$ halts if and only if $M$ halts on some $y \geq x$. (Arrange the inputs in some arbitrary way of your choice.)

  2. AALL to INFINITE: Given a Turing machine $M$, construct a Turing machine $M'$ that on input $x$ halts if and only if $M$ halts on all $y \leq x$.

Both directions require use of dovetailing.

$\endgroup$
  • $\begingroup$ I don't think you need dovetailing in the second reduction, though it's definitely useful in the first. $\endgroup$ – templatetypedef Nov 26 '13 at 19:57
  • $\begingroup$ You're right, it's not needed in the second reduction. $\endgroup$ – Yuval Filmus Nov 26 '13 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.