1
$\begingroup$

I've read a proof explaining why $A_{\mathrm{TM}}$ is undecidable, and I don't seem to understand why we need to give the opposite of $H$ function $D$ itself as input.

Here's the copy-paste of that proof (link: https://courses.cs.washington.edu/courses/cse322/04au/Lect10.pdf):

$A_{\mathrm{TM}} = \{\langle M,w\rangle\mid M\text{ is a TM that accepts }w\}$ is undecidable! Proof (by contradiction):

  1. Assume $A_{\mathrm{TM}}$ is decidable there’s a decider $H$, $L(H)$ = $A_{\mathrm{TM}}$.
  2. $H$ on $\langle M,w\rangle = \mathrm{ACC}$ if $M$ accepts $w$ $\mathrm{REJ}$ if $M$ rejects $w$ (halts in $q_{\mathrm{REJ}}$ or loops on $w$).
  3. Construct new TM $D$: On input $\langle M\rangle$: Simulate $H$ on $\langle M,\langle M\rangle\rangle$ (here, $w = \langle M\rangle$). If $H$ accepts, then reject input $\langle M\rangle$; If $H$ rejects, then accept input $\langle M\rangle$.
  4. What happens when $D$ gets $\langle D\rangle$ as input? $D$ rejects $\langle D\rangle$ if $H$ accepts $\langle D,\langle D\rangle\rangle$ if $D$ accepts $\langle D\rangle$; $D$ accepts $\langle D\rangle$ if $H$ rejects $\langle D,\langle D\rangle\rangle$ if $D$ rejects $\langle D\rangle$. Either way: Contradiction! $D$ cannot exist, so $H$ cannot exist. Therefore, $A_{\mathrm{TM}}$ is not a decidable language.

So, I don't understand why we need to give $H$ the input of $\langle D,\langle D\rangle\rangle$, why not give it the input of $\langle D,w\rangle$? And give $D$ the same input, isn't that the same thing? Or what's the logic behind the second $\langle D\rangle$? For some reason it's very confusing for me. Thanks.

$\endgroup$
2
$\begingroup$

The problem is that your proposed $D$ either isn't a TM or doesn't lead to a contradiction. Suppose we did as you suggested, defining a machine $D$ that required as input a pair $(\langle\,M\,\rangle, w)$ where $\langle\,M\,\rangle$ was the description of a TM $M$ and $w$ was an arbitrary word. Then, using $H$ as a subroutine we'd have $$ D(\langle\,M\,\rangle,w)=\begin{cases} \text{ACC} & \text{if $M$ doesn't accept $w$}\\ \text{REJ} & \text{if $M$ accepts $w$} \end{cases} $$ Now what happens if you give $D$ the input pair $(\langle\,D\,\rangle, w)$? We'd have the behavior $$ D(\langle\,D\,\rangle,w)=\begin{cases} \text{ACC} & \text{if $D$ doesn't accept $w$}\\ \text{REJ} & \text{if $D$ accepts $w$} \end{cases} $$ and here's where the problem crops up. The conditions "$D$ doesn't accept $w$" and "$D$ accepts $w$" make no sense, since $D$ was defined on inputs that were required to be pairs: a TM description and a word. It might happen that $w$ in the condition was interpretable as a (TM, word) pair, but the result would have nothing to do with the original input $(\langle\,D\,\rangle,w)$. In any case, we wouldn't get to the contradiction we needed, which is why the original construction needed to define $D$ with a single argument, $\langle\,M\,\rangle$.

$\endgroup$
2
$\begingroup$

Why not give it the input of $\langle D,w\rangle$?

What's $w$? The machine $D$ is given some input, which it interprets as the coding of a Turing machine $M$. It's not given any $w$: only $\langle M\rangle$.

Imagine instead that you're given a function $f$ which is defined as $f(x)=x^x$. I ask you to calculate $f(10)$ and your question is a bit like asking, "Why does it have to be $10^{10}$? Why can't it be $10^y$?"

$\endgroup$
  • $\begingroup$ Well, yea, that's the thing, won't we get a contradiction regardless of what word we put in? I don't understand why the input string has to be the description of D. In your analogy, why not make f to take in x and y? Why not define D to take as input <M,w> and reject w, if H (taking <M,w> as well) accepts it, and vice versa? $\endgroup$ – Pavel Jan 1 '16 at 4:02

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.