[Solved]: Reduction to complement of Accept Problem

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 \not\in 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