Does this proof really prove undecidability of halting?

Question

I want to ask a couple questions about the following proof. The proof originally came from a textbook and then a question on stackoverflow below.

How does this proof, that the halting problem‍​ is undecidable, work?

Question 1:

Does the proof below essentially make H a simulator for its input machine?

In other words, is there an important difference between saying H = M and the following description from the proof?

H([M,w]) = {accept if M accepts w}
         = {reject if M does not accept w.}

Question 2:

How is my following comments correct or incorrect?

I thought the halting problem was the problem of deciding if a given machine will halt regardless of its output(accept/reject). If a solution exists for a halting problem, it has to be something that analyses source code like a compiler/decompiler/disassembler instead of actually running it. If it needed to run it, obviously it would never determine on a "no" answer.

Noticing that apparent problem in the proof, the whole proof seems not to show undecidability of the halting problem.

The proof instead seems to show this: The following algorithm will not halt:

    boolean D()
    {
        return not D();
    }

Following is the proof in question retyped from Intro to the Theory of Computation by Sipser.

THE HALTING PROBLEM IS UNDECIDABLE

Now we are ready to prove Theorem 4.11, the undecidability of the language

ATM = {[M,w] | M is a TM and M accepts w}.

PROOF: We assume that ATM is decidable and obtain a contradiction. Suppose that H is a decider for ATM. On input , where M is a TM and w is a string, H halts and accepts 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

H([M,w]) = {accept if M accepts w}
         = {reject if M does not accept 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 its own description . Once D has determined this information, it does the opposite. That is, it rejects if M accepts and accepts if M does not accept. The following is a description of D.

D = "On input [M], where M is a TM:
1. Run H on input [M, [M]].
2. Output the opposite of what H outputs; that is, if H accepts, reject and if H rejects, accept."

Don't be confused by the idea of running a machine on its own description! That is similar to running a program with itself as input, something that does occasionally occer in practice. For example, a compiler is a program that translates other programs. A compiler for the language Pascal may itself be written in Pascal, so running that program on itself would make sense. In summary,

D([M]) = { accept if M does not accept [M]
       = { reject if M accepts [M]

What happens when we run D with its own description as input> In that case we get:

D([D]) = {accept if D does not accept [D]
       = {reject if D accepts [D]

No matter what D does, it is forces to do the opposite, which is obviously a contradiction. Thus neither TM D nor TM H can exist.

Answer 1

In other words, is there an important difference between saying H = M and the following description from the proof?

The H machine is called Universal Turing Machine (UTM) and is able to simulate any other Turing Machine, including itself.

If M is an Universal Turing Machine like H, it is ok to say H = M, otherwise this would be weird.

I thought the halting problem was the problem of deciding if a given machine will halt regardless of its output(accept/reject). If a solution exists for a halting problem, it has to be something that analyses source code like a compiler/decompiler/disassembler instead of actually running it. If it needed to run it, obviously it would never determine on a "no" answer.

That is why the proof works based on contradiction and it is kind hard to understand. Basically it assumes first that exists such a machine that answers "yes" or "no" to any given input. [Hypothesis]

Let's call this machine Q. Assuming Q is valid and it is an UTM, it can simulate another machine S that works following the steps below:

1. S reads an input (a program and its input)
2. S duplicates the input it just read
3. S calls Q passing the copied input
4. S waits for Q to answer (and based on our hypothesis it always will)

Let's imagine now the input Q(S, S). Q will receive the program S and the argument of S is S itself. This input will make S call Q indefinitely and will never stop.

Since Q and S were legal programs but there is a kind of input that makes Q never stop, Q is a machine impossible to built and therefore it is impossible to decide if a program S stops or not. Therefore we have the proof that the halting problem is undecidable.

Sipser explains it well. Read it again now and see if you catch the idea :)

Now, on to your question again. The Turing Machine is our most powerful machine for representing problems. As a recognition machine, it has to go through the input and run the algorithm to determine if it is valid or not. It is impossible to know the output of an algorithm without running it.

The compiler is just a translator of syntax and little semantics. It cannot foresee how one will use the program and what the output will be.