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?