Understand the Answer. Hell it Took Me 30 Years to Understand the Question!

My hobbies over the years have been mathmatical logic, the attempt to model thought and deterministic programming. Obviously this has brought me to many odd places like feedback robotics, natural language parsing, symbolic logic, the ontology of time, etc., so it is not surprising over the years I have run across the halting problem and Godels refutation of Peano's axioms, to name just a few of the philosophical conundrums confounding modern day philosophers.

I finally had some free time this past week so I returned to a topic that has always eluded me; namely why is the halting problem such a big deal. I liken it to Godel's proof because they both rely on the use of Cantor's Diagonal to formally construct their proofs. Cantor's Diagonal is a way to formally introduce the concept of infinity into an equation. He was an evil man :-)

I guess one of my problems with understanding the actual question (or problem) is that being brought up as a computer programmer I always had to take into consideration the resources at hand when developing algorithms so I rarely had the luxury of assuming unlimited (or infinite) resources in any application I would develop. When I would study a problem in classic mathematical logic it became clear many proofs that a system was inconsistent would rely on the introduction into the equations of the notion of infinity and this always confused me. After all, nothing is infinite in real-life so how do we allow it into our every day equations like it is some real quantity rather than some abstract notion? It almost makes one glad Cantor ended up institutionalized.

So this past week it finally dawned on me the halting problem (much like Godel's proof) is simply the result of allowing infinity into the equation. While it is derived from Hilbert's Entscheidungsproblem it is basically the problem of recursively allowing the output of an operation to be used as the input. It really has little to do with recursive function theory or set theory and more to do with ignoring the very real constraints we experience in every day life (like time, clipping, etc).

I do not mean to say that time, resource constraints, etc are the only problems as Russell's Paradox demonstrates it is really more infinity based, or the belief that any system can handle unrestrained totality. In reality systems are constrained and I believe we are best served by constructing systems with input constraints in mind. In so doing we can reduce the unpredictable to predictable within reason.