Sunday, October 11, 2009

Non-Computable Problems: Halting problem and others

If you have not studied algorithm complexity analysis this might seem a little strange. There is actually problems that the computer can't solve no matter what happens. To make it a little easier to understand, we usually think that there is nothing a human can't do but can a human fly! We'll it's not possible. You can say the same thing about non-computable problems, it's just problems that the computer can't solve.
Halting Problem:
One example, that always pops to one's mind when asked about non computable problems, is the Halting Problem. This problem is fairly simple "Given a program and an input to the program, find whether the program will run indefinitely or not when processing that input" in other words find if a certain input will cause a program to enter an infinite loop. And the computer can do that!
There is a fairly complicated proof for that problem and you can find it here .
Other Problems:
What made me mention this class of problems is that we've been asked to find other problems that are not computable which seemed kind of interesting so I searched for a while and found some,
The Totality problem: this problem is just a generalization of the halting problem and it states "Given a program, find if this program will terminate on all its inputs or not". And it's fairly simple to proof non computable given that the halting problem is non computable too.
Also there is The Equivalence Problem which states "Given two programs find whether the two programs solves the same problems or not".
You can find more of those problems and there proofs here.
I hope that this post got you thinking about what the computer can really do!

No comments:

Post a Comment