Gödel, Kurt

Porträtt av Kurt Gödel.
Kurt Gödel. Foto: IAS.

österrikisk-amerikansk matematiker och logiker (1906—1978). – Kurt Gödels ofull­ständig­hets­sats från 1931 inspirerade Alan Turing till analysen av stoppro­blemet. – Ofull­ständig­hets­satsen 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 for­mu­le­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å uppen­bar­ligen är sanna. Detta bevisades i artikeln ”Über formal unentscheidbare Sätze der Principia Mathematica und Ver­wandte 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 Ofull­ständig­het: Kurt Gödels bevis och paradox (Incomp­lete­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 23 april 2018]

Church, Alonzo

(1903—1995) – amerikansk matematiker. Han bevisade 1936 i artikeln ”A note on the Ent­scheidungs­pro­blem” (se avgörbarhetsproblemet) att det finns mate­matiska frågor som det inte går att besvara 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 lik­värdiga. Båda byggde på Kurt Gödels ofull­ständig­hets­sats. – Church-Turings hypotes säger att alla mate­matiska 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 (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 be­räk­ningen tar slut någon gång, eller om den fort­sätter i all evighet. – En artikel på engelska om vanliga miss­­upp­­fatt­ningar av Church-Turings hypotes finns här.

von Neumann-arkitektur

den uppbyggnad av datorer som har varit standard sedan 1940-talet. Data och program lagras i samma minne – sammanhanget avgör vad som är vad. Arki­tek­turen är upp­kallad efter mate­ma­tikern John von Neumann, men andra forskare var med och utvecklade principerna. De första datorerna som tillämp­ade von Neumann-arkitekturen var brittiska Small-scale experimental machine från 1948 och ameri­kan­ska IAS-maskinen från 1952, som blev mönster­bildande. – von Neumann kände till Alan Turings idéer, men han ville göra ett dator­system som var mindre intellektuellt krävande för pro­­gram­merarna. Prin­ciperna beskrevs först i rapporten First draft on the Edvac (länk) från 1945 (se Edvac). – John von Neumann delade in datorn i fyra huvud­­delar, nämligen (med moderna termer) pro­cessor, minne, styrning och användargränssnitt. Detta var inget nytt: samma delar ingår i alla datorer, inklusive Charles Babbages analysmaskin, som ritades hundra år tidigare. Mer speci­fikt för von Neumann-arkitekturen är att den:

  • – har ett gemensamt minne för program­instruktioner och data. Vad som är vad avgörs av sammanhanget. Ett annat känne­tecken för von Neu­mann-arkitekturen är:
  • – att beräkningarna sker sekventiellt. Programinstruktionerna verk­ställs en i taget, data och instruktioner hämtas från minnet ett i taget.

– Under 1940-talet fanns en konkurrerande arkitektur, Harvardarkitekturen, som tydligt skilde mellan instruktioner och data. Det har gjorts många försök att utveckla nya arkitekturer. Främst gäller det att komma ifrån ”von Neu­mann-flask­­halsen”, den sek­ven­ti­ella inläsningen av data och instruktioner från minnet. Det går ju inte att läsa in instruktioner och data samtidigt, vilket gick i Harvard­arkitekturen. John von Neumann insåg för­delarna med parallell data­behandling, men han ansåg att det skulle bli för besvärligt att genom­föra. Numera är parallellism vanligt, eftersom datorer ofta har flera processorer, eller fler­kärniga pro­cessorer. Principen om gemen­samt minne har också ifråga­­satts, eftersom programspråk tydligt skiljer mellan data och instruktioner. – Efter­­som von Neu­mann-arkitekturen hanterar instruktioner och data i samma minne skulle man kunna skriva program som för­ändrar sin egen kod, men knappast någon utnyttjar den möjlig­heten.

[datorer] [it-historia] [ändrad 23 januari 2018]

Enigma

  1. – en portabel krypterings-maskin som under andra världs­kriget användes av Nazitysk­lands trupper i fält och till sjöss. Enigmas kryptering knäcktes av brittiska mate­ma­tiker och krypto­­experter under ledning av Alan Turing i Bletchley Park. Detta underlättades av att de brittiska styrkorna när de evakuerade Nordnorge i juni 1940 fick med sig tre intakta Enigma‑maskiner. Britterna kunde därför följa tyskarnas krypterade radiotelegrafi med bara någon timmes fördröjning. Detta anses ha bidragit till att förkorta kriget med uppemot ett år. – I själva verket var Enigma en serie maskiner med variationer i uppbygg­naden. En detaljerad beskrivning finns i Wiki­pedia. – En Enigma‑simulator finns på denna länk. En funge­rande Enigma‑maskin i original såldes i april 2015 på auktion i New York för 269 000 dollar. – Enigma är inte samma maskin som Lorenz SZ42 eller Geheimfernschreiber, G‑skrivaren, som knäcktes i Sverige av Arne Beurling;
  2. – teknik för att utföra beräkningar och analys på krypterade data. Beräkning­arna görs alltså på data som fortfarande är krypterade, se homomorfisk kryp­te­ring. Tekniken har utvecklats av Guy Zyskind (länk) från MIT och företagaren Oz Nathan. Den bygger på samma mate­ma­tiska metoder som används i bitcoin för att säker­ställa att samma digitala pengar inte används på två ställen samtidigt (dubbelspendering). – Enigma presen­te­rades sommaren 2015. En ingående beskriv­ning finns på enigma.media.mit.edu;
  3. – årlig konferens om it‑säkerhet, anordnad av Usenix med början 2016. – Se Usenix webbsidor.

Enigma betyder gåta och kommer av grekiska ainigma – dunkelt tal.

[it-historia] [it-säkerhet] [konferenser] [kryptering] [ändrad 16 april 2019]