Is it possible to mapping reduce either of these languages to the other?

Question

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?

Answer 1

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

Hints:

1. INFINITE to A_ALL: 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. A_ALL 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.