# Reduction to complement of Accept Problem

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.

• 1) These objects you define are not Turing machines, they are languages. In fact, you claim they are not equivalent to any Turing machine. 2) Which of your statements are you having trouble with?
– Raphael
Feb 6 '14 at 21:18
• Sorry if I'm not being clear. I am reducing the SPARSE-TM to the complement of the A-TM. However, I don't think I am doing it correctly. I'm trying to prove that SPARSE-TM being decidable implies that complement of A-TM is decidable, which is impossible. Feb 6 '14 at 21:20

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.