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 Nazi­tysk­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ör­drö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‑skriv­a­ren, 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 2 oktober 2018]