Året er 1968. Som en af årets studenter står jeg over for det vigtige valg af studium på Aarhus Universitet. Helt i tråd med ånden i 1968 blev vi rådet til at vælge ud fra, hvad vi syntes var sjovest, og vi skulle absolut ikke tænke på afsporende kriterier som eksempelvis anvendelighed.
Og det gjorde jeg så – det skulle være noget med matematik. Lidet vidende, at jeg reelt var kommet til at vælge et fag, som ud over at være sjovt skulle komme til at ændre hverdagen radikalt for hele menneskeheden.
På Aarhus Universitet havde man i 1965 fremskaffet en af de første regnemaskiner i landet. Regnemaskinerne var udviklet først og fremmest til militære formål, men fremsynede og visionære folk på universitetet kunne allerede dengang se, at der kunne være en fremtid i »de der regnemaskiner«, og at Aarhus Universitet måtte være på forkant.
Mit studium kom derfor til at foregå på en helt ny uddannelse, som kombinerede matematik med noget, som ingen rigtig vidste, hvad var, men som man kaldte datalogi.
Hvad var det lige, der skete?
Regnemaskinen på Aarhus Universitet var en dansk produceret GIER. Den havde en lagerkapacitet på under 100 kB, kostede i dagens priser omkring 10 millioner kroner, og GIER var helt frem til 1976 den eneste regnemaskine på hele universitetet. Den var derfor kun for de få udvalgte. Som studerende kunne vi få adgang nogle få timer om ugen – typisk om natten.
Til sammenligning har mange af os i dag vores private mobiltelefon i lommen – med groft regnet en million gange så stor kapacitet og til en brøkdel af prisen. Og vi bruger den døgnet rundt til alle mulige dagligdags gøremål som for eksempel e-mail, netsøgning, netbank og nethandel.
Hvad var det lige, der skete? Hvordan kunne »de der regnemaskiner« på under 50 år gå fra status som avancerede regnemaskiner til videnskabelige og militære formål for de få til en helt nødvendig og naturlig del af hverdagen for alle?
Der er groft sagt to forklaringer
Der er groft sagt to forklaringer, som pænt går hånd i hånd. For det første den rent teknologiske, hvor hardwaren konstant er blevet mindre, hurtigere og billigere.
Men computeren er i princippet den samme i dag som for 50 år siden – al information er gemt i bits (en dims, som kan antage en af to værdier, for eksempel 0 og 1), og computeren er i dag som dengang en bitvender, som nu blot kan vende mange flere bits meget hurtigere.
Computeren i dag kan på imponerende vis behandle eksempelvis lyd og billeder, men for computeren er det et fedt og det samme. Det hele er gemt som bits, som programmer vælger at tolke som for eksempel lyd eller billeder, så det for os brugere illuderer lyd- eller billedbehandling.
For det andet har softwaren konstant udvidet computerens anvendelsesmuligheder. I dag præsenteres vi dagligt for nye smarte apps, der som oftest er varianter af noget, som vi kender i forvejen. Men enkelte gange sker det, at nogen får en idé, som for alvor rykker og åbner for helt nye anvendelsesmuligheder.
I det følgende vil jeg give nogle få eksempler fra datalogiens verden på ideer, som har rykket.
Volapyk med mening
På meget få år er vi alle blevet afhængige af computeren til kommunikation med både offentlige myndigheder (modtagelse af elektroniske dokumenter, indberetning af selvangivelser mv.) og private virksomheder (netbank, nethandel mv.).
Vi modtager og sender en masse følsomme informationer elektronisk over internettet i tro på, at de ikke bliver opsnuset af uvedkommende.
Når der øverst på en webside står en linje, som starter med https://…, indikerer det lille s, at kommunikationen foregår krypteret og dermed sikkert. Men hvad betyder det egentlig?
Krypteringsteknikker er oftest baseret på nøgler
Kryptering kommer fra det græske ord kryptos, som betyder skjult. Mere konkret dækker kryptering over teknikker, som kan bruges til at kryptere en besked til noget volapyk, som så igen kan dekrypteres til den oprindelige besked.
Denne artikel stammer fra bogen ’25 søforklaringer – Naturvidenskabelige fortællinger fra Søauditorierne’.
Bogen bringes i samarbejde med Aarhus Universitetsforlag.
I løbet af efteråret er det muligt at deltage i flere fordrag, der blandt andet omhandler emner omtalt i bogen. Foredragene bliver holdt i Aarhus, Herning, Horsens og Vejle
Krypteringsteknikker er oftest baseret på nøgler, som bruges til at kryptere (lukke) og dekryptere (lukke op). Antag, at en afsender – Søren – vil sende en besked over internettet til en modtager – Mette – og at beskeden indeholder information, som Mette, og kun Mette, skal kunne læse.
Hvis Søren sender beskeden afsted over internettet (som bits for eksempel i ASCII-standarden), risikerer han, at hvem som helst kan opsnuse beskeden undervejs – nøjagtig som når vi sender breve med posten!
En volapyk-besked skal kunne dekrypteres af modtageren
I krypteret kommunikation sender Søren i stedet en volapyk-version af beskeden, som selvfølgelig godt kan opsnuses, men som ikke giver mening for udenforstående. Bortset fra Mette, som ved modtagelsen skal kunne dekryptere volapyk-versionen til den oprindelige besked.
Hvis et sådant system skal virke i praksis, er der (mindst) to krav, som skal være opfyldt:
- Søren skal kunne kryptere en besked, og Mette skal kunne dekryptere og dermed genskabe den oprindelige besked (genskabelseskravet)
- Det skal ikke være muligt for andre end Mette at genskabe beskeden ud fra den krypterede version (hemmelighedskravet)
Behovet for kryptering er flere tusinde år gammelt
Behovet for og brugen af kryptering er kendt flere tusinde år tilbage i tiden. I Romerriget benyttede man eksempelvis en teknik, som i dag kendes som Cæsar-teknikken. Den blev brugt til kommunikation mellem hærafdelinger.
Cæsar-teknikken kræver, at afsender og modtager er enige om et heltal – for eksempel 3 – som hemmelig nøgle. Afsender krypterer derefter en besked ved at erstatte hvert bogstav med det bogstav, som ligger 3 længere fremme i alfabetet, og modtager dekrypterer tilsvarende ved at tælle 3 tilbage i alfabetet.
Cæsar-teknikken kan virke lidt naiv i dag. Den tilfredsstiller klart genskabelseskravet ovenfor, men lige så klart lever den ikke op til hemmelighedskravet. I det danske alfabet ville der være 29 forskellige hemmelige nøgleværdier, og det vil selvfølgelig være let for en tredjeperson at prøve at dekryptere med alle 29 forskellige nøgler.
Enigma-maskinen ‘knækkede nøgler’
I tidens løb er der blevet udviklet mange mere og mere sofistikerede varianter af Cæsar-metoden til kryptering.
De fleste kender sikkert til historierne fra Anden Verdenskrig, hvor den tyske hær krypterede militære beskeder med Enigma-maskiner specielt konstrueret til formålet, ligesom den engelske hær etablerede en enhed på Bletchley Park med den opgave at dekryptere de tyske Enigma-beskeder, dvs. at ‘knække nøgler’.
Enheden bestod af matematiske eksperter, herunder ikke mindst en vis Allan Turing, som i dag betragtes som en af datalogiens fædre (mere om ham senere).
It-kryptologi og tallenes natur
Udfordringerne for it-kryptering er imidlertid langt større end på Enigmas tid, blandt andet fordi man kan bruge computeren selv til at knække nøgler! Så udfordringen for it-kryptering er at finde helt nye teknikker, som ikke kan knækkes af selv de smarteste og hurtigste supercomputere.
En række dataloger tog i 1970’erne udfordringen op, og uafhængigt af hinanden opfandt de banebrydende originale teknikker til it-kryptering. Den fælles idé, som for alvor rykkede, var at basere sig på velkendte resultater fra den matematiske disciplin talteori.
Resultater, som gennem århundreder er blevet formuleret og bevist af grundforskere, der var drevet af nysgerrighed og ikke havde tanke for eventuelle anvendelser. Og ideerne fra dengang i 1970’erne er stadig den dag i dag grundlaget for den it-kryptering, vi alle er blevet afhængige af.
Der findes symmetriske og assymetriske nøgler
Man skelner i dag mellem to forskellige klasser af krypteringsteknikker: symmetriske og asymmetriske. De symmetriske (også kaldet secret key encryption) benytter sig af samme hemmelige nøgle mellem afsender og modtager til såvel kryptering som dekryptering – ligesom i Cæsar-teknikken.
I de asymmetriske (også kaldet public key encryption) har alle to nøgler, en offentligt kendt og en hemmelig privat, og afsender krypterer en besked til en modtager med modtagers offentlige nøgle, og modtager dekrypterer med sin egen private nøgle.
Men det er svært at se, hvad sætninger som denne har med ‘den rigtige verden’ at gøre – klarest udtrykt af en af de største talteoretikere G.H. Hardy (1877-1947):
»I have never done anything ‘useful’. No discovery of mine has made, or is likely to make, directly or indirectly, for good or ill, the least difference to the amenity [bekvemmelighed] of the world.«
Og så alligevel er Hardys forskningsområde nu nogle få årtier senere fundamentet for vores daglige brug af netbank, nethandel og meget, meget mere!
Lad os som et eksempel se på en af de mest kendte asymmetriske krypteringsmetoder, RSA, som har fået sit navn efter tre dataloger Ron Rivest, Adi Shamir og Leonard Adleman, der stod bag den oprindelige idé fra 1975.
I RSA genereres offentlige og hemmelige nøgler som store tal ud fra et eksotisk, men letforståeligt begreb fra matematikken, nemlig primtal, dvs. tal, som kun kan deles med 1 og tallet selv. 2, 3 og 5 er eksempler på primtal, mens 4 og 6 ikke er primtal.
RSAs genskabelseskrav er baseret på en smuk egenskal for primtal
Beviset for, at RSA tilfredsstiller genskabelseskravet ovenfor – at Mette ved at dekryptere med sin egen hemmelige nøgle får den oprindelige besked krypteret med Mettes offentlige nøgle – er baseret på en smuk, men tilsyneladende totalt uanvendelig egenskab for alle primtal.
Det var den franske matematiker Pierre de Fermat, der helt tilbage i 1640 formulerede dette. Det skete i hans såkaldte ‘lille sætning’.
Et karakteristisk eksempel på matematisk grundforskning styret udelukkende af Fermats nysgerrighed i tallenes natur uden nogen tanke på anvendelser – og da slet ikke i sammenhæng med moderne it-kryptologi!
Sikkert – indtil videre
Men hvad med RSA og hemmelighedskravet til kryptering – at udenforstående ikke skal kunne genskabe en besked ud fra den krypterede version? I princippet er det ikke umuligt at gætte Mettes private nøgle. Det er blot et spørgsmål om at prøve med tallene et for et ligesom ved Cæsar-teknikken.
Men for det første kan det vises, at med størrelsen af de nøgler, som vælges i praksis, vil det tage selv den hurtigste supercomputer, vi kender i dag, mange år at gennemløbe alle muligheder.
For det andet, og endnu vigtigere, kan datalogerne vise, at noget tilsvarende gælder for en vilkårlig anden mere sofistikeret teknik til at gætte Mettes private nøgle. Under visse antagelser!
Ethvert tal kan skrives som et produkt af primtal
Én antagelse er, at visse matematiske problemer ikke kan løses inden for rimelig tid – selv på superhurtige computere. For RSA’s vedkommende drejer det sig om faktorisering – et problem, som simpelt kan forklares som følger.
Det er velkendt fra matematikken, at ethvert tal på en og kun en måde kan skrives som produkt af primtal (20 kan for eksempel skrives som 2×2×5). Faktorisering er nu ganske enkelt det problem for et givet heltal at finde dets produkt af primtal.
RSA-antagelsen er, at for store heltal vil enhver algoritme, som løser problemet, tage urealistisk lang tid om at nå frem til resultatet. Det er en antagelse, som de fleste tror på, men som ikke er formelt bevist.
Antagelsen er relateret til et uløst problem i teoretisk datalogi
Antagelsen er relateret til det mest celebre uløste problem i teoretisk datalogi: P = NP? Et af i alt syv matematiske problemer, hvis løsning vil udløse en pris på en million dollars. Prisen blev udlovet af det amerikanske Clay Mathematics Institute i 2000.
Problemet er med dagligdags ord, om ethvert problem, som hurtigt kan verificeres på en computer (det er let at tjekke, om et forslag til en faktorisering er korrekt), også hurtigt kan løses på en computer.
Det vil føre for vidt at gå dybere ind i en forklaring af problemet her, men som det næsten fremgår af den simple forklaring, vil en bekræftelse af P = NP betyde enden på RSA (og alle de andre it-krypteringsteknikker, som vi bruger i dag). De færreste tror dog på det udfald.
Digitalsignatur er en it-version af en underskrift
En anden antagelse er, at algoritmer afvikles på computere af samme type, som vi kender dem i dag. Men man kan ikke udelukke, at der på et tidspunkt vil blive udviklet helt nye former for computere, som vil kunne knække RSA-nøgler. Faktisk ved man, at det vil være tilfældet med såkaldte kvantecomputere.
Men bare rolig. Indtil videre er det helt sikkert at benytte RSA og andre veletablerede krypteringsteknikker, og skulle en af antagelserne ovenfor bryde sammen, er datalogerne klar med nye sofistikerede teknikker.
Endvidere bør det nævnes, at vi her har fokuseret på et enkelt overordnet princip, som i sagens natur involverer mange andre aspekter. Som eksempel kan princippet bag RSA (og andre asymmetriske krypteringsteknikker) direkte anvendes til en anden vigtig opgave på internettet: digital signatur.
En digital signatur er, som navnet siger, en it-version af en underskrift, som vi kender den fra almindelige dokumenter. I RSA- versionen er ideen kort fortalt, at Mette underskriver en besked ved at kryptere den med sin egen private nøgle, og alle andre kan derefter verificere, at Mette er den faktiske underskriver ved at dekryptere med Mettes offentlige nøgle.
De mest interessante pastaretter
Langt de fleste af os bruger hver eneste dag computeren eller vores smartphone til at søge information. Vi taster et par ord ind til vores søgemaskine, og næsten hver eneste gang får vi i løbet af et splitsekund listet hjemmesider, som indeholder lige nøjagtig den information, som vi ledte efter.
Søgemaskiner leder efter information i samlingen af alle www-sider på internettet, World Wide Web. Det er i dag en kæmpestor samling af mange milliarder sider – måske den mest komplekse menneskeskabte konstruktion gennem tiderne.
Og søgemaskiner har typisk mange tusinder af søgninger i sekundet. Så det er virkelig som at lede efter en nål i en høstak – og hvordan kan det lade sig gøre? Det virker af og til, som om søgemaskinen er en intelligent tankelæser. Det er den ikke! Men hvad sker der så i en moderne søgemaskine? Uden at gå i detaljer er de overordnede principper faktisk overraskende simple.
Der er to komponenter i en søgemaskine. For overhovedet at kunne søge er det nødvendigt med struktur på den kæmpemæssige samling af information, og det tager den ene komponent sig af (webcrawling og indexing), mens den anden komponent så tager sig af selve søgningen (searching og ranking).
En webcrawler er uhyre simpel at lave
Information struktureres i et såkaldt indeks, der er en simpel og ældgammel idé, som vi alle kender fra for eksempel kogebøger, hvor vi på de sidste sider kan finde et stikordsregister over ord som for eksempel pasta, dvs. en liste over alle de sider i kogebogen, hvor der findes opskrifter med pasta.
Et www-indeks er tilsvarende en liste over alle ord, som forekommer på www- sider, og for hvert ord en liste over alle de www-sider, hvor ordet forekommer.
Samlingen af www-sider er imidlertid lidt speciel, idet den konstant ændrer sig: Hvert sekund dukker nye sider op, og andre sider forsvinder. Og det er her, webcrawling kommer ind i billedet: En moderne søgemaskine kravler konstant rundt på nettet og forfølger links (de ord, man kan klikke på, og derved komme til en ny side) for derigennem dels at opdatere viden om www-sider, og hvordan de linker til hinanden, dels at opdatere indekseringen af www-sider som beskrevet ovenfor.
En webcrawler er uhyre simpel at lave, så den kan gennemløbe mange millioner sider i løbet af en dag, og søgemaskinen har dermed altid et rimeligt billede af hele World Wide Web.
De fleste sider er sandsynligvis totalt uinteressante
Når vi så søger efter for eksempel pasta, slår søgemaskinen ganske simpelt op i sit indeks og finder alle de sider, hvori pasta forekommer. Det er der ingen ben i. Der er ganske vist mange ord at ‘slå op i’, men det har datalogerne styr på med masser af effektive metoder til at søge i store datamængder.
Problemet er nu, hvad søgemaskinen stiller op med de mange elementer i indekset for pasta, dvs. de mange millioner www-sider, hvori pasta forekommer. De fleste sider er sandsynligvis totalt uinteressante, og vi ønsker selvfølgelig at få præsenteret de ‘mest interessante’. Men hvordan vælger søgemaskinen de mest interessante?
De første søgemaskiner fra midten af 1990’erne definerede typisk de mest interessante sider ved at se på indholdet af sider, for eksempel antallet af forekomster af søgeordet, dets forekomster i overskrifter og lignende.
Nogle vil også huske, at de sider, som virkelig var af interesse, tit og ofte stod meget ‘langt nede’ i resultatet i en søgning. Det krævede derfor alt for megen forgæves læsning og klikken at finde frem til en interessant side, og derfor var de tidlige søgemaskiner ikke særligt udbredte.
Google finder nålen
Men omkring år 2000 skete der pludselig noget. Et par unge datalogistuderende på Stanford University, Larry Page og Sergey Brin, havde fået en genial idé til at finde de mest interessante sider – en idé, som skulle vise sig med ét at gøre søgemaskinerne til hvermands eje.
De to studerende kaldte deres søgemaskine for Google – oprindeligt Googol, som er en betegnelse for tallet 1 efterfulgt af 100 nuller. Google er i dag er navnet på en af verdens største IT-virksomheder og samtidig blevet et dagligdags ord for at søge på nettet – i 2012 officielt optaget i Dansk Sprognævns Retskrivningsordbog.
Deres idé, som de kaldte PageRank, var ikke at se på indholdet af sider, men i stedet på links mellem sider. De mest interessante sider er så de sider, som flest andre sider linker til. Kort sagt de mest populære sider.
Men det er ikke hele historien. Hvis man blot talte antallet af direkte links, kunne ejeren af en side jo let selv gøre siden ‘interessant’ ved at linke til den fra en masse selvkonstruerede sider og dermed ødelægge hele princippet bag ‘mere interessant’.
Selve ideen i PageRank definerer en sides vigtighed
Den oplagte løsning på det problem er at definere ‘interessant’ i forhold til antallet af links fra ‘interessante’ sider. Men det er jo en definition, som bider sig selv i halen (dataloger kalder den rekursiv), og som tilsyneladende ikke kan bruges til noget.
Og alligevel er det selve ideen i PageRank, som definerer en sides vigtighed i forhold til, hvor ofte en tilfældigt strejfende webcrawler ville besøge siden. Mere konkret vælger man i PageRank følgende strejfer: Når strejferen besøger en www-side s, vælger den med 85 % sandsynlighed at gå videre til en tilfældig side, som s linker til, og med 15 % sandsynlighed at gå videre til en helt tilfældig side på World Wide Web.
Det relative antal gange, en www-side besøges af en sådan strejfer, vælges nu som mål for, hvor ‘interessant’ siden er.
Bemærk, at strejferen kun vil besøge en side s ofte, hvis den ofte besøger nogle af de sider, som linker til s, og dermed indfanges den rekursive formulering af ‘interessante’ sider ovenfor. Og det mål foreslog Page og Brin nu at bruge til at præsentere de mest interessante sider – med en forbløffende effekt!
Matematikken kommer datalogien til hjælp
Men hvis Google skulle starte en sådan strejfer, hver gang vi foretager en søgning, ville det naturligvis tage alt for lang tid at få et bud på de mest interessante sider. Og her kommer matematikken og datalogien igen til hjælp!
På baggrund af en matematisk disciplin, som går under betegnelsen Markov-kæder, kan målet for, hvor ‘interessant’ en side er, på simpel vis estimeres på basis af (et stort antal) multiplikationer af (store) såkaldte matricer, dvs. rækker og kolonner af tal, som repræsenterer strejferens opførsel.
Det vil sige, at Google-ranking i princippet kan koges ned til at multiplicere store matricer igen og igen – en stor men simpel regneopgave, som lige præcis er en af computerens spidskompetencer. Og det er kernen i argumentet for, hvor overraskende hurtigt Google kunne præsentere de mest interessante pastaretter.
Google Translate er baseret på håndtering af statistiske informationer
Det bør nævnes, at moderne søgemaskiner som Google gennem årene er blevet raffineret med mange nuancer i forhold til ovennævnte, men det overordnede princip er stadig det samme.
I det hele taget er googlesøgninger kun et eksempel på moderne anvendelse af datalogiske teknikker til udnyttelse af computerens enorme kapacitet til at håndtere store datamængder. Faktisk er mange forskningsområder i dag i stigende grad baseret på netop computerens evne til at udføre modelberegninger med meget store datamængder.
Som et kuriosum kan det nævnes, at også Google Translate er baseret på håndtering af enorme statistiske informationer om eksisterende oversættelser – uden nævneværdig brug af sprogvidenskab.
Grænser for galskaben
Ovenfor har vi set eksempler på banebrydende ideer med enorm betydning for udbredelsen af it. Hvor er grænsen, kunne man spørge. Eller er der overhovedet nogen grænse for computerens formåen? Svaret er et rungende ja!
Ovenikøbet findes der mange tilsyneladende simple og velmotiverede praktiske opgaver, som beviseligt ikke kan løses på computeren, uanset hvor smarte ideer dataloger og andet godtfolk måtte få fremover.
En løsning på en it-opgave er en algoritme, dvs. en opskrift til computeren på, hvordan opgaven skal løses (fx RSA-kryptering eller Google-ranking). Og argumentet for, at der findes opgaver, som ikke har algoritmiske løsninger, hænger overraskende tæt sammen med den idé, som måske mere end nogen anden har haft betydning for computerens udbredelse: dualiteten mellem algoritme og data.
En algoritme er en bageopskrift
Lad os begynde med at se på, hvad en algoritme egentlig er. Vi kender algoritmer i mange sammenhænge (bageopskrifter, samlevejledninger til LEGO osv.). En algoritme er en tekst, der beskriver, hvordan man bearbejder nogle ingredienser (for eksempel mel og æg), så man får et ønsket produkt (for eksempel en kage).
En beskrivelse af en algoritme på en computer kaldes et program og er præcis det samme – en tekst, som beskriver en bearbejdning af inddata til uddata! Men der er en væsentlig forskel.
Mens data for en bageopskrift (mel og æg) er helt andre størrelser end opskriften selv, har vi jo set, at inddata og uddata til computerens programmer (uanset om vi tolker dem som for eksempel tal, billeder eller lyd) i virkeligheden er bitmønstre, dvs. tekster nøjagtig som programmerne selv!
Det lyder banalt, men ikke desto mindre var det den simple observation, som for alvor ligger bag det måske største ryk overhovedet i computerens historie – et ryk, som normalt tilskrives den ungarsk-amerikanske matematiker John von Neumann (1903-1957).
Mange algoritmer kunne lagres på computeren
Regnemaskinen er meget ældre end von Neumann. De første mekaniske regnemaskiner kan dateres flere hundrede år tilbage i tiden. Men alle regnemaskiner indtil 1940’erne bestod af to separate enheder: en konstrueret specielt til algoritmen (regneopskriften) og en anden til data (tal) – helt i tråd med bageopskrifterne.
Det ændrede sig, da John von Neumann foreslog at udnytte dualiteten mellem computerens algoritmer og deres data: at lagre algoritmer på nøjagtig samme måde som data. Konstruktionen af den første computer efter det princip, EDSAC (Electronic Delay Storage Automatic Calculator) blev ledet af den britiske datalog Maurice Wilkes (1913- 2010) på Cambridge University i England.
Og konsekvenserne var enorme. Indtil EDSAC skulle computeren som oftest fysisk bygges om, hver gang en ny algoritme skulle afvikles. Men med von Neumanns idé kunne mange algoritmer lagres på computeren, og algoritmeskift håndteres af computerens egen software. Og den idé bliver udnyttet i det ekstreme i nutidens computere – uden at vi som brugere bemærker det.
Turings observation var i en anden kontekst
Dualiteten mellem algoritmer og data på computeren var i virkeligheden observeret allerede i 1936 af en ung, britisk matematiker Allan Turing (1912-1954) ( ja, den samme Turing, som senere under anden verdenskrig knækkede krypteringsnøgler på Bletchley Park).
Men Turings observation var i en helt anden kontekst og med et helt andet sigte, nemlig at udforske grænserne for computerens formåen.
Og det er interessant, at ikke blot dualiteten mellem algoritme og data her spiller en afgørende rolle, men også, at nogle af de mest kendte filosofiske, abstrakte paradokser her får kød og blod som stringente og håndfaste ingredienser i Turings matematiske beviser.
Begrebsmæssigt er der ikke forskel på en repræsentation af en algoritme og dens data
Turing var sammen med en række andre matematikere i 1930’erne optaget af at etablere et matematisk grundlag for computerens algoritmer. Turing definerede begrebet i termer af programmer til en matematisk abstrakt maskine, som i dag går under betegnelsen en Turing-maskine.
Turing indså, at der begrebsmæssigt ikke er nogen forskel på repræsentationen af en algoritme og dens data, selv om der altså ikke i 1930’erne fandtes en eneste computer, som udnyttede denne observation!
Begge repræsentationer er i en Turing-maskine (som i en moderne computer) tekster, og en tekst kan man frit vælge at betragte enten som en algoritme eller som data.
Denne dualitet – at man kan se på samme objekt på to forskellige måder – er et tema, som man også har beskæftiget sig med i kunstens verden, for eksempel i Magrittes berømte maleri La trahison des images, som viser en pibe med underteksten: »Dette er ikke en pibe.«
Barberen, som ikke findes
Dualiteten mellem algoritme og data har dramatiske konsekvenser mht. computerens begrænsninger. Kernen i Turings ræsonnementer herfor var først og fremmest, at dualiteten mellem algoritme og data uundgåeligt medfører en konkret variant af et velkendt fænomen: selvreference.
Selvreference er også et kendt tema fra kunstens verden, eksempelvis i Eschers tegning fra 1948 af en hånd, som tilsyneladende tegner sig selv, og fra filosofien, hvor det oftest er kernen i et eller andet paradoks. Et sådant paradoks er følgende udsagn om beboerne i en landsby:
- Barberen klipper alle, som ikke klipper sig selv.
Paradokset fremkommer nu i form af spørgsmålet:
- Hvem klipper så barberen?
It-mæssigt er der intet mystisk over paradokset
Pointen i paradokset her er, at en sådan barber ikke kan findes! Hvis barberen ikke klipper sig selv, skulle han iflg. (1) klippe sig selv, og hvis han klipper sig selv, skulle han iflg. (1) ikke klippe sig selv. Og der findes masser af underholdende eksempler på tilsvarende paradokser.
Men i it-sammenhæng er der intet mystisk over selvreference. På grund af dualiteten mellem algoritme og data kan en programtekst P dels ses som en algoritme, dels som data, dvs. den rå tekst. Men alle tekster kan ses som inddata til algoritmen (P), som derfor kan anvendes på data (P) på lige fod med alle andre tekster.
Det lyder underligt at ‘anvende P på sig selv’, og i de fleste tilfælde vil det da også give ringe mening set fra et praktisk synspunkt. Men det er en uundgåelig konsekvens af det faktum, at algoritmer og data i computeren er repræsenteret i samme form: bits!
Og for mange programmer giver det særdeles god mening. For eksempel kan et program, som tæller antal forekomster af et bestemt symbol i en tekst, uden nogen form for mystik sættes til at tælle antal forekomster i programmet selv.
Det uundgåelige paradoks måtte føre til eksistensen af simple, veldefinerede opgaver
Turing indså, at dette uundgåelige paradoks nødvendigvis måtte føre til eksistensen af simple, veldefinerede opgaver, som beviseligt ikke kan løses algoritmisk, dvs. på en computer. Lidt forsimplet kan vi illustrere Turings ræsonnement med en variant af barberparadokset.
Afviklingen af en algoritme på en tekst som inddata resulterer i en anden tekst som uddata. Vi kan nu dele alle uddata-tekster i de tekster, som indeholder ordet klipper, og de tekster, som ikke indeholder klipper, og betragte udsagnet:
- Programmet B skriver ‘klipper’ i uddata, når det afvikles med inddata P, for hvilke der gælder, at P afviklet med sig selv som inddata ikke skriver ‘klipper’ i uddata.
Læg mærke til, at ‘opgaven’ for det tænkte program B er præcis og veldefineret. For alle inddata P gælder det, at enten forekommer ‘klipper’ i uddata, når P afvikles med sig selv som inddata, eller også forekommer ‘klipper’ ikke!
Der er ikke tale om en ulden og løst formuleret opgave som for eksempel, om en computer ‘kan være intelligent’. Og paradokset fremkommer nu nøjagtig som i paradokset om barberen:
- Skriver B ‘klipper’ i uddata, når det afvikles med sig selv som inddata?
Og præcis som i barberparadokset er der her en indbygget modstrid med den konklusion, at der ikke kan findes et program B, som tilfredsstiller (1).
Alle har oplevet, at programmer kan have fejl
Og hvad så? Vi har kun vist, at en enkelt programmeringsopgave ikke kan løses – en ganske vist simpel og veldefineret, men i praksis totalt uinteressant opgave.
Desværre er opgaven kun lige starten i Turings argumenter for, at det samme beklageligvis også er tilfældet for forfærdeligt mange særdeles interessante opgaver – som for eksempel fejlfinding i programmer.
Vi har alle oplevet, at programmer kan have fejl (forkert beregning af restskat, forkert signal til togets bremsesystem osv.). Og vi kan alle være enige om, at det ville være en lettelse, hvis vi kunne undgå sådanne fejl.
Det kunne for eksempel ske ved, at alle programmer, inden de sættes i brug, blev testet af et superprogram, en såkaldt debugger, som kunne analysere programmet (som data) og besvare spørgsmålet: Er der fejl i programmet (som algoritme)?
Den ultimative debugger findes ikke
Desværre ved man (formelt udtrykt i Rice’s sætning fra 1951), at for alle ikke-trivielle forståelser af fejl i ovenstående (dvs. alle forståelser, hvor der findes mindst et program med fejl og mindst et uden fejl), vil der beviseligt ikke findes en debugger som ønsket.
Ethvert forsøg på at lave et sådant superprogram vil altid enten svare ‘ja’ for mindst et program, som faktisk er fejlfrit, eller (endnu værre) ‘nej’ for mindst et program, som har fejl.
Så der er en god teoretisk grund til, at programmer også i dag er fyldt med fejl. Den ultimative debugger findes ikke, og den vil aldrig kunne findes. Der er arbejde til dataloger nu og i al evighed!
Og det rykker stadig
Året er nu 2013. Vi har set et par eksempler på it-gennembrud i de 45 år, som er gået, siden jeg begyndte på Aarhus Universitet.
Jeg kunne have valgt mange andre, som ville have illustreret den pointe: at de store gennembrud ofte på overraskende vis udnytter resultater fra grundforskningen, som er udviklet i helt andre sammenhænge og typisk helt uden tanke på specifikke anvendelser.
Jeg skal afholde mig fra at gætte på udviklingen de næste 45 år, men jeg er overbevist om, at der vil komme mange tilsvarende overraskende it-gennembrud fra datalogiens hånd, og at man også om 45 år vil trække på smilebåndet af vores primitive brug af it i dag.
