April fools!

Actually, this is fundamentally impossible to make. Why? The answer goes back to Alan Turing and the halting problem. The question of the halting problem is, is it possible to construct a program that can tell if another program will halt? Well, consider this program (in Wikipedia-style pseudocode):

functionexample()

ifhalts?(example)then

infinite-loop()

else

returnnil

So, what happens when we run

*halts?*(example)

? Well, if this returns true, then `example`

itself should go into an infinite loop, not halting. If it returns false, indicating that the example loops forever, then it in fact quickly returns nil and halts. So there's no real answer to whether this halts. And--it's not hard to see--there are (countably) infinitely many similar programs that exploit the same loophole.When I first learned this, I thought, "This is cheating; that's too easy." Well, yes. That's higher level math for you. But there's another way of thinking about it, without that cheating device: to be able to tell if absolutely

*any*piece of code halts, you need to know everything about that code and basically run it in some sort of emulator. There are cases where you can know it doesn't halt, but if it doesn't halt unexpectedly, and you're running the code... that doesn't work.

Building off of this, think about complexity: the first thing you need to know before assessing complexity is whether an algorithm halts. But we just showed that we can't do that! Also, what if the code does something like this:

functionexample2(n)

ifcomplexity(example2) =O(n) then

return new integer[n][n]// this takes O(n^2)

else ifcomplexity(example2) =O(n^2) then

return new integer[n]// this takes O(n)

and we want a tight bound for complexity.

Of course, specific solutions are possible, but these are both difficult to construct and highly limited in function. I hope you had fun with your daily dose of pessimism!

## No comments:

Post a Comment