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

Question

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) { }
}

Answer 1

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

Answer 2

<M,<M>> is like the functionality of the following C++ codes: (file name: test_self.cpp)

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main()
{
    string file_name;
    cout << "Enter the file name: ";
    cin >> file_name;
    fstream out(file_name, ios::in);

    if(!out){
        cout << "Can't open the file!" << endl;
        return 1;
    }

    while(!out.eof()){
        string line; 
        getline(out, line);
        cout << line << endl;
    }

    out.close();

    return 0;
}

It's not as strang as you think because you can view any source file as a pure text file, which consists of several characters. After the source file compiles into machine codes, it is different from the content of the source codes. After compiling, the source file is still there and since it's just a text file, you, of course, can read its contents even if the source file is the same as the file before compiling. You can try out the above program and see what the contents shows in the console(especially if you enter test_self.cpp). Then, I think you can understand what <M,<M>> means.