Tuesday, April 25, 2006

Scooping the Loop Snooper

Warning : Techie poem ahead. Read at your own risk.

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!

by Geoffrey K. Pullum
Stevenson College
University of California
Santa Cruz, CA 95064

From Mathematics magazine VOL73. No. 4, Oct 2000 319-320

Saturday, April 22, 2006

Online petitions

Best web business idea today is to create an Online petition website. No matter what happens, create an online petition, circulate round of emails all around the world and get satisfaction that you have started a "revolution" now it's "world's" responsibility to carry it on. No matter what topic is just start a petition. Whether William Hung goes out of American Idol or some Rahul chap goes out of Indian Idol, just create a petition and show your outrage. How many petitions have you signed till date? and how many of them had positive outcome? or for that matter any outcome?

I am reminded of a story here. Churchill used to instruct his subordinates to keep woods and axe ready for him when he returns after acidic public lectures to subside his anger. Petitiononline seems to be doing same thing for us. Just to subside our anger. We feel we have done our part and get back to our lives!!!

One such mail came to me asking to sign petition to protest against quota in IITs and IIMs. Although I support the cause, I strictly believe this is not the way out.
Slimshady aptly puts it in words...

1. We signed this petition when Akshardham was attacked and they went to varanasi
2. We signed this petition when an IITian got slaughtered and they moved to IIM
3. We signed this petition when a Girl got Desecrated and they moved to another
4. We are signing this petition now so that they can divide and rule

Needs to do something solid rather than merely signing petitions. Various students from different IITs have gone on hunger strike. I don't know if it's effective move but atleast stronger move than signing petition. They might end up like Rajeev Goswami in case of Mandal Comission but they are putting out their anger and not feeling satisfaction by putting their names on online forums.

Quote of the day : The only verdict is vengeance; a vendetta, held as a votive, not in vain, for the value and veracity of such shall one day vindicate the vigilant and the virtuous....
--V for Vendetta

PS :- Although it may seem that it's contradicting to my stance on Blank Noise Project, but it isn't. Why you ask? Blank Noise Project had different purpose, different presentation and different audience. Read the need of Blank Noise Project here.

Monday, April 10, 2006

Being Cyrus

Once the game is over, The king and the pawn go into the same box.

With arrival of movies like Raincoat, Black, Iqbal, Page 3, Hazaaron Khwahishein aisi... Bollywood has proved that it's certainly moving forward and going to routes which has remained virgin to it. Being Cyrus is one such attempt. While others have attempted to go subtle. Being Cyrus is not only subtle, but also highly professional, stylish and well executed.

We see the movie through eyes of a young parsi, Cyrus Mistry. He joins family of Dinshaw Sethna, well-known pot-maker in the past and his wife Katy. What follows is a twisted story of Sethna family of Fardounjee Sethna and his sons, Dinshaw Sethna (Naseeruddin Shah) and Farokh Sethna (Boman Irani).

First half deals superbly with development of characters of both of the brothers, their father and their spouses. Homi Adjania, being a Parsi himself, gives superb look into the Parsi culture and mannerisms. Scenes like Boman Irani's encounter with his neigbour, Boman Irani's dealing with his father give a fair outlook. Second half starts a mystery where actual plot starts. Who is good? Who is bad? Who is killer? Who is victim? You never know!!!

Saif Ali Khan vowed to do film with a solo hero after Kal ho naa ho. At that point of time, he seemed overconfident, but in recent times he has definitely grown up into a decent actor. Boman Irani and Naseeruddin Shah are at their usual best. Simone Singh scores. Dimple Kapadia is adequate. Manoj Pahwa does more than what director might have hoped for him as Inspector Lovely.

At no point in movie you have dragging feeling. Editing is superb. Why not? Editing is taken care of by Jon Harris, who edited Guy Ritchie's Snatch. Camera work, Cinematography gives you an international feel. While other offbeats (Page 3, Iqbal) were different yet Indian, but this one is truly international class. Homi Adjania's work as a debutant is fabulous. Watch out for him, he's going to make big in new-age Hindi Cinema. Movie is a punch with its 90 minutes storyline. Highly recommended!!!

Other Reviews : Gaurav Sabnis, Rediff

PS:- This review has been cross-posted to InFiCa, where I am ahem...a movie critic now.