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]