No general procedure for bug checks succeeds.
Now, I wonât just assert that, Iâll show where it leads:
I will prove that although you might work till you drop,
you cannot tell if computation will stop.
For imagine we have a procedure called P
that for specified input permits you to see
whether specified source code, with all of its faults,
defines a routine that eventually halts.
Â
You feed in your program, with suitable data,
and P gets to work, and a little while later
(in finite compute time) correctly infers
whether infinite looping behavior occurs.
Â
If there will be no looping, then P prints out âGood.â
That means work on this input will halt, as it should.
But if it detects an unstoppable loop,
then P reports âBad!â --- which means youâre in the soup.
Â
Well, the truth is that P cannot possibly be,
because if you wrote it and gave it to me,
I could use it to set up a logical bind
that would shatter your reason and scramble your mind.
Â
Hereâs the trick that Iâll use -- and itâs simple to do.
Iâll define a procedure, which I will call Q,
that will use Pâs predictions of halting success
to stir up a terrible logical mess.
Â
For a specified program, say A, one supplies,
the first step of this program called Q I devise
is to find out from P whatâs the right thing to say
of the looping behavior of A run on A.
Â
If Pâs answer is âBad!â, Q will suddenly stop.
But otherwise, Q will go back to the top,
and start off again, looping endlessly back,
till the universe dies and turns frozen and black.
Â
And this program called Q wouldnât stay on the shelf;
I would ask it to forecast its run on itself.
When it reads its own source code, just what will it do?
Whatâs the looping behavior of Q run on Q?
Â
If P warns of infinite loops, Q will quit;
yet P is supposed to speak truly of it!
And if Qâs going to quit, then P should say âGood.â
Which makes Q start to loop! (P denied that it would.)
Â
No matter how P might perform, Q will scoop it:
Q uses Pâs output to make P look stupid.
Whatever P says, it cannot predict Q:
P is right when itâs wrong, and is false when itâs true!
Â
Iâve created a paradox, neat as can be ---
and simply by using your putative P.
When you posited P you stepped into a snare;
Your assumption has led you right into my lair.
Â
So where can this argument possibly go?
I donât have to tell you; Iâm sure you must know.
A reductio: There cannot possibly be
a procedure that acts like the mythical P.
Â
You can never find general mechanical means
for predicting the acts of computing machines;
itâs something that cannot be done. So we users
must find our own bugs. Our computers are losers!