1
$\begingroup$

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) { }
}
$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ okey. H receives a string type <M, w>, which is a description of a TM M concatenated with a string w. I'm understanding that <M, <M>> is a string of description of a TM M concatenated with description of a TM M. That does not make sense. Why would be helpful give <M, <M>> to the decider H ? Feeding H with {<M, w> | w is the string received by D} would make sense, but why <M> ? $\endgroup$ – Rafael Castro Apr 12 '15 at 2:36

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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