We Do Not Know

When I took the Theory of Computation class last term, I was fascinated by the amount to which it stretched the limits of human knowledge. Perhaps it is because computation is so new a field – just 60 years ago, a “computer” was a woman at a desk with a pen and paper – or perhaps because it is a field that intrinsically bumps up against universal computation limits.

The ideas in the theory of computation that I want to focus on are related to Gödel’s (pronounced more like “guhdel”) incompleteness theorem. The actual proof is written in very technical language, but the idea is (according to the well-curated wikipedia page on the proof),

Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true, but not provable in the theory (Kleene 1967, p. 250).

Ignoramus et Ignorabimus – we do not know and we will not know. There exists some arithmetical statement that is true but not provable. If you’re not mathematically inclined, you could think of “this sentence is false”, as a kind of english-language nonprovable. If the sentence is true, it is also false. Not the most rigorous, but it gets the idea across.

We Will Not Know

The idea that there is a limit to what science can tell us was proposed in 1872, by a German scientist Emil du Bois-Reymond, about such things as “the ultimate nature of matter and force”. Scientists are still working on that, and discovering things like the higgs boson, purported to be the giver of mass. But the theory of computation bumps up against this threshold, with things like the Halting problem:

From Wikipedia’s page on the Halting Problem:

 The question is simply whether the given program will ever halt on a particular input.

For example, in pseudocode, the program:

loop forever

does not halt; rather, it goes on forever in an infinite loop. On the other hand, the program

print "Hello, world!"

halts very quickly.

While deciding whether these programs halt is simple, more complex programs prove problematic.

One approach to the problem might be to run the program for some number of steps and check if it halts. But if the program does not halt, it is unknown whether the program will eventually halt or run forever.

Given one of these programs of significant length, we have the problem that is unsolvable. Mathematical models of Turing Machines often expand out to quadrillions of steps, although they might simply be drawn as a few symbols on paper. For example, a Turing Machine that takes a Turing Machine as input, and determines something about the nature of that machine could take billions of steps to simply read in the other machine, much less process it.

Fascinating.

Supernatural

From a religious studies standpoint, we see an obvious hole to fill. What is beyond the edge of the known universe? What is the machine that can decide the halting problem? For some, a god fills this gap, something that technically possesses infinite power and knowledge, which exists outside of our natural universe.

Defining a mathematical “god” perhaps is useful. One can use it to define the origin of the natural numbers (a debate still held by, for example, Profs. Porciau and Sanerib in our own Mathematics department). Yet for others, the  notion is empty – there is still so much of our universe and ourselves to be discovered that deciding now whether or not there is an answer is ridiculous. It is okay to acknowledge that the answer may be discovered by humanity far after our lives are over, or perhaps never.

And yet, is that not a reflection of the halting problem? We do not know if we will find it (halt) or search for the answer forever.

Excuse me for a minute while I go lie down and process all of this.