Gödelpriset

the Gödel Prize – årligt pris för enastående artiklar i ämnet teoretisk datorveten­skap. Det är uppkallat efter logikern Kurt Gödel. Priset har delats ut sedan 1993. Bakom priset står ACM och European as­so­ci­a­tion for theoretical computer science, EATCS (eatcs.org). I priset ingår 5 000 dollar. – Kurt Gödels insats för datorvetenskapen var dels att hans ofullständighetssats inspirerade Alan Turing till artikeln om Turingmaskinen, dels att han var först med att formulera problemet P=NP.) – Se denna webbsida.

[datorvetenskap] [utmärkelser] [ändrad 6 juni 2017]

avgörbarhetsproblemet

das Entscheidungsproblem – frågan om det går att avgöra ifall ett matematiskt eller logiskt påstående är sant eller falskt på ett mekaniskt sätt (alltså med en algoritm) som ger rätt svar för alla mate­matiska och logiska påståenden. – Pro­blemet fick sitt namn av den tyska ma­te­ma­tik­ern David Hilbert (1862—1942, se Wikipedialänk – se också Hilberts paradox), men andra filosofer och matematiker hade tänkt i samma banor tidigare. Ett annat sätt att se på saken är att fråga ifall det finns ett logiskt–matematiskt språk som kan användas för att formulera varje tänkbart problem, och som också kan användas för att räkna ut lösningen. Kurt Gödels ofullständighets­sats från 1931 visade indirekt att det inte går att avgöra, och något senare visade Alan Turing och Alonzo Church, obe­ro­ende av varandra och på olika sätt, att svaret på frågan är nej. Turings bevis innehöll beskrivningen av det som numera kallas för Turing­maskiner. (Avgörbarhetsproblemet kallas också för avgörandeproblemet.)

[matematik och logik] [ändrad 6 juni 2017]

stopproblemet

Tecknad bild av superdatorn Deep Thought från Liftarens guide till galaxen.
Datorn Deep Thought som behövde 7,5 miljoner år för att räkna ut svaret.

(the halting problem) – frågan om det på förhand går att räkna ut ifall en körning av ett dator­­­program kommer till ett slut någon gång, eller om beräkningen fort­sätter i all evighet. – Alan Turing bevisade i sin berömda artikel ”On computable numbers with an application to the Entscheidungsproblem” (länk) från 1936 att upp­giften är olöslig. – Ob­servera att detta gäller när frågan ska besvaras enbart med mekaniska metoder och för varje tänk­bar beräkning. En matematiskt kunnig mänsklig bedömare kan ofta avgöra ifall en beräkning kommer att fortsätta i evighet eller om den tar slut någon gång, men stopproblemet gäller ifall man kan programmera en dator så att den avgör saken i alla tänkbara fall och utan mänsklig hjälp. – Vi vet till exempel att om vi sätter en dator att räkna ut det exakta värdet på pi så kommer den aldrig att bli klar, men det ”vet” inte datorn. Att det är så har mänskliga matematiker räknat ut, och det har de inte gjort genom att räkna på pi oändligt länge. Hur länge man än räknar på värdet av pi så får man nämligen inte, enbart genom att fortsätta räkna, någon in­for­ma­tion om ifall räkne­arbetet tar slut någon gång, eller aldrig tar slut. – I upp­­satsen ”On computable numbers…” beskrev Turing också det som senare blev känt som Turing­maskinen. – Några månader före Turing hade Alonzo Church bevisat samma sak, fast utan att beskriva en maskin. – Stopproblemet är besläktat med avgörbarhetsproblemet (das Entscheidungsproblem), men också med Kurt Gödels ofullständig­hets­sats. – Läs också om omega (Chaitins konstant).

[datorvetenskap] [matematik och logik] [ändrad 6 juni 2017]

Gödel, Kurt

Kurt Gödels ansikte.
Kurt Gödel.

österrikisk-amerikansk matematiker och logiker (1906—1978). – Kurt Gödels ofullständighetssats från 1931 inspirerade Alan Turing till analysen av stopproblemet. – Ofullständighetssatsen visar att det inte kan finnas logiska och/eller matematiska system som på samma gång är hel­täckande och motsägelsefria. Med hel­täckande menas att regelsystemet kan tillämpas på alla påståenden som kan formule­ras inom systemet. I varje system av lagar, regler och symboler – till exempel matematik – kan man, visade Gödel, alltid hitta påståenden som uppenbarligen är sanna, men som inte kan bevisas inom ramen för systemet. Det går kanske att bevisa påståendet om man lägger till nya regler – men om man gör det så går det ofelbart att, med användning även av de nya reglerna, formulera nya påståenden som i sin tur inte kan bevisas, men som ändå uppenbar­ligen är sanna. Detta bevisade han i artikeln ”Über formal unentscheidbare Sätze der Principia Mathematica und Verwandte System” (engelsk översätt­ning här). – I själva verket finns det två ofullständighetssatser, som hör ihop:

  • – Den första är den som beskrivs ovan;
  • – Den andra satsen säger att ett sådant system som beskrivs i den första satsen inte kan bevisa att det är mot­sägelse­fritt.

– Se också Ent­scheidungs­problem. – Gödel lämnade Österrike efter den tyska ockupationen 1938 och fick då en tjänst på Institute of advanced study (ias.edu) i Princeton, New Jersey, där han blev god vän med Albert Einstein. – Gödelpriset är uppkallat efter Kurt Gödel. – En biografi över Kurt Gödel är Ofullständighet: Kurt Gödels bevis och paradox (Incomplete­ness: The proof and paradox of Kurt Gödel, 2005) av Rebecca Gold­stein (webbplats).

[för- och bihistoria] [kurt gödel] [matematik och logik] [personer] [ändrad 6 maj 2020]

Church, Alonzo

(1903—1995) – amerikansk matematiker. Han bevisade 1936 i artikeln ”A note on the Entscheidungsproblem” (se avgörbarhetsproblemet) att det finns mate­matiska problem som det inte går att lösa på med mekaniska metoder. Det var samma sak som Churchs studie­­kamrat Alan Turing bevisade senare samma år i sin upp­sats om stopproblemet. Turing visade senare att de två bevisen var likvärdiga. Båda bevisen byggde på Kurt Gödels ofullständighetssats. – Church‑Turings hypotes säger att alla matematiska beräkningar som kan beskrivas i ett ändligt antal steg (med en algoritm) kan lösas av en maskin. Om en nog­­grann men fantasi­lös människa med papper och penna kan räkna ut lösningen (lösa problemet mekaniskt) kan en maskin också göra det. Men: beräkningen kan pågå i all evighet. Till exempel är det lätt att beskriva divisionen 2 delat med 3, men det tar en evig­het att räkna ut svaret med decimala siffror (0,6666666……) om man inte sätter stopp. För att inte tala om sådant som att räkna ut värdet på pi. – Det som både Church och Turing bevisade var att även om en maskin kan utföra alla beräkningar som kan uttryckas som algoritmer, så kan maskinen inte avgöra ifall beräkningen tar slut någon gång, eller om den fort­sätter i all evighet. – En artikel på engelska om vanliga missuppfatt­ningar av Church‑Turings hypotes finns här.

[alonzo church] [datorvetenskap] [för- och bihistoria] [personer] [ändrad 6 november 2019]