Next: What is Up: Structure and essence Previous: Structure in computing and   Contents

# Gödel and unfathomable complexity

Gödel's Incompleteness Theorem had a profound impact on mathematics when it was first established in the 1930's and a profound impact on me when I learned about it. At the beginning of the 20th century a famous mathematician, Hilbert, proposed the construction of a formula or mechanistic process for deciding all mathematical questions. Gödel proved this was impossible.

Mathematics then and now is based on formal systems. In effect these are mechanistic processes or computer programs for enumerating theorems. Gödel proved that any consistent formal system powerful enough to define the primitive recursive functions had statements in the system that could not be decided within the system. The primitive recursive functions are a fragment of elementary mathematics powerful enough to define a Universal Turing Machine. It was a shock to many mathematicians that there were mathematical questions that could not be decided with certainty. Mathematics is still digesting the implications of Gödel's result.

One implication is the Halting Problem. Although we can predict what a computer program will do at every step we cannot in general predict if it will ever do something such as halt. Of course if it does halt and we run it long enough we will observe it halting. But if it never halts we can not know that for certain. For there is no general way to determine when we will have waited long enough. For many programs we can decide the Halting Problem. Some programs have simple loops that continually repeat the same sequence in an obvious way. There are far more complex ways that a program can loop forever that we can understand. But we cannot do this in general for every possible computer program. There will always be programs that have some subtle way to loop or iterate that are beyond our current understanding. For me this suggested the creative nature of mathematics.

I was struck by both the fundamental emptiness and unfathomable complexity of the mechanistic structures that can be built up from the simplest of components. It appeared that all the complex structure of the universe could come from such simple structures. No finite being could every fully comprehend or experience the potential complexity that comes from these mechanistic structures. Yet no where in the vast complexity of mathematics and science is there anything that begins to touch on my own immediate experience. Yes I can understand how aspects of experience are structured or related to each other but the experience itself is completely beyond structural understanding.

This led me to ask what is?