[Solved]: Is it possible to mapping reduce either of these languages to the other?

Problem Detail: 

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?

Thanks!

Asked By : templatetypedef

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18323

3.2K people like this

 Download Related Notes/Documents