John von Neumann medal

IEEE John von Neumann medalvon Neumann-medaljen –– ett pris som delas ut årligen av IEEE för ”ena­stående prestationer inom datorvetenskapen”. Priset är upp­kallat efter dator­pionjären John von Neumann. – Se IEEE:s webb­sidor: länk.

[utmärkelser] [ändrad 7 september 2018]

IAS machine

en mönsterbildande tidig dator, byggd enligt John von Neumanns princip att programmen ska lagras i samma minne som de data som bearbetas. – IAS‑maskinen byggdes på Institute of advanced study, IAS, (ias.edu) i USA och invigdes 1952. Det var inte den första dator som byggdes enligt von Neumanns princip (SSEM var före), men IAS machine blev förebild för många tidiga datorer, bland annat BESK.

[datorer] [it-historia] [ändrad 2 oktober 2018]

Turingmaskin

En riktig Turingmaskin, byggd av amerikanen Mike Davis.
En riktig Turingmaskin, byggd av amerikanen Mike Davey.

en teoretisk dator som beskrevs 1936 av Alan Turing. Det var en ren tankekonstruktion. (1936 fanns inga datorer.) – En Turing­maskin mot­svarar ett modernt datorprogram, men när man talar om Turingmaskiner menar man ofta universella Turingmaskiner, som mot­svarar datorer. – Alan Turing beskrev maskinen i artikeln ”On computable numbers with an application to the Entscheidungsproblem” (länk). Artikeln handlade om ett matematiskt problem, stopproblemet, inte om datorer. Turing beskrev det som senare fick heta Turingmaskinen enbart för att göra ett matematiskt bevis åskådligt. Det var inte en beskrivning av något som Turing verkligen tänkte bygga. – Turing­­maskinen har en pappers­remsa som matas fram och tillbaka genom ett läs- och skrivhuvud enligt bestämda regler. Det finns flera upp­­sätt­ningar regler som kallas för tillstånd, och i reglerna ingår över­gångar från ett tillstånd till ett annat. Skriv­huvudet kan läsa, radera och skriva tecken på remsan. Man programmerar Turing­maskinen med tecken på remsan, och Turingmaskinen matar sedan, enligt reglerna, remsan fram och tillbaka, läser, raderar och skriver samt växlar till­stånd tills den kommer till en regel som säger ”stopp”. Då stannar maskinen och lösningen på pro­blemet kan avläsas på remsan. Detta är helt genomförbart, bortsett från de praktiska problemen med pappersremsan, pennan och radergummit. – I princip kan varje pro­blem som kan lösas med ett modernt dator­program också lösas av en mot­svarande Turing­maskin, men naturligt­vis är det ogörligt att använda en maskin med pappers­remsa. Man brukar därför simulera Turing­maskiner i datorer. (Se här.) Det är nämligen bra att öva sig på program för Turingmaskiner när man ska lära sig programmera. –– Se också finit tillstånds­maskin. –– Efter andra världskriget konstruerade Alan Turing en dator, ACE som till stor del baserades på de principer som Turing beskrev i sin artikel. – Turingmaskinen införde idén om lagrade program i datortekniken. Idén togs upp av John von Neumann i hans arkitektur för datorer, von Neumann-arkitekturen. Den är mindre sofistikerad än Turings modell, men mer över­skådlig, och blev allenarådande i dator­tekniken. –– Pro­fessor Bernard Hodson (länk) i Kanada har ut­vecklat en modern programmerings­teknik baserad på Turings principer. –Mate­matikern Stephen Wolfram arrangerade 2007 en tävling om Turingmaskiner, se här. – Mike Davey beskriver hur han byggde en riktig Turingmaskin (se bilden) i denna artikel. – Richard Ridel har byggt en Turingmaskin av trä, se denna video.

[it-historia] [matematik och logik] [ändrad 12 mars 2018]

spelteori

