Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
Problem Detail: 

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.

Asked By : Pavel

Answered By : Rick Decker

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51332

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback