Re:Did Turing prove the undecidability of the halting problem?
by afiori on Tuesday July 02, 2024 @04:01PM
(#40859945)
With a little massaging of input and output you can convert any program P into the program P_n defined as "repeat P n times".
For any n P terminate if and only if P_n terminates, so no general procedure can decide the halting problem for all programs except 1.
The limit case is maybe interesting. What about the algorithm that decides the halting problem for every program except for one? Does the impossibility proof prohibit such an algorithm? Does it make a difference if the identity of the unique program is known or unknown?
And then of course there is classic pen and paper hand derivation like the old guard (Knuth and his peers) did. The claim that that is following an algorithm is yet to be proved or disproved.