Why does the proof of undecidability of $A_{TM}$ require the universal TM to take input $\langle M,\langle M\rangle\rangle$?

Question

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.

Answer 1

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$.

Answer 2

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$?"