[trominos]

This is great but (unfortunately) it's not quite right. The author seems to have forgotten the difference between a program without specified inputs -- which can't be said to "halt" or "not halt", because it might halt on some inputs and loop on others -- and a program with specified inputs, which always either halts or loops.

Thus at one point the poem asks whether Q halts without specifying an input to Q. This question is meaningless.

The correct proof is given by BrandonM in a thread somewhere on this page. Check it out. (scott_s restates the incorrect proof above BrandonM, for comparison.)

[scott_s]

The bug in my pseudocode is that I did the wrong thing after consulting P inside Q. I'm not convinced that using "program" or "Q" as shorthand for "program(inputs)" and "Q(inputs)" changes the semantics of the pseudocode or the implications of the paradox.