View previous topic | View next topic

Infinite Programs

Page 1 of 1

s.o.z.
960201.  Wed Jan 02, 2013 4:52 pm Reply with quote

I think this qualifies as quite interesting, although my post is also quite simplified as I don't think I understand the proof well enough to explain it fully in a simple way (though I think the poem I've attached does a good job of it).

Simply put; it is actually impossible for an algorithm/formula to exist that can decide if a computer program will run infinitely. This was proven by the legend Alan Turing himself (is there anything the man can't do?).

This is the "answer", though an unsatisfying one, to something called the halting problem: (I'm copying from Wikipedia here) "Given a description of an arbitrary computer program, decide whether the program finishes running or continues to run forever".

Prof. Geoffrey Pullum has written a wonderful poem called "Scooping the Loop Snooper" about the halting problem that explains the proof that the halting problem is unsolveable.

Scooping the Loop Snooper:

(an elementary proof of the undecidability of the halting problem)

No program can say what another will do.
Now, I won't just assert that, I'll prove it to you:
I will prove that although you might work til you drop,
you can't predict whether a program will stop.

Imagine we have a procedure called P
that will snoop in the source code of programs to see
there aren't infinite loops that go round and around;
and P prints the word "Fine!" if no looping is found.

You feed in your code, and the input it needs,
and then P takes them both and it studies and reads
and computes whether things will all end as the should
(as opposed to going loopy the way that they could).

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 I would use - and it's simple to do.
I'd define a procedure - we'll name the thing Q -
that would take and program and call P (of course!)
to tell if it looped, by reading the source;

And if so, Q would simply print "Loop!" and then stop;
but if no, Q would go right back to the top,
and start off again, looping endlessly back,
til the universe dies and is frozen and black.

And this program called Q wouldn't stay on the shelf;
I would run it, and (fiendishly) feed it itself.
What behaviour results when I do this with Q?
When it reads its own source, just what will it do?

If P warns of loops, Q will print "Loop!" and quit;
yet P is supposed to speak truly of it.
So if Q's going to quit, then P should say, "Fine!" -
which will make Q go back to its very first line!

No matter what P would have done, Q will scoop it:
Q uses P's output to make P look stupid.
If P gets things right then it lies in its tooth;
and if it speaks falsely, it's telling the truth!

I've created a paradox, neat as can be -
and simply by using your putative P.
When you assumed P you stepped into a snare;
Your assumptions have led you right into my lair.

So, how to escape from this logical mess?
I don't have to tell you; I'm sure you can guess.
By reductio, there cannot possibly be
a procedure that acts like the mythical P.

You can never discover 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!

(http://introcs.cs.princeton.edu/java/76computability/halting-poem.html)


Let me know if I've phrased anything unclearly or if I've misunderstood or misstated anything!

 
Jenny
960221.  Wed Jan 02, 2013 8:37 pm Reply with quote

Hi soz, and welcome to QI :-)

I do hope there are no copyright issues with that poem, but it's an interesting one.

 
'yorz
960223.  Wed Jan 02, 2013 8:55 pm Reply with quote

And the metre sublime :-)
Welcome, soz.

 

Page 1 of 1

All times are GMT - 5 Hours


Display posts from previous:   

Search Search Forums

Powered by phpBB © 2001, 2002 phpBB Group