qr code

Från kulramar till datorer

Från kulramar till datorer

Att behärska ett ämne innebär att man i viss mån känner till dess historia. Liksom sir Isaac Newton en gång skrev om sina upptäckter[1]

If I have seen further it is by standing on the shoulders of giants.

är en modern dator resultatet av ackumulerad mänsklig kunskap som utvecklats under en längre tidsrymd.

Datavetenskapens historia inbegriper såväl matematiska teorier som teknikutveckling. Vi kommer här endast att ta upp teoretiska aspekter av datavenskapens historia med tyngdpunkt på matematik och algoritmteori.

Att känna till ett ämnes historia inbegriper också kännedom om personer som haft en avgörande betydelse för ämnets utveckling. Här presenteras ett urval av sådana personer, återigen med tyngdpunkt på de teoretiska aspekterna.

Beräkningsmatematik

I modern tid används en dator som en universalmaskin med vilken man kan utföra komplicerade beräkningar, kommunicera, dela och inhämta information, spela spel, mm. Inte minst används en dator ofta som en avancerad skrivmaskin. När den moderna elektroniska datorn utvecklades under den första hälften av 1900-talet, var det dock inte för att någon behövde en bättre skrivmaskin. Datorn utvecklades till en början som en avancerad beräkningsmaskin och därför är beräkningsmatematikens historia en viktig del av datorns historia.

Ända sedan antiken har människor använt räkneredskap såsom kulramar för att utföra beräkningar. Kulramar av olika slag används än idag i stora delar av Asien. Med astronomins utveckling under 1500- och 1600-talet växte behovet att utföra matematiska beräkningar med mycket stora tal. Det var speciellt svårt att multiplicera och dividera stora tal. På 1400-talet ansågs multiplikation vara så pass svårt att en svensk matematikprofessor gav följande råd om matematikstudier[2]:

Om den unge mannens matematikstudier skulle inskränkas till addition och subtraktion kunde han möjligen få denna undervisning vid ett tyskt universitet, men multiplikation och division var högt utvecklad i Italien, som var det enda land där en sådan högre utbildning fanns att tillgå.

Svårigheter med multiplikation var ett incitament för att utveckla beräkningskonsten.

John Napier

En person som kom att ha mycket stor betydelse för beräkningskonsten var John Napier (1550 - 1617). Napier var en skotsk godsägare och hobbymatematiker som bland annat uppfann ett räkneredskap kallat Napiers ben. Napiers räkneredskap bestod av ett antal stavar gjorda av ben med siffror på. Med Napiers ben fick man hjälp med att multiplicera eller dividera och den enda räkneoperation som användaren själv behövde använda var addition. Napier använde en sedan tidigare känd metod för multiplikation kallad multiplikation med nätmetoden.

Exempel 1 Multiplikation med nätmetoden

För att multiplicera \(237\) och \(42\) börjar vi med att göra ett rutnät där varje ruta delas av en diagonal.

nätmetoden steg 1

Därefter multiplicerar vi två siffror i taget och placerar tiotalet snett ovanför diagonalen och entalet snett under diagonalen i motsvarande ruta. Dessa resultat var markerade på stavarna i Napiers ben. Multiplikationerna, de som var så svåra, var alltså redan utförda.

nätmetoden steg 2

För att få fram produkten adderar vi tal längs diagonalerna med början längst ned till höger. Eventuella minnessiffror skrivs i fältet närmast till vänster. Vi fortsätter på samma sätt uppåt och åt vänster längs diagonalerna.

nätmetoden steg 3

För att avläsa resultatet bildar vi det tal vars siffror står utanför rutnätet i riktningen neråt och sedan åt höger.

nätmetoden steg 4

Även om Napiers ben förenklade den mödosamma uppgiften att multiplicera så var detta räknedon inte Napiers stora bidrag till räknekonsten. Napiers stora bidrag till räknekonsten och matematiken var att han uppfann logaritmen[3].

Såsom matematik lärs ut idag, börjar man med att lära sig begreppet upphöjt till som ett förenklat skrivsätt för upprepad multiplikation, exempelvis är \( 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 2^5\), vilket utläses två upphöjt till fem. I uttrycket \(2^5\) är \(2\) bas och \(5\) exponent, själva uttrycket är en potens. Säg att vi velat ta reda på vilken exponent som skulle användas för att skriva \(32\) som en potens med basen \(2\), då hade vi kunnat använda logaritmen i basen två av \(32\) dvs vi hade kunnat använda att \(\log_2 32 = 5 \). Informellt kan man se det som att logaritmen är den okända exponenten då en bas är given.

Logaritmen av talet \(a\) i basen \(b\) skrivs \(\log_b a\), exempelvis är:

\[ \begin{align} \log_{2}32 &= 5 \;\mbox{ eftersom } 2^5 = 32 \\ \log_{5} 125 &= 3 \;\mbox{ eftersom } 5^{3} = 125 \\ \log_{10} 10\,000 &= 4 \;\mbox{ eftersom } 10^{4} = 10\,000 \end{align} \]

När Napier uppfann logaritmen var operationen upphöjt till ännu inte känd. Det var inte för att hantera okända exponenter som logaritmen uppfanns utan för att förenkla multiplikation och division. Med användning av en logaritmtabell kunde en multiplikation utföras som en addition och en division som en subtraktion. Med modern notation kan vi beskriva dessa förfaranden med hjälp av två logaritmlagar. Om \(b\) är en given bas och om \(x\) och \(y\) är givna tal sådana att

