Problem Detail: I am reducing a given Turing Machine to the complement of the known undecidable problem, $$ Complement(A_{TM}) = { langle M,w rangle mid M text{ is TM}, w notin L(M) }$$ To this Turing Machine, known as SPARSE TM: $$ SPARSE_{TM} = { langle M rangle mid M text{ is 1-tape TM}, |L(M)| leq 1000} $$ Here is what I have so far, but I think I need help because one of the statements I make seems fishy. Assume there is a TM S that decides the complement of the accept TM and a TM R that decides SPARSE. Then S looks like:
S = "On input `<M,w>`: Construct M': M' = "On input x: if x in L(M): #Fishy statement accept else: reject Run R on <M'> if R accepts: accept; if R rejects: reject
This (if right) would then reduce the SPARSE TM and prove that it is undeciable, right? Any help would be appreciated.
Asked By : Alex Chumbley
Answered By : Yuval Filmus
When reducing $L_1$ to $L_2$, we need to come up with a computable mapping $f$ such that $x in L_1$ iff $f(x) in L_2$. We don’t start with a Turing machine deciding $L_2$ and then construct one for deciding $L_1$, although this construction can easily be accomplished using the mapping $f$. The reason we refrain from doing so is that sometimes we already know that $L_2$ is undecidable, and yet there is merit in saying that $L_1$ reduces to $L_2$, since $L_1$ might have an even strong guarantee of “hardness”; this sort of thinking leads to classical recursion theory. Regarding your construction, there are two problems: (1) it doesn’t involve $w$, (2) when you write “if $x in L(M)$”, you actually mean “simulate $M$ on $x$”; this simulation could halt, or it could never halt. Generally speaking, when a Turing machine never halts, then we say that it rejects. See if this fits with what you were trying to accomplish.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/21400
