patternMinor
Is it possible to mapping reduce either of these languages to the other?
Viewed 0 times
thesethelanguageseitherpossiblereducemappingother
Problem
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?
$$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?
Solution
I'll assume that by $L(M)$ you mean the set of strings on which $M$ halts.
Hints:
-
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.)
-
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.
Hints:
-
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.)
-
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.
Context
StackExchange Computer Science Q#18323, answer score: 2
Revisions (0)
No revisions yet.