ö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 heltäckande och motsägelsefria. Med heltäckande menas att regelsystemet kan tillämpas på alla påståenden som kan formuleras 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å uppenbarligen är sanna. Detta bevisade han i artikeln ”Über formal unentscheidbare Sätze der Principia Mathematica und Verwandte System” (engelsk översättning 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 motsägelsefritt.
– Se också Entscheidungsproblem. – 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 (Incompleteness: The proof and paradox of Kurt Gödel, 2005) av Rebecca Goldstein(webbplats).
(1903—1995) – amerikansk matematiker. – Alonzo Church bevisade 1936 i artikeln ”A note on the Entscheidungsproblem” (se avgörbarhetsproblemet) att det finns matematiska problem som det inte går att lösa med mekaniska metoder. Det var samma sak som Churchs studiekamrat Alan Turing† bevisade senare samma år i sin uppsats 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 noggrann men fantasilös människa med papper och penna (givet tillräckligt med tid) 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 evighet 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 fortsätter i all evighet. – En artikel på engelska om vanliga missuppfattningar av Church‑Turings hypotes finns här.
den uppbyggnad av datorer som har varit standard sedan 1940‑talet. – von Neumann‑arkitektur innebär att data och program lagras i samma minne – sammanhanget avgör vad som är vad. Arkitekturen är uppkallad efter matematikern John von Neumann†, men andra forskare var med och utvecklade principerna. De första datorerna som tillämpade von Neumann‑arkitekturen var brittiska Small-scale experimental machine†(SSEM) från 1948 och amerikanska IAS machine† från 1952, som blev mönsterbildande. – von Neumann kände till Alan Turings† idéer, men han ville göra ett datorsystem som var mindre intellektuellt krävande för programmerarna. Principerna 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 huvuddelar, nämligen (med moderna termer) processor, 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 (men aldrig förverkligades). Mer specifikt för von Neumann‑arkitekturen är att den:
– har ett gemensamt minne för programinstruktioner och data. Vad som är vad avgörs av sammanhanget. Ett annat kännetecken för von Neumann‑arkitekturen är:
– att beräkningarna sker sekventiellt. Programinstruktionerna verkstä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 Neumann‑flaskhalsen”, den sekventiella 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 Harvardarkitekturen. John von Neumann insåg fördelarna med parallell databehandling, men han ansåg att det skulle bli för besvärligt att genomföra. Numera är parallellism vanligt, eftersom datorer ofta har flera processorer, eller flerkärniga processorer. Principen om gemensamt minne har också ifrågasatts, eftersom programspråk tydligt skiljer mellan data och instruktioner. – Eftersom von Neumann‑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öjligheten.
– en portabel krypterings‑maskin som under andra världskriget användes av Nazitysklands trupper i fält och till sjöss. – Enigmas kryptering dekrypterades med någon timmes fördröjning av brittiska matematiker och kryptoexperter under ledning av Alan Turing† i Bletchley Park. Men den förste som knäckte Enigmas kryptering var den polskakryptologenMarian Rejewski i december 1932. Han hade inte tillgång till någon Enigmamaskin, bara till dokumentation som den franska underrättelsetjänsten hade kommit över. Strax före andra världskrigets utbrott 1939 delade Rejewski med sig av sina kunskaper med Frankrike och Storbritannien. Britterna satsade då, under ledning av Turing, på att utveckla ett system för att dekryptera Enigmameddelanden mekaniskt i stället för med papper och penna. Detta underlättades av att de brittiska styrkorna när de evakuerade Nordnorge i juni 1940 fick med sig tre intakta Enigmamaskiner. Britterna kunde därför snart tolka tyskarnas krypterade radiotelegrafi. 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 uppbyggnaden. En detaljerad beskrivning finns i Wikipedia. – En Enigma‑simulator finns på ciphermachinesandcryptology…. En fungerande 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†;
– en teknik för att utföra beräkningar och analys på krypterade data. Beräkningarna görs alltså på data som fortfarande är krypterade, se homomorfisk kryptering. Tekniken har utvecklats av Guy Zyskind(länk) från MIT och företagaren Oz Nathan. Den bygger på samma matematiska metoder som används i bitcoin för att säkerställa att samma digitala peng inte används på två ställen samtidigt (dubbelspendering). – Enigma presenterades sommaren 2015. En ingående beskrivning finns på enigma.media.mit.edu;