\[ \begin{align} x = b^m &\iff \log_b x = m \\ y = b^n &\iff \log_b y = n \end{align} \]

så följer de två logaritmlagarna ur motsvarande potenslagar.

Potenslag Logaritmlag
\(b^m\cdot b^n = b^{m+n}\) \(\log_b(x\cdot y) = \log_b x + \log_b y\)
\( \dfrac{b^m}{b^n} = b^{m-n}\) \( \log_b\left( \dfrac{x}{y} \right) = \log_b x - \log_b y \)

Att multiplicera potenser motsvaras alltså av att addera logaritmer. Eftersom alla tal (utom noll) kan skrivas på potensform, kan en multiplikation utföras som en addition av logaritmer.

Exempel 2 Multiplikation med hjälp av logaritmtabell

Vi tänker oss att vi har tillgång till en logaritmtabell med tiologaritmer och ska beräkna produkten av \(5,72\) och \(3,01\). Vi börjar med att slå upp logaritmerna i tabellen:

\[ \begin{align} \log_{10} 5,72 &= 0,75740 \\ \log_{10} 3,01 &= 0,47857 \end{align} \]

Vi adderar logaritmerna och får att

\[ 0,7574 + 0,47857 = 1,23597.\]

Med hjälp av logaritmtabellen kan vi nu ta reda på att

\[ \log_{10} 17,2175 = 1,23597.\]

Alltså är

\[ 5,72\cdot 3,01 \approx 17,22\]

Den enda räkneoperation vi behövt utföra är addition!

Napier lanserade sina idéer med boken Mirifici logarithmorum canonis descriptio som kom ut år 1614. Det hade tagit honom 20 år att färdigställa boken och en stor del bestod av en logaritmtabell.

Räknestickan

Strax efter publiceringen av Napiers logaritmtabell, publicerade den engelske matematikern Henry Briggs (1561 - 1630) en logaritmtabell med basen tio. Några år senare, år 1622, uppfann den engelske matematikern William Oughtred (1574 – 1660) räknestickan vilken använde sig av logaritmiska skalor.

En räknesticka består av två eller tre linjaler sådana att en av linjalerna kan förskjutas i sidled. För att förstå hur en räknesticka fungerar kan det vara illustrativt att tänka sig hur man adderar med hjälp av två linjaler.

Exempel 3 Addition med linjaler

I vårt tankeexperiment kan den övre blå linjalen förskjutas i sidled. Det finns också en markör med vilken man kan avläsa resultatet.

För att addera \(4,1\) och \(3,6\) placeras den övre linjalen så att \(0\) står mot talet \(4,1\) på den nedre linjalen. Markören placeras sedan vid den övre linjalens gradering \(3,6\) och resultatet \(7,2\) kan avläsas på den nedre linjalen.

vanliga linjaler

En enkel räknesticka för multiplikation består av två linjaler som är graderade med logaritmiska skalor.

Exempel 4 Multiplikation med räknesticka

Logaritmen av \(1\) är \(0\) (eftersom \(10^0 = 1\) ). Ettan på den logaritmiska linjalen motsvarar därför talet noll.

För att multiplicera \(3,1\) och \(2,8\) placeras den övre linjalen så att \(1\) står mot \(3,1\) på den nedre linjalen. Markören placeras vid den övre linjalens \(2,8\) och resultatet \(8,7\) kan avläsas på den nedre linjalen.

logaritmiska linjaler 1

Vi har använt att

\[ \log 3,1 + \log 2,8 \approx \log 8.7 \iff \log(3,1\cdot 2,8) \approx \log 8,7 \iff 3,1\cdot 2,8 \approx 8,7. \]

Om vi istället hade velat multiplicera \(3,1\) med \(6,2\) hamnar resultatet för långt åt höger på räknestickan. Vi tänker oss då att graderingen på den övre linjalen delas med \(10\) så att graderingen \(10\) motsvarar talet \(1\) och graderingen \(6,2\) motsvarar talet \(0,62\). Vi utför multiplikationen \(3,1\cdot 0,62\). Efteråt multiplicerar vi resultatet med \(10\) för att få rätt svar.

För att multiplicera \(3,1\) med \(0,62\) placerar vi den övre linjalens \(10\) vid den nedre linjalens \(3,1\). Markören placeras sedan vid den övre linjalens \(6,2\) och resultatet \(1,9\) avläses på den nedre linjalen. Resultatet är \(10\cdot 1,9=19\) alltså är \(3,1\cdot 6,2\approx 19\).

logaritmiska linjaler 2

Räknestickan användes i skolans matematikundervisning fram till 1970-talet, därefter började den successivt att ersättes av miniräknaren. Idén om en räknemaskin föddes dock långt innan miniräknaren uppfanns och innan det fanns elektronik. De första räknemaskinerna var inte elektroniska utan mekaniska.

Blaise Pascal

Blaise Pascal (1623 - 1662) var en fransk matematiker och fysiker som i skolans värld mest är känd för att vara mannen bakom enheten Pa (används för att mäta tryck) och för att han kommit på Pascals triangel.

Pascals triangel
Pascals triangel

Pascal började redan som tonåring att konstruera mekaniska räknemaskiner som byggde på kugghjulsprincipen. Han var den förste som konstruerade en funktionsduglig mekanisk räknemaskin kallad Pascaline[4]. En Pascaline hade en mekanism för att överföra minnessiffror och den kunde addera tal med högst fem siffror. Räknemaskinen var gjord så att den även skulle kunna utföra en subtraktion men denna operation fungerade sämre. Det byggdes totalt sett cirka 50 stycken räknemaskiner av Pascals modell.

