I have been reading some material about undecidability of a language, and I am not quite sure of one part. For what I see:

I start with a decider H, that has an input <M,w> where M is a Turing Machine and w is a string, so I have the following:

H(<M,w>)=accept if M accepts w
         rejects if M rejects w

all fine until this point. Now it says that I construct a new Turing Machine D, and this TM has H as a subroutine. If I make a graph I imagine something like this:

-------------      D that is a TM
|   -----   |
|   | H  |  |
|   |____|  |

So it says that D calls H to determine what M would do if the input is M, it means something like:


Now it says that it should do the opposite this decider H, it means that:

H(M,<M>)=reject if M accepts <M>
         accepts if M rejects <M>        ---------(1)

and this procedure can be generalized for D like:

D(<M>)=accept if M does not accept <M> ----------(2)
       reject if M accept <M>

I have two questions here, for not opening another thread, but in part (1) why the decider H makes the opposite? What would happen if it does not? I have read in a book that the argument is that sometimes a program can receive a program as an input, such as in a compiler, why it decides to do the opposite?

The interpretation of part (2) does it mean that the Turing Machine D, with input M, this input refers to the same Turing Machine that was put as an input for the decider H?

At the ends there is a contradiction, but I cannot get it, why in step (1) it is decided to do the opposite?

  • 2
    $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Evil Dec 10 '16 at 0:02
  • $\begingroup$ @Layla it decides to do the opposite in order to simulate a diagonalization argument. I don't have much detail to add but this should get you started $\endgroup$ – Shubham Singh rawat Dec 10 '16 at 6:53

We have the language (commonly called $A_\text{TM}$): $$ A_\text{TM}=\{(\langle M\rangle, w)\mid M\text{ is a TM and $M$ accepts $w$}\} $$ and we want to show that this language is undecidable. We proceed by contradiction, assuming that there is a TM, $H$ that is a decider for $A_\text{TM}$. The action of $H$, when given a description $\langle M\rangle$ of a TM $M$ and a string $w$, is to accept if $M$, given $w$, accepts and to reject otherwise.

We use the purported decider $H$ to make another decider $D$ which takes as input a TM description $\langle M\rangle$ and sends that description to $H$, both as a machine description and as an input string (which answers your question (2): yes, we send $\langle M\rangle$ to $H$ as both inputs).

Now you've correctly interpreted the action of TM $D$:

$D$, on input $\langle M\rangle$, accepts if and only if $M$, on input $\langle M\rangle$, rejects.

In other words, $D$ always correctly determines whether a TM doesn't accept its own description as an input.

Which brings us to your question (1): why design the decider $D$ in such a peculiar way? The answer is precisely so that we can reach a contradiction. Since $D$ uses $H$ as a subroutine, it's clear that $D$ is a valid TM as long as $H$ is also. But now consider what happens if we give $D$ its own description as input? The action of $D$ on its own description is now

$D$, on input $\langle D\rangle$, accepts if and only if $D$, on input $\langle D\rangle$, rejects.

This contradictory behavior clearly is impossible, so our initial assumption, that there was a decider $H$, must be false. In other words, the language $A_\text{TM}$ must be undecidable.


If the language is decidable (your assumption), than its complement should be decidable too. So you can get it and it should work anyway. Getting the opposite is good to exploit a paradox (check Russell's one to get the idea), so even if this language could be decided by some TM, there is a cell in the table where the TM does not know how to answer, due to Russell's paradox.

  • $\begingroup$ I don't really see how Russell's paradox comes into it. Russell's paradox is quite specific to set theories and that's not what's going on, here. Perhaps you could explain the connection? $\endgroup$ – David Richerby Dec 10 '16 at 14:42
  • $\begingroup$ If $D$ does not accept $<D>$, then $D$ accepts. (Note that $D$ itself is a TM and so should be in the list of the TMs) $\endgroup$ – MoreOver Dec 10 '16 at 17:07
  • $\begingroup$ Agreed, and that's definitely a paradox. But it's not Russell's paradox. $\endgroup$ – David Richerby Dec 10 '16 at 17:09
  • $\begingroup$ $<D> \in L(D) \iff <D> \notin L(D)$. $\endgroup$ – MoreOver Dec 10 '16 at 17:27
  • $\begingroup$ Sure. That's the paradox. But Russell's paradox is specifically about a set being a member of itself, not about a set containing a string that describes a machine that accepts the set. We don't gain everything by calling every paradox "Russell's paradox." $\endgroup$ – David Richerby Dec 10 '16 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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