The Statement and Implications of Gödel’s Theorems
In 1931, an Austrian mathematician, Kurt Gödel, at age 25 published his doctoral thesis, On Formally Undecidable Propositions of Principia Mathematica and Related Systems. In this epoch-making paper, Gödel enunciated a theorem and corollary that registered a magnitude ten on the seismometer of mathematical quakes. Simply stated, they are the following:
Gödel’s First Theorem
In any mathematical system complex enough to contain simple arithmetic, there exists an undecidable proposition–that is, a proposition that is not provable and whose negation is not provable.
Corollary (Gödel’s Second Theorem)
The consistency of any mathematical system complex enough to contain simple arithmetic, cannot be proved within the system.
Gödel’s theorem implies that whether we choose the axioms of Peano, Hilbert, Russell, or anyone else, there will always be theorems that are true, but can neither be proved nor disproved using only those axioms and the rules of logic. In this sense, the system is incomplete. We can prove or disprove any particular theorem in the system by adding one or more axioms, but then the corollary asserts that we will not know whether or not our new set of axioms is consistent.
Alan Turing’s conception of the Turing Machine
In 1936, just 5 years after Gödel’s publication, Alan Turing thought of this problem in a “computing-machine” context (later called a Turing machine) as follows: Imagine substituting integral values of the variables into a computing machine to determine whether those values satisfy the equation. If the equation is satisfied, the computer program terminates and prints out “Yup, there’s a solution.” If the equation is not satisfied, it picks another set of values and tries again. Turing asked, “Is there a program that can determine for any given diophantine equation whether the process will terminate, i.e., halt? This became known as the halting problem.
Turing was able to resolve the halting problem (Hilbert’s 10th problem) in the negative, confirming that there exists no algorithm or program that can determine, without actually substituting possible solutions, whether a particular diophantine equation, indeed, has a solution. (A proof is included in Intelligence: Where we Were, Where we Are, & Where we’re Going.)
Gödel had established that we cannot know whether a mathematical theorem can be proved or disproved from a given set of axioms. Since a computer program merely deduces logic-based results from a set of axioms, the Turing machine (a theoretical computer) is also unable to determine whether a program will yield terminate, thereby yielding a solution or a declaration of no solution to an equation.
Alan Turing meets Claude Shannon
In 1938, just two years after Turing resolved Hilbert’s 10th problem with his abstract turing machine, Claude Shannon, a 22-year old graduate student at MIT, provided a key link in turning Turing’s machine into a reality. In a ground-breaking paper based on his master’s thesis, he showed how the operations of boolean algebra could be represented using switching circuits. Early in 1943, Shannon was having tea in the cafeteria of the Bell Labs where he met British mathematician Alan Turing. Turing shared with Shannon a paper he had published in 1936, outlining how a theoretical device (later called a Universal Turing Machine)could execute a series of instructions, composed only of 0’s and 1’s, to perform any mathematical or logical computation. Shannon was impressed with Turing’s work in cryptography (encoding and decoding messages) because it was closely related to his work at Bell Labs in finding the best way to encode messages to minimize noise. His work in this area eventually led to the use of switching circuits in computers and the creation of information theory, paving the way for the Internet 50 years later.
Computer Science and Complexity Theory
Gregory Chaitin, one of the founders of complexity theory, argues that there are things in nature that are so random as to be incompressible. Pursuing an argument similar to that presented by Brouwer and other mathematicians, he asks, “Why should I believe in a real number [a number like π with a non-repeating infinite decimal expansion] if I can’t calculate it, if I can’t prove what its bits are, and if I can’t even refer to it?” He suggests that Gödel’s Theorem is good news, because it asserts that nature is not compressible into a small set of axioms and is therefore endowed with the kind of complexity that maximizes diversity. Arguing against the hope that computer-proving software will eventually certify all mathematical proofs, he stated in 2005:
Formal axiomatic systems are a failure! Theorem-proving algorithms do not work [bold lettering, his]. One can publish papers about them, but they only prove trivial theorems.
The epistemological discussions continue as we move more deeply into artificial intelligence and it appears that quantum computing through its capacity for parallel processing will not provide anything more than merely yielding a faster processing speed. Our access to truth may be much more obscure than first thought and our current awareness of this complexity began with Gödel’s insight.