Gottfried Wilhelm von Leibniz

Den tyske matematikern Gottfried Wilhelm von Leibniz (1646 - 1716) är kanske mest känd för att han samtidigt och oberoende av sir Isac Newton utvecklade infinitesimalkalkylen. Flera av de beteckningar som används inom matematisk analys idag, är beteckningar som Leibniz först använde; exempelvis införde Leibniz beteckningarna \(dy\) och \(dx\) för infinitesimala förändringar i \(x\)- och \(y\)-led och beteckningen \(\int_a^b f(x) dx \) för integral.

Leibniz förbättrade också Pascals räknemaskin och konstruerade, med hjälp av en urmakare, en mekanisk räknemaskin som kunde hantera alla de fyra räknesätten. Multiplikation utfördes som upprepade additioner och division som upprepade subtraktioner. Leibniz var visionär och insåg tidigt vilken enorm nytta vi skulle kunna ha av att låta maskiner utföra tidsödande beräkningar. År 1658 skrev han[5]:

For it is unworthy of excellent men to lose hours like slaves in the labor of calculation, which could be safely relegated to anyone else if machines were used.

Även om Leibniz mekaniska maskin inte använde sig av binära tal, insåg Leibniz att räknemaskiner i framtiden skulle kunna dra stor nytta av att använda sig av det binära talsystemet. Det binära talsystem som idag alla datorer använder sig av, beskrevs för första gången i artikeln Explication de l'Arithmétique Binaire från år 1709 av Leibniz.

Algoritmteori

Precis som binära tal uppfanns långt innan det fanns datorer, användes algoritmer långt innan de började användes inom datavetenskap. I Euklides Elementa från ca 300 f.Kr. beskrev exempelvis Euklides en metod för att beräkna den största gemensamma delaren till två tal. På den tiden användes inte ordet algoritm men metoden har senare kommit att kallas för Euklides algoritm. En variant av Euklides algoritm används för RSA-kryptering.

Ordet algoritm är den latinska versionen av namnet al-Khwarizmi. Muhammad ibn Musa al-Khwarizmi (780-850) var en persisk matematiker som även har givit namn åt ordet algebra. I boken Hisab al-jabr w'al-muqabalah beskrev al-Khwarizimi hur man löser ekvationer. Ordet algebra är en latinsk variant av ordet al-jabr. Idag förknippar vi algebra med bokstavsräkning och det kan därför vara intressant att nämna att al-Khwarizimi själv inte använde bokstäver som beteckningar för tal, han beskrev däremot metoder för hur man bestämmer algebraiska lösningar. Just detta att han beskrev metoder, eller "hur man gör", förlänade honom alltså äran att få namnge ordet algoritm.

Leonhard Euler

Den schweiziska matematikern Leonhard Euler (1707-1783) räknas som en av de största matematikerna genom tiderna. Han är även en av de mest produktiva matematikerna och det finns en uppsjö av matematiska begrepp uppkallade efter honom[6]. Det mesta av det Euler gjorde ligger på en för hög nivå för grundskolematematik men två saker bör nämnas i samband med programmering, Eulers stegmetod och problemet med broarna i Königsberg.

Eulers stegmetod

Eulers stegmetod är en metod för att lösa differentialekvationer numeriskt.

Med vanlig ekvationslösning försöker man bestämma ett eller flera okända tal. När man löser en differentialekvation är man inte ute efter att bestämma något okänt tal, utan en okänd funktion. Vid vanlig ekvationslösning utgår man från något samband som gäller för det okända talet. Vid lösning av en differentialekvation utgår man ifrån något samband som gäller för hur funktionen förändras.

När det gäller vanlig ekvationslösning kan vissa ekvationer lösas med algebraiska metoder, dvs för hand med penna och papper. Det finns också ekvationer som bara kan lösas med numeriska metoder. På samma sätt finns det differentialekvationer med kända lösningsmetoder vilka kan lösas för hand. De allra flesta differentialekvationer saknar emellertid kända lösningsmetoder och kan bara hanteras med hjälp av numeriska metoder. Det var en sådan numerisk metod Euler beskrev.

Detta att man kan observera hur någonting förändras och att man vill kunna beskriva skeendet som en funktion, är en vanligt förekommande situation inom fysiken. Genom att lösa en differentialekvation kan man exempelvis beskriva den bana en kastad boll har under påverkan av jordens gravitationsfält, detta går att göra med algebraiska metoder. En mer komplicerad situation på samma tema är att beskriva en komets bana genom rymden, i vilket fall man måste räkna på hur alla närliggande himlakroppar påverkar varandra. Kometens bana kan simuleras med hjälp av numeriska metoder och programmering.

Vi ska demonstrera hur Eulers stegmetod fungerar. För att du ska kunna förstå demonstration krävs det att du kan något om matematisk analys. I annat fall kan du hoppa över demonstrationen och bara konstatera att den programmering av rörelse som vi ska göra senare i kursen, hänger ihop med en numerisk metod som uppfanns på 1700-talet, långt innan datorn uppfanns.

Demonstration av Eulers stegmetod

