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
            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
    $\begingroup$ 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? $\endgroup$
    – Raphael
    Feb 6, 2014 at 21:18
  • $\begingroup$ 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. $\endgroup$ Feb 6, 2014 at 21:20

1 Answer 1


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.

  • $\begingroup$ Okay thank you for catching that I'm not using w. I think I can go ahead with this with your suggestions. Thanks $\endgroup$ Feb 7, 2014 at 1:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.