(game theory) –– teori om hur man väljer bästa handlingsal­ter­na­tivet gentemot en eller flera andra aktörer. Ofta handlar det om ifall man ska utgå ifrån att den andra parten är hederlig, hjälpsam och upp­riktig eller oheder­lig, smitare och bluffare. – Spel­teori kan tillämpas på säll­skaps­spel, där reglerna är fasta och antalet möj­lig­heter är begränsat, men teorin har redan från början främst gällt eko­nom­iskt be­te­ende samt politisk och militär strategi. – Det klassiska exemplet på spel­teori är fångens dilemma. Ett annat är middag­sätarens dilemma. Ett spel som ger intres­santa resultat är ulti­matum­spelet.– Se också Nash­jäm­vikt och all­män­ning­ens tragedi. – Spel­teori används inom mark­nads­eko­no­misk analys, men teorin blev först känd som militär­stra­te­giskt verktyg under det kalla kriget. Som upp­hovs­män räknas John von Neumann och Oscar Morgen­stern (se Wiki­pedia). – Spel­teore­tiska hypo­teser har med it kunnat testas genom simu­le­ring i stor skala. Det an­ord­nas tävlingar där olika spel­teore­tiska stra­te­gier tävlar mot varandra. – På senare år har psyko­log­iska experi­ment i grupper visat att ekonomins spel­teori inte alltid kan förutsäga mänsk­ligt bete­ende. Männi­skor väljer inte alltid det alter­na­tiv som ger högst ekono­misk utdel­ning: de drar sig hellre ur en trans­aktion än de finner sig i att bli orätt­vist behand­lade, även om de förlorar pengar på kuppen. Spel­teore­tiska försök visar också att männi­skor har svårt att accep­tera folk som åker snål­skjuts på andra, och därför vill av­skräcka dem, även om det kostar. Själv­känsla och rättvisa verkar vara viktig­are än ekono­misk vinst.

[psykologi] [spelteori] [ändrad 13 april 2017]

von Neumann, John

(1903——1957) –– ungersk matematiker och datorpionjär, från 1930 verksam i USA. – John von Neu­mann var en av de viktigaste teore­ti­kerna bakom den moderna dator­­tekniken. Han har gett namn åt von Neu­­mann‑arki­tek­turen, som han tillämpade vid kon­­struk­tionen av datorn Edvac. Han for­mu­le­rade också teorier om cell­­auto­mater och själv­repli­ke­rande maskiner –– en idé som an­knöt till upp­täckten av DNA. – John von Neu­mann räknas också, tillsammans med Oscar Morgen­­stern (se Wikipedia), som den vik­tig­aste teoretikern bakom spel­­­teorin. Spel­­­teorin an­vändes i USA som ett verk­tyg för stra­te­gisk analys under det kalla kriget, och John von Neu­mann var med i den ameri­kanska atom­­energi­­kom­mis­sionen som ledde utveck­lingen av USA:s kärn­vapen­arsenal. De sista åren kom han till mötena i rull­­stol. Han och Henry Kissinger var före­­bilder till Peter Sellers roll­­figur Dr Strangelove (se IMDb: länk). – Ut­­märkelsen John von Neu­mann medal är uppkallad efter honom.

[it-historia] [john von neumann] [personer] [spelfilmer] [spelteori] [ändrad 12 juni 2017]

cellautomat

(cellular automaton, plural cellular automata) –– mönster av rutor (celler) som förändras genom att varje ruta påverkar sina närmaste grannar. – Cellautomater realiseras oftast som dator­­program, men de kan i princip köras med papper och penna. Man börjar med ett god­tyckligt valt mönster – – man fyller i siffror eller andra värden i några av cellerna –– och ett antal regler. En regel kan till exempel säga att ”om summan av värdena i en cells grann­cell­er är över 10, ändra värdet i cellen till 1”. Man tillämpar reglerna på alla rutor, och börjar sedan om på nytt med samma regler, så att nya mönster uppstår. Detta upp­­repas tills mönstret inte förändras längre. Det kan också sluta med en slinga (ett antal mönster upp­repas om och om igen). I sällsynta fall tycks mönstret förändras i oänd­lig­het. – Cellautomater kan köras i ett begränsat rut­mönster eller på en obegränsad yta. Cellerna behöver inte vara rutor, utan kan ha andra former, och cell­auto­maten kan ha fler än två dimensioner. –– Vissa enkla cell­automater upp­visar ett oväntat komplicerat beteende (emergent beteende). Det beror på vilka värden man har i utgångs­läget och vilka regler cellautomaten följer. – En cell­automat är ett slags dator (en universell Turingmaskin) och kan i princip programmeras för att lösa alla problem som kan lösas med en dator. –– John von Neumann hittade på cellautomater på 1940‑talet. Hans mål var att hitta en mekanism för att bygga strukturer som kan göra kopior av sig själva. Idén med cellautomater har vidareutvecklats av dator­pionjären Konrad Zuse i boken Rechnender Raum (Calculating space), från 1969 och av matematikern Stephen Wolfram i boken A new kind of science från 2002. Den mest kända tillämpningen är John Horton Conways (se h2g2) program Game of life (se Wikipedia) från 1970 (se artikel i Scientific American). – Läs mer i Wikipedia.

[datorvetenskap] [programmering] [ändrad 7 juni 2017]

 

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]