Skip to main content
1 of 2
templatetypedef
  • 9.2k
  • 1
  • 31
  • 60

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

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!

templatetypedef
  • 9.2k
  • 1
  • 31
  • 60