Melvin Henriksen–Professor of Mathematics Emeritus at Harvey Mudd College–biedt deze uitleg:
Het geven van een wiskundig precieze verklaring van Godels Stelling van Onvolledigheid zou de belangrijke intuïtieve inhoud ervan alleen maar verdoezelen voor bijna iedereen die geen specialist is in wiskundige logica. In plaats daarvan zal ik de stelling herformuleren en vereenvoudigen in de taal van de computer.
Stel je voor dat we toegang hebben tot een zeer krachtige computer genaamd Oracle. Net als de computers waarmee we vertrouwd zijn, vraagt het Orakel dat de gebruiker instructies “invoert” die volgens precieze regels verlopen, en het levert de “output” of het antwoord op een manier die ook deze regels volgt. Dezelfde invoer zal altijd dezelfde uitvoer opleveren. De invoer en uitvoer worden geschreven als gehele getallen (of gehele getallen) en Oracle voert alleen de gebruikelijke bewerkingen uit: optellen, aftrekken, vermenigvuldigen en delen (indien mogelijk). In tegenstelling tot gewone computers zijn er geen zorgen over efficiëntie of tijd. Oracle zal op de juiste manier gegeven instructies uitvoeren, hoe lang het ook duurt en het zal pas stoppen als ze zijn uitgevoerd – zelfs als dat meer dan een miljoen jaar duurt.
Laten we eens een eenvoudig voorbeeld bekijken. Onthoud dat een positief geheel getal (laten we het N noemen) dat groter is dan 1 een priemgetal wordt genoemd als het niet deelbaar is door enig positief geheel getal naast 1 en N. Hoe zou je Oracle vragen om te beslissen of N priem is? Zeg het om N te delen door elk geheel getal tussen 1 en N-1 en te stoppen als de deling gelijkmatig is of als het N-1 bereikt. (Eigenlijk kun je stoppen als het de vierkantswortel van N bereikt. Als er op dat punt geen even delingen van N zijn geweest, dan is N priem.)
Wat Godel’s stelling zegt is dat er goed gestelde vragen zijn die alleen over de rekenkunde van gehele getallen gaan en die Oracle niet kan beantwoorden. Met andere woorden, er zijn beweringen die – ook al zijn ze op de juiste manier ingevoerd – Oracle niet kan evalueren om te beslissen of ze waar of onwaar zijn. Zulke beweringen worden onbeslisbaar genoemd, en zijn erg ingewikkeld. En als je er een naar Dr. Godel zou brengen, zou hij je uitleggen dat zulke beweringen altijd zullen blijven bestaan.
Zelfs als je een “verbeterd” model van Oracle zou krijgen, noem het OracleT, waarin een bepaalde onbeslisbare bewering, UD, waar wordt verklaard, zou een andere onbeslisbare bewering worden gegenereerd om haar plaats in te nemen. Nog raadselachtiger is dat je ook een ander “verbeterd” model van het Orakel zou kunnen krijgen, dat OracleF wordt genoemd en waarin UD onwaar wordt verklaard. Hoe dan ook, ook dit model zou andere onbeslisbare uitspraken genereren, en zou resultaten kunnen opleveren die verschillen van die van OracleT, maar die even geldig zijn.
Vind je dit schokkend en bijna paradoxaal? Het was nog schokkender voor de wiskundige wereld in 1931, toen Godel zijn onvolledigheidstheorema onthulde. Godel formuleerde zijn resultaat niet in de taal van computers. Hij werkte in een welomlijnd logisch systeem en wiskundigen hoopten dat zijn resultaat afhing van de eigenaardigheden van dat systeem. Maar in het volgende decennium of zo, een aantal wiskundigen – met inbegrip van Stephen C. Kleene, Emil Post, J.B. Rosser en Alan Turing – aangetoond dat dit niet het geval was.
Onderzoek naar de gevolgen van deze grote stelling gaat tot op de dag van vandaag door. Iedereen met toegang tot Internet die een zoekmachine als Alta Vista gebruikt, kan honderden artikelen van zeer uiteenlopende kwaliteit over Godel’s Stelling vinden. Een van de beste dingen om te lezen is echter Godel’s Proof door Ernest Nagel en James R. Newman, gepubliceerd in 1958 en uitgebracht in paperback door New York University Press in 1983.