A recent conversation I had with a friend concerning the existence of deities prompted me to think a bit more deeply about how man has used logic to help describe or extract truths in the world and then use use to our advantage.

In the process we have been able to describe thousands of real natural systems and exploit them, from our understanding of the biology of corn and other plants and then using that knowledge to modify them to suit our purposes...to the realizations of the patterns of truth that govern the behavior of planes in the sky or missiles on a launch trajectory. All these things are enabled by the slow acquisition of knowledge concerning the invariant truths and relationships of the real world.

However, we often fail to realize that the certainty of control that we appear to have over the world is mostly an illusion. As a scientist I was trained to prize empirical data above all else, data informs hypothesis and sets of hypothesis inform theories...these theories are then tested against more incoming empirical data to refine them over time...it is a beautiful system that has a constant vector toward the direction of increasing truth so long as that which is observed remains stable enough to enable the statement "increasing truth" true. David Hume showed that this is an arbitrary selection on our part enabled by the fact that for most of the things we do study there is invariance in the underlying basis that we latch our logical "formal systems" on to in order to make predictions.

We do it in quantum mechanics, we do it in kinematics, we do it in biochemistry and it is the hope that the electron charge won't suddenly change, among other hopes that enables our theories to have the great deal of accuracy we put on them. Yet beyond the protection from the variability of key elements of reality there is a need to recognize that outside of empirical data gathering our ability to cognate the possibilities is actually restricted...in fact according to Greg Chaitin possibly infinitesimally so.

However the start of our search for logical certainty goes back a bit further and for that we should start with the work of a brilliant mathematician who happened to be the friend of Albert Einstein, his name?

Kurt Godel and Incompleteness

Kurt Godel was an amazing character in the history of mathematics, particularly quirky he focused his work on one of the most abstract areas of mathematics, logic itself. In mathematics logic is formalized to a degree that goes far beyond what you may have learned when you took courses where you were introduced to "modus tolens" and other such concepts. The tools used by Godel were applied to attempt to explore the limits of mathematics itself. In the mid 30's Godel wrote his seminal paper on mathematical incompleteness in it he set off a quiet bomb in the mathematical community. Decades earlier people like Bertrand Russell and David Hilbert tried to set programs for systematizing all of mathematics, they felt that it were possible to classify all the possible structures that span mathematical ideas...by doing so they would show that math was "complete" in that it was fully descriptive of all elements that could be defined within it. Godel's incompleteness theorems showed that these efforts would never succeed.

A simple idea

The idea of incompleteness spans from a simple idea, that in order for our formal systems to fully describe the world they must be able to determine answers for all questions posed with those systems. It may be found that some answers are incredibly difficult to answer but the hope was that in theory given enough processing time all questions in the system could be answered. Godel showed that this was not true and in fact had a reciprocal relationship governing it. In the mathematics he used the word "complete" indicates that a formal system is able to satisfy the requirement above of being able to answer all possible questions posed within it. Godel showed that only formal systems with infinite axiom sets (losely the rules that define how that system functions) can be complete. Where a complete system is simply one that satisfies the ability to answer all questions that can be asked with those tools. The reality though is that if the systems have a finite set of axioms (and all our formal systems are) then there are questions within them that can NOT be answered. If this wasn't devastating enough for the systematization program that Hilbert and others sought it gets worse. Not only are there questions that can't be answered in the system but there is no way to infer where those "holes" lie in the system before hand, trial and error is the only guide. For decades after Godel wrote these papers mathematics (and the physics that uses mathematics to build it's descriptive system of the world) were in denial. The fact that some things could not be answered was not fully appreciated...but then things only got worse when a British genius started looking at the matter from a different view...

Alan Turing tackles thought...

Alan Turing is a giant in computing, often called the father of the computer and one of the principle designers of the ENIAC computer that helped break codes, he also deciphered a complex cipher used in the German Enigma machines during the war, providing the allies incredible insight into German operations which they used to misdirect and ambush the Germans opportunistically for more than a year. However, Alan Turing also thought a great deal about the limits of computing machines, he was familiar with Godel's work and wondered what incompleteness meant for the human mind...in several papers he showed that the answer was even more amazing and devastating to our efforts to divine all truth than Godel's. Turing showed that not only are all systems filled with holes, gaps in their ability to divine truth of questions posed within them...but that because we as human beings are computing agents our minds are limited by the same constraints of systems we design to model the world. His "halting problem" states that some problems fed to a computing agent would never yield an answer and those problems are then undecidable...an undecidable problem is worse than one that can't be inferred with a given system because one has no recourse to gaining the answer. In Godel's incompleteness , the hope still remained that some clever over lap of systems could illuminate gaps in different systems...but Turing showed that this task for some "holes" would indefinitely continue (you could never create enough systems and thus never fully be able to infer the truth or false nature of the original question posed.

As occurred with Godel, the world met Turings results with silence...ultimately his result is not about just computers it is about us, we are computing machine but are we limited by these findings. Godel tried to find the answer and some say the task drove him insane...one of the most brilliant minds in all of mathematical history driven mad by his work.

The failing of logic...

Contemporary mathematicians like Gregory Chaitin took the problem further by asserting that not only are their undecidable problems but there are an infinite number of such problems...that we are in fact living in a space of possibilities that are infinite in answers and our ability to answer is infinitesmal...what a bizarre conclusion...that in our certainty...in all the things that we think we have inferred about the world. How it formed, how our sun formed, how life evolved, how the Universe expanded all these things are are within the sliver of empirically derived transitory "Facts" in a space of such "facts" that our systems are useless to ever divining. So it would seem that logic fails us miserably...it enables us to posit absurd statements based on nothing more than a whim and be unable to prove or disprove our own assertions! We can do this infinitely and thus we connect to the space of possibilities that may have decidable answers to them but that we can't determine because our systems are not constructed to do so.

That yellow invisible alien standing next to you loves you and you can't disprove his existence...even though I just asserted it from thin air...such is the contradiction of logic, a thing which is simultaneously absolutely useful to our inferring truths about the world and just as useless to divining all possible truth states. I find the symmetry of this contradiction both terrifying and beautiful.

Links:

http://en.wikipedia.org/wiki/Halting_problem

http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems

http://en.wikipedia.org/wiki/Kurt_godel

http://en.wikipedia.org/wiki/Alan_Turing

http://en.wikipedia.org/wiki/Gregory_Chaitin

http://www.youtube.com/watch?v=Cw-zNRNcF90

## Comments