Cheap and Secure Web Hosting Provider : See Now

[Answers] Trying to understand the proof of the halting problem presented in Sipser textbook

, , No Comments
Problem Detail: 

I'm having some problems to understand the classic proof of the halting problem.

The Proof:

$A_{tm} = ${$<M,w>$ | $M$ is a $TM$ and $M$ accepts $w$}.

We assume that $A_{tm}$ is decidable and obtain a contradiction.

I have no problem to imagine that. It's a machine that accepts some string $w$. But it must not accept others strings $not-w$. And if it's decidable, it always halts.

Suppose that $H$ is a decider for $A_{tm}$. On input $<M, w>$, where $M$ is a $TM$ and $w$ is a string, $H$ halts and accept if $M$ accepts $w$. Furthermore, $H$ halts and rejects if $M$ fails to accept $w$. In other words, we assume that $H$ is a $TM$, where

\begin{equation} H(<M, w>)=\begin{cases} accept &\text{if $ M$ accepts $w$}.\\ reject & \text{if $ M$ does not accept $w$}. \end{cases} \end{equation}

Here I have the impretion that $H$ is doing the same thing that $A_{tm}$ does. But If it's saying that $H$ is decider, I can assume that $H$ has some magic power to discover if $A_{tm}$ will halt in input $w$

Now we construct a new Turing machine $D$ with $H$ as a subroutine. This new TM calls H to determine what $M$ does when the input to M is it own description $<M>$. Once $D$ has determined the information, it does the opposite. That is, it rejects if $M$ accpets and accepts if $M$ does not accept. The follow is a descripion of $D$:

No problem here.

\begin{equation} D=\begin{cases} 1. &\text{Run $H$ on input <M, <M>>}.\\ 2. & \text{Output the oposite of what $H$ outputs; that is, if $H$ accpets, reject and if $H$ rejects, accept}. \end{cases} \end{equation}

Here is where I find hard to understand. The input string of $H$ is $<M, w>$, how could it run some thing like $<M, <M>>$ ?

If was only $<M>$, I could imagine that $w$ is the empty string.

I understand the halting problem with the following code:

function halts(func) {   // Insert code here that returns "true" if "func" halts and "false" otherwise. }  function deceiver() {   if(halts(deceiver))     while(true) { } } 
Asked By : Rafael Castro

Answered By : Luke Mathieson

The first misconception is that $A_{TM}$ is a Turing Macahine. $A_{TM}$ isn't a machine, it's a language, $H$ is the machine that decides the language $A_{TM}$. So you give $H$ a string that consists of two parts, a string $M$ that describes a Turing machine, and another string $w$, which can be anything.

This leads us to the second part, $w$ can be any string - it's the theoretical input to $M$ that you want to know whether $M$ would accept or not. So $H$ should accept if $M$ would accept $w$, and reject otherwise (i.e. when $M$ doesn't accept, which could be by rejecting or never halting). $\langle M \rangle$ is just a string, it happens to coincidentally be a description of a Turing Machine, but it is still just a string. So there's no reason we can't ask "does $M$ accept the string which is its own description?"

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback