From this moment on
Det finns en koppling mellan Gödels ofullständighetsteorem och datalogins grunder. Alan Turing, datavetenskapens fader, skapade datalogin med sin idé om en universell maskin. Hans teoretiska modell av en universell maskin, Turingmaskinen, kan beräkna allt som går att beräkna, men precis som Gödel så kommer Turing fram till att allt inte går att beräkna/bevisa.
Det finns ett grundläggande problem som kallas the halting problem, som inget program någonsin kan lösa. Given en beskrivning av ett program och en ändlig inmatning, avgör om programmet kommer att stanna eller kommer att köra för evigt, givet den inmatningen. Har man bara Turings resultat så få man Gödels resultat på köpet. Själva kärnan i Gödels ofullständighetsteorem är bara två rader lång. Kruxet är att man först måste ha konceptet med en dator innan man kan ge två-rads-beviset.
Så? Man får ett paradigmbyte inom matematiska bevis från klassiska QED-resonemang till brute force.
Fermats gåta var det sista klassiska problemet och fyrfärgsproblemet var det första som bearbetades med rå datorkraft. 
Andra bloggar om