Situationen är den att \(y\) är en funktion av \(x\). Formeln för hur \(y\) kan skrivas uttryckt i \(x\) antar vi är okänd, däremot vet vi överallt hur mycket \(y\) förändras som en funktion av \(x\). Förändringen betecknar vi som \(y'\), derivatan. Derivatan är en funktion av \(x\), en funktion som vi alltså känner till:

\[ y' = - x\]

För att rita upp funktionens graf, startar vi i någon punkt och går längs derivatans riktning ett litet steg. För att ta nästa steg, använder vi derivatan för det nya \(x\)-värdet, osv. Om vi på detta vis vill gå ett antal steg mellan punkter \( (x_0, y_0), (x_1, y_1), (x_2, y_2) \ldots \) får vi \(x\)-värdena genom att i varje steg använda funktionen

\[x_{i+1} = x_i + steg \]

och \(y\)-värdena genom att i varje steg använda funktionen

\[y_{i+1} = y_i + steg \cdot \mbox{förändringen} = y_i + steg \cdot (-x_i) \]

eftersom förändringen ges av vårt uttryck för derivatan.

Det enda vi nu behöver för att rita upp flera steg är någon startpunkt \( (x_0, y_0) \).

Ändra steglängden. Dra i den stora blå punkten.

I GeoGebra-demonstrationen är den stora blå punkten startpunkt. Den svarta grafen visar hur funktionen ser ut om man löser differentialekvationen med algebraiska metoder ‐ hur funktionen egentligen ser ut. De streckade linjerna (tangenterna) visar derivatan riktning.

Vi kommer inte att hantera funktioner \(y\) av \(x\) på detta vis i denna kurs, däremot kommer vi att modellera rörelse i koordinatplan eftersom detta är synnerligen vanligt inom dataspel. Våra \(y\)-värden kommer inte att vara funktioner av \(x\), istället kommer både \(x\)-värdena och \(y\)-värdena att vara funktioner av tiden \(t\). För att få till en rörelse kommer vi i varje tidssteg att förändra \(x\)- och \(y\)-värdena med samma princip som används i Eulers stegmetod.

Broarna i Königsberg[7]

På 1700-talet var Königsberg (numera Kaliningrad) huvudstad i Ostpreussen. Genom Königsberg flöt floden Pregel vilken delade upp staden i fyra landområden. Det fanns sju broar över Pregel. (I dagens Kaliningrad finns det andra broar, bl.a. för att vissa av de gamla broarna bombades under andra världskriget.)

broarna i Königsberg
Broarna i Königsberg såsom Euler ritade dem.

På söndagarna brukade invånarna i Königsberg gå på söndagspromenad över broarna och diskutera huruvida man kunde besöka alla landområden och komma tillbaka till startpunkten genom att gå över varje bro exakt en gång. Denna diskussion blev känd utanför Königsberg, så pass känd att borgmästaren i Danzig (numrera Gdansk) slutligen skrev ett brev till Euler som var verksam vid vetenskapsakademin i Sankt Petersburg och bad honom begrunda problemet. Borgmästare tänkte att Euler kanske kunde hitta en väg över broarna eller bevisa att en sådan väg inte fanns. Euler blev till en början förvånad över att han ens fick frågan eftersom detta problem dels inte hade med matematik att göra och dels var ett så pass enkelt problem att vem som helst kunde lösa det. Euler måste dock ha blivit förundrad över den allmänna problemställningen eftersom han till slut bestämde sig för att lösa problemet i det allmänna fallet, det vill säga i fallet där det finns ett godtyckligt antal landområden och ett godtyckligt antal broar. På så vis lade han (som i förbifarten) grunden för grafteorin. Broarna i Königsberg brukar räknas som det första grafteoretiska problemet.

I Eulers beskrivning av problemet med broarna i Königsberg, började han med att beskriva varför problemet överhuvudtaget kunde vara intressant, att det kanske kunde vara en ny sorts matematik vars relevans ännu var okänd.

In addition to that branch of geometry which is concerned with distances, and which has always received the greatest attention, there is another branch, hitherto almost unknown, which Leibniz first mentioned, calling it the geometry of position [Geometriam situs]. This branch is concerned only with the determination of position and its properties; it does not involve distances, nor calculations made with them. It has not yet been satisfactorily determined what kinds of problem are relevant to this geometry of position, or what methods should be used in solving them.

Hur löste då Euler problemet? Vi börjar med att ge en kort beskrivning av hur Euler gjorde i det allmänna fallet:

Först betraktar vi landområden som inte är startpunkt eller slutpunkt. Varje gång man kommer till ett sådant landområde måste man också kunna lämna det. De broar som gränsar till ett sådant område måste därför kunna paras ihop. Antalet broar som gränsar till ett sådant område är alltså ett jämnt tal.

Sedan betraktar vi landområden som är startpunkt eller slutpunkt. Euler delade upp detta i två fall.

  1. Vi börjar med fallet att vi inte återvänder till samma landområden på slutet. För startområdet måste vi först kunna lämna området, därefter måste varje bro som användas till att gå in i området kunna paras ihop med en annan bro som leder ut. Alltså måste antalet broar som gränsar till startområdet vara udda. Samma sak gäller för slutområdet.
  2. Sedan antar vi att vi slutar i samma område som vi startade ifrån. Nu gäller återigen att för varje bro som används för att lämna startområdet måste det finnas en bro som leder tillbaka in. Antalet broar som gränsar till startområdet måste därför vara jämnt.

I fallet med broarna i Königsberg, har alla landområden ett udda antal angränsande broar, därför går det inte att göra den söndagspromenad som invånarna i Königsberg ville göra.

Euler använde själv inte noder och bågar, dessa är en senare uppfinning. Inom grafteori beskrivs problemet med broarna i Königsberg av en graf. För att göra en graf använder vi samma beteckningar som Euler. Noderna är landområden (A, B, C, D). Bågarna är broar (a, b, c, d, e, f, g).

broarna i Königsberg som graf
Broarna i Königsberg som graf.

Inom grafteorin kallas en väg över noder och bågar sådan att varje båge besöks exakt en gång för en Eulerväg. Om vägen dessutom börjar och slutar i samma nod kallas den för en Eulercykel. Det Euler visade var med modern terminologi att:

  • En graf innehåller en Eulercykel om och endast om antalet bågar som utgår ifrån en nod är ett jämnt tal för varje nod.
  • En graf innehåller en Eulerväg om och endast om antalet bågar som utgår ifrån en nod är ett jämnt tal för varje nod utom eventuellt två noder (startnoden och slutnoden).

Om man kan rita upp en graf utan att lyfta pennan från pappret och utan att dra pennan längs samma kurva mer än en gång, innehåller grafen en Eulerväg.

George Boole

George Boole (1815 - 1864) var en engelsk matematiker och logiker som blivit känd för att han uppfann den så kallade booleska algebran. Inom boolesk algebra används talen noll och ett som logiska värden, noll står för falsk och ett för sann. I modern tid brukar man inte tala om "logiska värden" inom datavetenskap utan kallar istället dessa för booleska, eftersom allting internt i en dator representeras av binära tal.

Sanningsvärdestabeller inom boolesk algebra ser ut som inom logiken, fast med sann och falsk utbytta till ett och noll.

Booleskt och.
\(p\) \(q\) \( p \land q\)
1 1 1
1 0 0
0 1 0
0 0 0
Booleskt eller.
\(p\) \(q\) \( p \lor q\)
1 1 1
1 0 1
0 1 1
0 0 0
Booleskt inte.
\(p\) \( \lnot p\)
1 0
0 1

Inom boolesk algebra kan man åstadkomma de tre logiska operationerna på följande sätt

  • \(p \land q = p\cdot q \)
  • \(p \lor q = p + q - p\cdot q \)
  • \(\lnot p = 1-p \)

och sedan visa att

  1. \( \lnot (p \land q ) = \lnot p \lor \lnot q \)
  2. \( \lnot (p \lor q ) = \lnot p \land \lnot q \)

Vi visar likhet 1:

\[ \begin{align} \mbox{VL} &= \lnot (p \land q ) = \lnot (p\cdot q ) = 1-p\cdot q \\ \mbox{HL} &= \lnot p \lor \lnot q \\ &= (1-p) \lor (1-q) \\ &= 1-p + 1-q - (1-p)(1-q) \\ &= 2-p-q - (1 - p - q + pq) \\ &= 1-pq \end{align} \]

Eftersom vänsterledet är lika med högerledet måste likhet 1. gälla. Likhet 2. visas på liknande sätt. Likheterna motsvaras inom mängdläran av de Morgans lagar, dvs

  1. \( \overline{A \cup B} = \overline{A} \cap \overline{B} \)
  2. \( \overline{A \cap B} = \overline{A} \cup \overline{B} \)

där \( \cup \) ger unionen, \( \cap \) snittet och \( \overline{A} \) är komplementet av \(A\).

Venn-diagram
Union, snitt och komplement med Venn-diagram.

Idén om en dator föds

Under 1700-talet framställdes de första maskinerna som kom att bidra till den industriella revolutionen, exempelvis James Watts ångmaskin och spinnmaskinen Spinning Jenny i England. I Frankrike uppfanns den så kallade Jacquardvävstolen för att på mekanisk väg väva tyg. För att kunna väva olika sorters mönster användes så kallade hålkort vilka angav vilket mönster som skulle vävas.

Hålkort till en Jacquardvävstol
Hålkort till en Jacquardvävstol[8]

Under samma tidsperiod användes en allt större mängd trigonometriska tabeller och logaritmtabeller. Dessa tabeller sammanställdes av människor. Det engelska ordet computer började användes redan på 1600-talet för att beteckna människor som utförde beräkningar[9].

Det var mot denna bakgrund idén om en mekanisk dator föddes.

Charles Babbage

Charles Babbage (1791 -1871) brukar räknas som datorns upphovsman. Babbage var verksam vid universitetet i Cambridge där han innehade samma prestigefyllda professur som exempelvis sir Isaac Newton och den nyligen avlidne Stephen Hawking, det vill säga professuren Lucasian Professor of Mathematics.

De matematiska tabeller som användes på den tiden var framräknade av människor och innehöll därför ganska många fel. För att kunna använda framräknade värden i tabeller fick Babbage lägga tid på att verifiera värden, vilket han efterhand beskrev som[10]:

After a time many discrepancies occurred, and at one point these discordances were so numerous that I exclaimed, “I wish to God these calculations had been executed by steam"

Babbage kom senare att konstruera en mekanisk maskin, hans så kallade differensmaskin, vilken skulle producera matematiska tabeller genom att interpolera värden för matematiska funktioner. De som skulle implementera Babbages konstruktion i England, lyckades inte få differensmaskinen att fungera men idéerna spreds över Europa och i Stockholm byggde Per Georg Scheutz tillsammans med sin son en fungerande maskin som visades upp på världsutställningen i Paris år 1855, där den belönades med guldmedalj.

Under konstruktionen av differensmaskinen fick Babbage idén att konstruera en mer allmän maskin, en maskin som inte bara kunde räkna utan också skulle kunna programmeras. Babbage kallade denna maskin för den analytiska maskinen. I tidens anda hämtade Babbage idéer från ångmaskiner och vävmaskiner. Den analytiska maskinen drevs av ånga och den tog emot indata med hjälp av hålkort och producerade nya hålkort som utdata. Maskinen kunde utföra aritmetiska operationer och utöver att utföra en sekvens av instruktioner i tur och ordning, kunde man instruera maskinen att utföra olika instruktioner beroende på villkor ‐ som en villkorssats.

Även om enstaka delar av Babbages analytiska maskin byggdes redan under hans livstid, byggdes aldrig en hel maskin, vare sig under hans livstid eller efteråt. Trots att den analytiska maskinen bara var en mycket noggrant beskriven idé, brukar den räknas som den första datorn.

Ada Lovelace

Under de år Babbage konstruerade den analytiska maskinen, kom han i kontakt med Ada Lovelace (1815 - 1852) som var dotter till den engelske poeten lord Byron. Lord Byron och Lovelaces mamma var skilda och lord Byron levde ett extravagant och skandalomsusat aristokratliv på resande fot i Europa. För att undvika att dottern drabbades av samma galenskaper som sin far, lär Lovelaces mamma ha sett till att hon från tidig ålder fick undervisning i matematik, vilken var mycket ovanligt på den tiden ‐ matematik ansågs inte vara ett lämpligt ämne för flickor. Lovelace undervisades bl.a. av Augustus de Morgan, känd för de Morgans lagar i mängdläran. Undervisningen skedde med hjälp av en brevkorrespondens vilken är bevarad för eftervärlden[11].

Vid ett tillfälle höll Babbage en föreläsning i Italien vilken transkriberades till italienska av en italiensk ingenjör. Transkriberingen publicerades och Ada Lovelace översatte transkriberingen till engelska. På uppmaning av Babbage skrev hon samtidigt egna kommentarer om den analytiska maskinen. Lovelaces kommentarer blev i sig ett större arbete än den ursprungliga transkriberingen och de innehöll exempel på algoritmer som skulle kunna programmeras av den analytiska maskinen. Lovelace skrev också att maskinen skulle kunna göra så mycket mer än att bara hantera tal och räkningar, med hjälp av logiska operationer skulle den kunna utföra många olika komplexa uppgifter, exempelvis komponera musik.

I Lovelaces kommentarer fanns bland annat en beskrivning av hur man beräknade så kallade Bernoulli tal med hjälp av den analytiska maskinen. Hennes beskrivning publicerades år 1843. Detta var första gången en beskrivning av ett datorprogram publicerades, Lovelaces beskrivning räknas därför som det första datorprogrammet och Lovelace själv räknas som den första programmeraren, trots att det skulle dröja länge innan det byggdes en maskin som faktiskt kunde programmeras.

Alan Turing

Alan Turing (1912 - 1954) var verksam under samma tidsperiod som de första programmerbara datorerna konstruerades. Turing var teoretiker och hans teorier har kommit att definiera vad som menas med en dator.

Efter att ha disputerat i matematik vid universitetet i Cambridge, gav sig Turing på ett problem om beräkningar. År 1931 hade Kurt Gödel publicerat den så kallade ofullständighetssatsen, vilken i korthet bevisade att det i alla axiomatiska system fanns sanningar som inte kunde bevisas inom systemet[12]. I Gödels anda gav sig Turing på att bevisa att det fanns problem som inte kunde lösas med hjälp av en noggrant beskriven algoritm, ens om man använde av en maskin. Eftersom det ännu inte hade byggts en fungerande dator fanns det ingen vedertagen definition av vad en dator var eller vad en sådan kunde göra. Turing började därför med att definiera vad han menade med en maskin. Turings definition var en matematisk modell beskriven med en mycket enkel mekanik, inte en riktig maskin. Hans beskrivning var dock så generell att framtida datorer kom att jämföras med Turings maskin, modellen kunde i princip användas på alla algoritmer. Turing kallade maskinen för "automatic machine" eller i korthet "a-machine", numera kallas maskinen för Turingmaskin.

Turingmaskin

En Turingmaskin[14] består av en (obegränsad) remsa. Remsan är indelad i kvadrater. Varje kvadrat kan innehålla en etta, en nolla eller ingenting. Remsan används för binärt kodad information.

Turingmaskin

Turingmaskinen befinner sig hela tiden i något tillstånd som vi kan kalla \(t_0, t_1, t_2,\ldots \). När maskinen startar, vid tillståndet \(t_0\), har remsan någon sorts information (indata). När maskinen är klar (om den blir klar) innehåller remsan resultatet (utdatan).

Maskinen innehåller ett läs- och skrivhuvud som hela tiden befinner sig vid någon kvadrat på remsan. Huvudet kan läsa och skriva i den ruta där den befinner sig och förflytta sig ett steg åt höger eller vänster.

Maskinen har också en styrenhet som bestämmer exakt vad skrivhuvudet ska göra för varje tillstånd beroende på vad det står i den aktuelle kvadraten.

En instruktion kan för tillstånd \(23\) kan exempelvis vara

\(t_{23}\)

Om det står \(1\):

   skriv \(0\)

   flytta ett steg åt höger

   övergå till \(t_{175} \).

annars:

   flytta ett steg åt vänster

   övergå till \(t_{176} \).

En dator som kan hantera alla de program en Turingmaskin kan hantera, sägs vara Turingkomplett. Inom algoritmteori används Turingmaskiner för att beskriva vad som menas med lösbara problem, dvs problem som kan lösas av en Turingmaskin. Turingmaskiner används också för att klassificera hur svåra olika problem är.

En Turingmaskin kan till slut hamna i ett sluttillstånd då programmet körts klart. Det kan också vara så att sluttillståndet aldrig nås. Man kan exempelvis tänka sig att det någonstans i programmet finns en oändlig loop. I ett sådant fall stannar Turingmaskinen aldrig. Turing valde att använda detta problem:

Kan en Turingmaskin avgöra om en Turingmaskin med ett givet program och given indata kommer att stanna?

Problemet kallas för Turings stopproblem, eller halting problem på engelska. Turing bevisade att svaret var nej. Därmed hade han bevisat att det finns problem som inte kan lösas av en dator. Det är en avsevärd skillnad på att inte kunna lösa och att inte kunna lösa inom en rimlig tid. Ibland framställs erkänt svåra problem inom algoritmteori felaktigt som "icke-lösbara" när de i själva verket kan lösas fast det möjligen tar några miljarder år. Ett sådant svårt problem är att faktorisera en produkt av två mycket stora primtal. Det går att faktorisera men det för lång tid. Denna svårighet används inom kryptering. Turings stopproblem däremot, är bevisligen inte lösbart.

Under andra världskriget arbetade Turing på Bletchley Park i ett projekt som gick ut på att knäcka tyskarnas Enigma-kryptering. När de slutligen knäckte koden samlade de därefter in information från tyska radiosignaler, information som gick under kodnamnet Ultra. Ultra hade en avgörande betydelse för de allierade. Den amerikanska presidenten Eisenhower hade, tack vare Ultra, i stort sett lika god information om tyskarnas planerade framryckningar som Hitler hade[15]. Det mesta av det arbete som Turing och andra gjorde på Bletchley Park hemligstämplades fram till mitten av 1970-talet.

I slutet av 40-talet, efter kriget, arbetade Turing bl.a. med mjukvara till datorer och publicerade teorier kring maskiner och intelligens, detta var innan orden artificiell intelligens börjat användas. Turing föreslog ett test för att avgöra huruvida en maskin uppvisade mänsklig intelligens eller inte. Testet har senare kommit att kallas för Turingtestet.

Turingtest

Ett Turingtest går till på följande vis:

En intervjuare (en människa) kommunicerar med en maskin (A) och en annan människa (B). Både A och B döljs bakom skärmar och all kommunikation är textbaserad. Intervjuaren får ställa vilka frågor som helst och ska i slutet avgöra vilken av A eller B som är maskinen. Om intervjuaren inte kan dra slutsatsen att maskinen är en maskin, sägs maskinen ha klarat Turingtestet.

År 1966 skapades det första programmet som klarade Turingtestet. Programmet kallades ELIZA.

Turing var homosexuell vilket var förbjudet i England på den tiden. År 1952 åtalades han för "gross indencency". I domstolsförhandlingarna medgav Turing att han var skyldig och dömdes därefter till kemisk kastrering. Eftersom han nu i domstol befunnits vara kriminell ansågs han inte längre vara tillförlitlig och fick fortsättningsvis inte arbeta med kryptering inom brittisk signalspaning, vilket han gjort även efter andra världskrigets slut.

År 1954 hittades Turing, 41 år gammal, död. Bredvid sängen där han låg fanns ett halvätet äpple som förmodligen innehöll cyanid. Turing antas ha tagit sitt eget liv som en följd av det han fått utstå.

Under 2000-talet har det startats flera namninsamlingar för att tvinga fram en officiell ursäkt för det Turing fick utstå efter kriget. År 2013 fick Turing en officiell ursäkt från drottning Elisabeth II, å regeringens vägnar[16]. Efter detta startades namninsamlingar för att i efterhand benåda alla de 49 000 som, liksom Turing, dömts för "gross indencency"[17]. År 2017 benådades alla de dömda i efterhand med en lag som kommit att kallas Alan Turing law.

Den elektroniska datorn

De första fungerande datorerna, som gick att programmera, var så kallade elektromekaniska datorer som alltså både innehöll mekaniska komponenter och elektronik. De allra första sådana datorerna byggdes av Konrad Zuse i Tyskland i slutet av 1930-talet och början av 1940-talet.

Z3
En återskapad dator som konstruerats av Konrad Zuse dator Z3[18].

Zuse hade arbetat som ingenjör på en flygplansfabrik och hade där slagits av hur många beräkningar han tvingats göra för hand. Zuses första datorer kunde utföra beräkningar och han konstruerade ett antal datorer med utökad kapacitet, datorerna Z1, Z2 och Z3. Datorn Z3 hade den kapacitet man numera räknar att en maskin ska ha för att kunna kallas dator, den var Turingkomplett.

På 1940-talet utvecklades de första maskinerna som enbart bestod av elektronik och som styrdes av digitala signaler. Den första elektroniska digitala maskinen som var Turingkomplett, var datorn ENIAC (Electronic Numerical Integrator And Computer) vilken började konstrueras av den amerikanska armén på 1940-talet. I sin slutversion, på 1950-talet, vägde ENIAC 27 ton och upptog 167 m2. En komponent i de tidiga datorerna som gjorde dem skrymmande och tunga, var elektronrör vilka användes för signaler.

Eniac
Några elektronrör på en ENIAC[19].

Transistorn[20], som uppfanns på 1950-talet, kom att ersätta elektronrör i såväl datorer som andra elektroniska apparater. Med tiden gjordes transistorerna så små att de kunde ingå i integrerade kretsar vilka en modern dator är uppbyggd av. Mikrochipstekniken utvecklas ännu i en hastighet som beskrivs av Moores lag, dvs: antal transistorer som får plats i en integrerad krets fördubblas ungefär vartannat år.

John von Neumann

Liksom andra världskriget kom att driva på teknikutvecklingen i Europa, exempelvis krypteringstekniken, kom kriget i allra högsta grad att påverka teknikutvecklingen i USA. I Manhattanprojektet, för konstruktion av den första atombomben, behövdes kraftfulla beräkningsmaskiner. En av de vetenskapsmän som engagerades i Manhattanprojektet var matematikern John von Neumann (1903 - 1957) som hade expertis kring explosioner (vilka är svåra att matematiskt modellera).

von Neumann var en mångsysslare som gjorde betydande insatser framför allt inom matematik men även inom fysik och ekonomi. Vad beträffar datavetenskap beskrev han år 1945, tillsammans med andra, en arkitektur för datorer som senare kommit att kallas för von Neumann arkitekturen. Han föreslog också en konstruktion av en så kallad EDVAC-dator. Inom algoritmteori bidrog von Neumann bland annat med teorin om så kallade cellulära automater och en av de mest kända sorteringsalgoritmerna merge sort.

I Manhattanprojektet hade von Neumann, med hjälp av datorer, gjort beräkningar på atombombens verkan, dvs från vilken höjd den skulle fällas, vilken räckvidd den skulle ha, m.m. För att få maximal effekt föreslog von Neumann att Kyoto skulle vara målet för den första atombomben, vilket möjligen hade varit ett bra val om man kunnat betrakta fällandet av en atombomb enbart som ett optimeringsproblem. Den amerikanske krigsministern Henry L. Stimson såg till att Kyoto bevarades för eftervärlden och istället fälldes bomberna över Hiroshima och Nagasaki.

Grace Hopper

Under andra världskriget användes bl.a. en elektromekanisk dator kallad Mark I som utvecklats vid universitetet Harvard efter en design gjord av Howard H. Aiken. Ett av de första programmen som kördes av Mark I var ett program gjort av von Neumann. En av de mest kända programmerarna av Mark I är amiral Grace Hopper (1906 - 1992) som innan hon anslöt sig till den amerikanska flottan disputerat i matematik vid universitetet Yale. Aiken, som designat Mark I, var också reservofficer i flottan och kom att bli Hoppers chef. Hopper är känd inom datavetenskapen för att vara en av pionjärerna bakom kompilatorn. För en bredare publik är hon även känd för att ha en underhållande föreläsningsstil[21].

Under 50-talet ledde Hopper den amerikanska flottans arbete med att utveckla programmeringsspråk som mer liknade mänskligt språk än maskinkod, programmeringsspråk som skulle kunna användas av olika maskiner. De utvecklade ett språk kallat FLOW-MATIC vilket senare ledde till ett kompilerat språk, språket COBOL. Hopper räknas som en av pionjärerna bakom kompilatortekniken, vilken i sin tur är en förutsättning för att en dator ska kunna fungera som någonting annat än en ren beräkningsmaskin. Fram tills kompilatorer började användas, hade alla idéer som i slutänden resulterade i en dator, alla dess idéer hade kommit från matematiker och de hade handlat om beräkningar. Hopper, som själv var matematiker, beskrev hur kompilatorn togs emot[22]:

I had a running compiler and nobody would touch it. They told me computers could only do arithmetic.



Referenser och mer information

[1] Isaac Newton letter to Robert Hooke, 1675 [electronic resource]

[2] 2010, Matematik för lärare Ypsilon Band 1 (sid 320), av Hans Christian Hansen, Kristine Jess, Jonh Schou, Jeppe Skott.

[3] 1914, John Napier and the invention of logarithms, 1614; a lecture, by Hobson, Ernest William ‐ via Internet Archive

[4] Mechanical Computing (YouTube): How the Pascaline works

[5] 1685, Manuskript där Leibniz beskriver sin maskin Machina arithmetica in qua non aditio tantum et subtractio sed et multiplicatio nullo, divisio vero paene nullo animi labore peragantur, via History of computers ‐ The Stepped Reckoner of Gottfried Leibniz.

[6] Wikipedia ‐ List of things named after Leonhard Euler

[7] The truth about Königsberg av Brian Hopkins och Robin Wilson, via Mathematical Association of America (MAA)

[8] Bild på hålkort till vävmaskin från Wikimedia ‐ Jacquard loom cards (public domain)

[9] Wikipedia ‐ Human computer

[10] Memoir of the Life and Labours of the Late Charles Babbage via Biography Online

[11] Clay Mathematics Institute: Ada Lovelace's mathematical papers

[12] Numberphile (YouTube): Gödel's incompleteness theorem explained

[13] 1936, On Computable Numbers, with an Application to Entscheidungsproblem av Alan Turing via London Mathematical Society

[14] Computerphile (YouTube): Turing Machines Explained

[15] 1981, Eisenhower and the Intelligence Community in World War II av Stephen E. Ambrose

[16] BBC: Royal pardon for codebreaker Alan Turing

[17] change.org: Pardon all of the estimated 49,000 men who, like Alan Turing, ...

[18] Bild på Z3 från Z3 Deutches Museum (Creative Commons Attribution-Share Alike 3.0 Unported)

[19] Bild på ENIAC-elektronrör från ENIAC Penn 2 (Creative Commons Attribution-Share Alike 3.0 Unported)

[20] AT&T Tech Channel (YouTube) The Transistor: a a 1953 documentary, anticipating its coming impact on technology

[21] YouTube: Grace Hopper on Letterman eller Grace Hopper segment on 60 minutes

[22] America's NAVY: USS Hopper (DDG 70) Named for Rear Admiral "Amazing" Grace Hopper