The undecidability of the halting problem is not very important
Many a programmer, when confronted with a difficult computational problem, claim that it doesn’t make sense to investigate it further, since it is just a special case of the halting problem, and as proved by Turing back in the day, this is just not solvable in the general case. But I will try to show tha this is not a very useful or smart way of looking at things.
There are two important and opposite approaches that show the little utility of this thought process. They are two distinct attacks to the same area, both demostrably valid, and I hope to make them both easy to understand in this blog post.
The first issue involves the fact that, even if something is not tractable in the fully general case, it doesn’t mean there are not many useful cases where it’s not only perfectly tractable, but also well worth doing it. Let’s take static code analysis for example. Here is a nice piece of C code to find the maximum value in an array of unsigned integers:
|
1 2 3 4 5 6 |
unsigned int val = 0; for (int i = 0; i < N; +i) { if (array[i] > val) val = array[i]; } |
This code has a subtle but important bug: it will just never terminate. It’s actually an infinite loop. Why? Because the loop counter is not incremented. There is a typo, we missed a “+” sign in the “++i” expression, and thus the expression meant to increment the counter does nothing. Thus, the loop counter will stay at zero, and the code will loop until the sun goes nova.