In Sipser's Introduction to the Theory of Computation, there is an exercise that asks to prove $T$ decides $A_{TM}$, which is the language

$$A_{TM} = \{ \langle M,w \rangle | M \text{ is a TM and $w \in L(M)$}\}.$$

$T$ is a TM defined as follows. On input $\langle M,w \rangle$,

  1. Write the description of a TM $R$ that works as follows. On input $x$,
    • Run $T_A$ on $x$.
    • If $T_A$ accepts $x$ then accept.
    • If $T_A$ rejects $x$ then run $M$ on input $w$ and accept if $M$ does.
  2. Run $P$ on input $\langle R \rangle$, accept if $P$ rejects and reject if $P$ accepts.


  • $T_A$ is a TM that decides the language $A$.
  • $P$ is a TM that can decide the language $$ Z = \{\langle M\rangle | M\text{ is a TM and } L(M) = A\}. $$
  • $ A = \{(0 \cup 1)^a(1 \cup 2)^b(2 \cup 3)^c | a \geq b\} $.

How can you prove that $T$ decides $A_{TM}$ ?

  • $\begingroup$ This is a dump of an exercise problem, not a question. If you have a specific question regarding the wording of the problem or concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. You may also want to check out our reference questions. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Apr 14 '14 at 7:49

Hint: The exact definition of $A$ is not important; you just need $A \neq \Sigma^*$. When is $L(R) \neq A$? (look at the third line!)

| cite | improve this answer | |
  • $\begingroup$ when M does not accept w? how does that prove T decides $A_{TM}$ ? $\endgroup$ – user16742 Apr 14 '14 at 3:04
  • $\begingroup$ I'm afraid you'll have to work that out. You just have to "chase" the definitions. $\endgroup$ – Yuval Filmus Apr 14 '14 at 3:18
  • $\begingroup$ in the case when $L(R) \neq A$.. when M accepts w, does that mean R accepts A_TM ? $\endgroup$ – user16742 Apr 14 '14 at 3:50
  • $\begingroup$ If $M$ accepts $w$ then $R$ accepts all inputs (why?). I suggest you work on your own from now. Don't give up. Just follows the definitions through. The point of this exercise is for you to understand the definitions – there is no thinking required beyond that. $\endgroup$ – Yuval Filmus Apr 14 '14 at 4:04

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