It’s as if mathematics at the turn of the 20th century was seeking the ultimate theory of everything and Gödel proved that this just wasn’t possible. So far so good, or bad depending on your point of view. You may even recognize some of this theory as very similar to the theory of Turing machines and non-computability, in which case it might not be too much of a shock to you. However, at the time they were thought up both Gödel’s and Turing’s ideas were revolutionary and they were both regarded with suspicion and dismay.
It was thought to be the end of the dream: mathematics was limited. Mathematics wasn’t perfect and in fact every area of mathematics contained its limitations. Today you will find it argued that Gödel’s theorem proves that God exists. You will find it argued that Gödel’s theorem proves that human thought goes beyond logic. The human mind is capable of seeing truth that mathematics cannot prove. It is also argued that it limits artificial intelligence, because there are things that any machine cannot know and hence also proves that human intelligence is special because it can know what the machine cannot.
If you think about it, Gödel’s theorem proves none of this. It doesn’t even suggest that any of this is the case. Gödel’s theorem doesn’t deal with probabilities and what we believe, only in the limitations of finite systems in proving assertions about the infinite. Sometimes the infinite is regular enough to allow something to be proved. Sometimes, in fact most of the time, it isn’t. But important though this is, we live in a finite personal universe and we don’t demand perfect proof. We go with the flow, guess and accept good probabilities as near certainties.
And if you eliminate the infinite, Gödel's theorem doesn't hold.
Summary
Mathematical proof can be considered to be a game with symbols, axioms, that lead to proof. It was thought that this implied that math can be mechanized and reduced to an algorithm.
Many mathematical questions can be answered by an infinite search procedure. Not finding a counter example doesn’t prove anything and the power of math is in providing finite proofs for infinite searches.
Gödel proved that in any system of logic that was powerful enough to include arithmetic there were theorems that were true but for which a proof using the axioms of the system did not exist.
The incompleteness theorem was revolutionary and put a limit on what could be done with axiomatic systems. It has also been used, incorrectly, to prove many things such the existence of God and the inability of AI to equal real intelligence.
What the incompleteness theorem is saying is that there are some truths that cannot be established by a finite procedure, i.e. a proof.
If you expand the axioms to create a larger logical system then it is possible that what was unprovable becomes provable. The only problem is that new unprovable theorems are introduced.
A Programmers Guide To Theory
Now available as a paperback and ebook from Amazon.
Contents
What Is Computer Science? Part I What Is Computable?
The July Tiobe index is out and it isn't particularly interesting until you notice that it confirms the standard model of programming - code is written in Python and C and everything else is jus [ ... ]
Akka has launched a new Akka Agentic Platform that can be used to build, operate, and evaluate any type of agentic AI system. The platform provides orchestration, memory, toolkits for agents, and [ ... ]