John von Neumann medal

IEEE John von Neumann medalvon Neumann‑medaljen – ett pris som delas ut årligen av IEEE för ”enastående prestationer inom datorvetenskapen”. Priset är har namn efter datorpionjären John von Neumann†. – Se IEEE:s webbsidor: länk (längst ner på sidan).

[utmärkelser] [ändrad 13 juni 2021]

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†.

[historiska 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 Turingmaskin mot­svarar ett modernt datorprogram, men när man talar om Turingmaskiner menar man ofta universella Turingmaskiner, som kan sägas mot­svara 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 Turingmaskin 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. – Turingmaskinen har en pappersremsa som matas fram och tillbaka genom ett läs- och skrivhuvud enligt bestämda regler. Det finns flera uppsättningar regler som kallas för tillstånd, och i reglerna ingår övergångar från ett tillstånd till ett annat. Skrivhuvudet kan läsa, radera och skriva tecken på remsan. Man programmerar Turingmaskinen med tecken på remsan, och Turingmaskinen matar sedan, enligt reglerna, remsan fram och tillbaka, läser, raderar och skriver samt växlar tillstånd tills den kommer till en regel som säger ”stopp”. Då stannar maskinen och lösningen på problemet 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 problem som kan lösas med ett modernt datorprogram också lösas av en motsvarande Turingmaskin, men naturligt­vis är det ogörligt att använda en maskin med pappersremsa. 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åndsmaskin. – 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 överskådlig, och blev allenarådande i datortekniken. – Professor Bernard Hodson (länk) i Kanada har utvecklat en modern programmeringsteknik baserad på Turings principer. – Matematikern 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

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 uppriktig eller oheder­lig, smitare och bluffare. – Spel­teori kan tillämpas på sällskaps­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 ekonomiskt beteende samt politisk och militär strategi. – Det klassiska exemplet på spel­teori är fångens dilemma. Ett annat är middagsätarens dilemma. Ett spel som ger intres­santa resultat är ultimatumspelet. Se också Nash‑jäm­vikt och allmän­ning­ens tragedi. – Spelteori används inom mark­nads­eko­no­misk analys, men teorin blev först känd som militärstrategiskt verktyg under det kalla kriget. Som upphovsmän räknas John von Neumann† och Oscar Morgen­stern (se Wikipedia). – Spelteore­tiska hypoteser har med it kunnat testas genom simulering i stor skala. Det anord­nas tävlingar där olika spelteoretiska strategier tävlar mot varandra. – På senare år har psyko­log­iska experi­ment i grupper visat att ekonomins spelteori inte alltid kan förutsäga mänsk­ligt bete­ende. Människor väljer inte alltid det alter­na­tiv som ger högst ekonomisk utdelning: de drar sig hellre ur en trans­aktion än de finner sig i att bli orättvist behandlade, även om de förlorar pengar på kuppen. Spelteoretiska försök visar också att människor har svårt att accep­tera folk som åker snålskjuts på andra, och därför vill avskräcka dem, även om det kostar. Självkänsla och rättvisa verkar vara viktig­are än ekonomisk vinst. – På engelska: game theory.

[psykologi] [spelteori] [ändrad 12 januari 2020]

von Neumann, John

(1903—1957) – ungersk matematiker och datorpionjär, från 1930 verksam i USA. – John von Neumann var en av de viktigaste teoretikerna bakom den moderna datortekniken. Han har gett namn åt von Neumann‑arkitekturen, som han tillämpade vid konstruktionen av datorn Edvac†. Han formulerade också teorier om cellautomater och självreplikerande maskiner – en idé som anknöt till upptäckten av DNA. – John von Neumann räknas också, tillsammans med Oscar Morgenstern† (se Wikipedia), som den viktigaste teoretikern bakom spelteorin. Spelteorin användes i USA som ett verktyg för strate­gisk analys under det kalla kriget, och John von Neumann var med i den ameri­kanska atomenergikommissionen som ledde utvecklingen av USA:s kärnvapenarsenal. De sista åren kom han till mötena i rullstol. Han och Henry Kissinger var förebilder till Peter Sellers roll­­figur Dr Strangelove i filmen med samma namn (se IMDb: länk). – Utmärkelsen John von Neumann medal är uppkallad efter honom.

[datorpionjärer] [it-historia] [john von neumann] [spelfilmer] [spelteori] [ändrad 31 januari 2021]

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 datorprogram, men de kan i princip köras med papper och penna. Man börjar med ett godtyckligt 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 granncell­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 upprepas 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 rutmönster eller på en obegränsad yta. Cellerna behöver inte vara rutor, utan kan ha andra former, och cellautomaten kan ha fler än två dimensioner. – Vissa enkla cellautomater 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 datorpionjä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 (1937–2020, se h2g2länk) program Game of life (se Wikipedia) från 1970 (se artikel i Scientific American). – Läs mer i Wikipedia.

[datorvetenskap] [programmering] [ändrad 25 augusti 2020]

 

von Neumann-arkitektur

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. 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† (SSEM) från 1948 och ameri­kan­ska IAS machine† från 1952, som blev mönsterbildande. – 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 program­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 (men aldrig förverkligades). Mer specifikt 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 Neumann‑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 Neumann‑flaskhalsen”, 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 flerkärniga processorer. Principen om gemen­samt minne har också ifråga­­satts, eftersom programspråk tydligt skiljer mellan data och instruktioner. – Efter­­som 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öjlig­heten.

[datorer] [it-historia] [ändrad 23 september 2021]