Explanation of an explanation of Turing's proof to the halting problem?

Question

I am reading the transcription of a lecture from a professor Scott Aaronson, specifically the section titled Turing Machines. In this section he describes Turing's proof of the Halting Problem.

But can we prove there's no program to solve the halting problem? This is what Turing does. His key idea is not even to try to analyze the internal dynamics of such a program, supposing it existed. Instead he simply says, suppose by way of contradiction that such a program P exists. Then we can modify P to produce a new program P' that does the following. Given another program Q as input, P'

runs forever if Q halts given its own code as input, or
halts if Q runs forever given its own code as input. 

Now we just feed P' its own code as input. By the conditions above, P' will run forever if it halts, or halt if it runs forever. Therefore P' -- and by implication P -- can't have existed in the first place.

How would P(x) be defined here, the algorithm which can compute the halting problem?

halts if x halts
otherwise does ... 

Is P allowed to "output" something or only halt or not halt? It can write to a tape correct? So it could output 1 if x halts or 0 if it does not and then halt itself?... By attempting to define P am I trying to disprove Turing?..

Would we not need to know the source code of P to modify it to produce P'?

Is the overall idea of the proof that a machine to solve the halting problem would not be able to prove that it itself halts given its own source as input?

Answer 1

P should take two arguments: a TM M and a string x. P accepts if M halts on input x, otherwise rejects. Definition of P:

P(M, x): execute M on x and if it halts, go to the accepting state. If M doesn't halt on x, go to the reject state.

The language of the words accepted by P is Turing recognizable but not decidable. So you can define P, but the machine won't stop for all the inputs, and this is what you're trying to demonstrate.

You don't need to know the code source of P to produce P'. P' can be seen as:

P'(Q): execute P(Q, 'Q'), where 'Q' is the encoding of the TM Q, and if P accepts then don't halt, else halt.

The point is: if you suppose that a machine P that decides the Halting Problem exists, you're going to get a contraddiction. In fact you can produce a machine P' for the complement (you can do this because we are presuming the Halting Problem is decidable), so that it stops if the machine given in input doesn't and viceversa. If you try to use P' on P', then you get an antinomy.

I'm not sure this answer to your questions..