Skip to main content
Computer Science

Return to Question

Removed unnecessary elements from this question
Source Link
edit approved May 4, 2017 at 13:18
user20691
edit approved May 4, 2017 at 13:18
user20691

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$x$, there is a string y$y$ and computation history H$H$ where y$y$ has length greater than x$x$ and H$H$ is a history that shows that M$M$ accepts y and$y$. And a TM belongs to $A_{ALL}$ iff for every w$w$, there is a computation history H$H$ that shows that M$M$ accepts w$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!

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!

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?

Tweeted twitter.com/#!/StackCompSci/status/404923160216469504
Source Link
templatetypedef
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!