A proof that the Halting Problem is undecidable

Geoffrey K. Pullum
(School of Philosophy, Psychology and Language Sciences, University of Edinburgh)

No general procedure for bug checks will do.
Now, I won’t just assert that, I’ll prove it to you.
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!

Pages I run through

Ok, So I have decided to post this list as my motivation to collect and read more books …

This entry is written a while ago (4am ), The sun had already woke up and still I am wide awake.. @_@

And since I cannot sleep, I decided to  check for logical gaps and edit my proofs for my problem set due this week, and

of course to publish this.

Here is the list of books I’ve read, and still reading..

This is quite an accomplishment for me, because I am the type of person who likes to start reading then,

give up when I’m bored or too busy to spare my time reading non-academic stuff.

With no particular order, here  ‘tis.

1. Night- one of the books that reminds me how blessed and comfortable my life is.

2. The curious Incident of the dog in the Night time – one of my favorites, it teaches me  to love Math and Physics. It awakens the “hungry for knowledge” side of me.

3. Love in the Time of Cholera- True love waits. It gave me another perspective of what love really is.

4. ABNKKBSNPLAK- A mirror on my childhood/elementary experiences

5. Alamat ng Gubat- simplistic yet unfathomable.

4. MacArthur- I can’t remember the tone of Bob Ong in this book, but surely he made me laugh

5. Libro ni Hudas-

6. Just like Jesus- Made me cry when I first read this, life changer

7. Purpose Driven Life- another life changer book, a must read

8. What Mad man pursuit- The story of Francis Crick as they unravel the DNA form

9. On the origin of Species- The beagle expedition, and memoir of Mr. Darwin himself. It depicts his struggle as he oppose the church for the development of his research

10. Captivating- I gained a lot of self worth, when I read this book.

11. Lord of the Rings: Fellowship of the Ring- An epic fantasy!!! I fell in love with Tolkien.

12. The Hobbit- Fascinating, well told, and now I wanted a bed sheet with Middle Earth’s map. Yay

13. Angela’s Ashes: It is a depiction of how man struggles to live. McCourt is one of  the best.

14. Eat Pray Love- Yay.. I fell in love with Italy.

15. Uncle Petros and the Goldbach’s Conjecture: “Mathematicians are not made, they are born”, Though I am not born to be it, I am encouraged to add something to the body of knowledge of mankind, by doing my greatest efforts on my productive years.

In Queue (I am reading this in Parallel)

1. My incredibly miserable life

2. The Silmarillion

3. Metamath

4. Harry Potter (Book 1)

DanCelelebration 2010

DanCelebration 2010: Youth for Nation

The 23rd DanCelebration with the theme “Youth for Nation” held at De La Salle University last February 6 was awesome. As said in the introduction of the two emcees, it was the longest running intercollegiate competition in Metro Manila.

The dance contest is divided into two categories, the first one is street dance and the latter is contemporary. Unfortunately, I was only able to watch the street dance part because it’s too late for me to go home if I will finish the show.  Twelve contestants from different Universities passionately expressed their ideas on how youth can change the nation. Two of those twelve entries are from UP Street Dance Club, which I admired for their coherence, surprising stunts and creative use of props. Different interpretations for the theme were presented through different context and moves by each dancer.

Generally the whole show was great except for those annoying cheers from the crowd, though I expected a little more decent reaction from the viewers as strictly indicated at the back of the tickets under the rules and regulations of the theater.

In spite of that, all the performers are worthy of  praise for all the efforts and perseverance they gave for the success of the whole show.