Sunday, November 16, 2008

Will it halt?

This is perhaps the most important thing we should like to know about any process. OK I agree it doesn't seem like an important thing to know. What's the big deal? So lets just say, I have it with me: I have an algorithm to determine whether an algorithm will halt or not and it is always right. I call it h(a,i). It takes any algorithm a as it's first input and an input string i, algorithm a will work on, as its second input. It i.e. h(a,i) returns "will halt" or "will not halt" as its output.

Imagine what I could do with this h(a,i)! I can prove the Goldbach's conjecture and get the Field's Medal with it. More importantly, I can prove everything and win all the field's medals forever. ROFL!

OK here is how I will do it. But first, Goldbach's conjecture:
Every even integer greater than 2 can be written as the sum of two primes.
Nobody has proved it as such. Distributed supercomputers have verified this to be true until 1018. But hey! I have h(a,i)! So I write a program p(i) that loops over all possible even integers greater than i and halts whenever it finds an even number that cannot be written as sum of two primes. Now the best part is I don't even have to run p till the end of time. All I have to do is run h(p, 2). If it returns "will not halt", then Goldbach's conjecture is true or else it is false! What more evidence do we need than to know all even numbers greater than two can be written as sum of two primes? LOL!

Similarly, I could use h(a,i) to prove everything and anything!

P.S: Sorry to get your hopes up. This article was about the well known Halting Problem. And Alan Turing proved a perfect h(a,i) that computes correct answers for all possible values of a and i are impossible. He used a variant of Cantor's Diagonalization Argument to prove it. However a lot of partial versions h(a,i) that compute on a subset of a and i are possible. That is why automatic theorem provers exist. So tough luck guys! There are no easy paths to win Field's Medal :(

P.P.S: The Matrix Trilogy explores the philosophical implications of the halting problem. In it Oracle is like h(a,i), in that it is designed to predict the behavioral outcome of any process (e.g. a human mind, a set of events). It is right most of the time. However Neo is a special process, in that it tries to create a final outcome that would prove Oracle's prior prediction to be wrong. This is evident in the final conflict in Matrix Revolutions where Agent Smith gets the eyes of The Oracle and predicts Neo would give up in the end, but Neo simply chooses to contradict by not giving up. 

In fact this story is so close to the Halting Problem that Alan Turing's proof is all about proving the existence of algorithm "Neo" for all h(a,i). The existence of algorithm "Neo" also hints on the possibility of generating freewill within an algorithm. All one would need is a genetic algorithm that all become a better approximation of h(a,i) in each generation and an algorithm "Neo" to contradict it.

Fascinating! Isn't it?

No comments: