Name: Anonymous 2010-11-25 14:22
Compilers can't tell if a program will halt,
but it's not exactly the compilers fault.
Don't believe me? Yup it is true..
read through this thread, I'll explain it to you.
No general procedure for bug checks succeeds.
I won’t just assert that, I’ll show where it leads:
for although you might work till you drop,
you cannot tell if program will stop.
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, an anxious creator,
so P gets to work, and shortly there 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 are hooped .
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 is the trick, its simple to do.
I’ll define a procedure, let's call it 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 which, 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 answers ‘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, frozen and black.
And this program called Q wont just stay on the shelf;
I would ask it to forecast its run on itself.
When it reads its own 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’
so Q starts to loop! (P denied that it would.)
If P says go left, Q will go right.
to watch it unfold is a terrible sight.
Whatever P says, it can't 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 hypothetical 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.
By reductio, there cannot possibly be
a procedure that acts like our posited P.
You just can not find mechanical means
for predicting the acts of computing machines.
It’s something that simply cannot be done.
but why let compilers have all the fun?
Programs are puzzles to solve, you see
Our craft would be ruined by mythical P.
So when you write bugs, and only you yelped
try to remember that it can't be helped.
but it's not exactly the compilers fault.
Don't believe me? Yup it is true..
read through this thread, I'll explain it to you.
No general procedure for bug checks succeeds.
I won’t just assert that, I’ll show where it leads:
for although you might work till you drop,
you cannot tell if program will stop.
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, an anxious creator,
so P gets to work, and shortly there 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 are hooped .
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 is the trick, its simple to do.
I’ll define a procedure, let's call it 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 which, 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 answers ‘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, frozen and black.
And this program called Q wont just stay on the shelf;
I would ask it to forecast its run on itself.
When it reads its own 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’
so Q starts to loop! (P denied that it would.)
If P says go left, Q will go right.
to watch it unfold is a terrible sight.
Whatever P says, it can't 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 hypothetical 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.
By reductio, there cannot possibly be
a procedure that acts like our posited P.
You just can not find mechanical means
for predicting the acts of computing machines.
It’s something that simply cannot be done.
but why let compilers have all the fun?
Programs are puzzles to solve, you see
Our craft would be ruined by mythical P.
So when you write bugs, and only you yelped
try to remember that it can't be helped.