daimiposten er internt meddelelsesorgan for studerende og medarbejdere ved Datalogisk Afdeling, Aarhus Universitet. Indlæggene er ikke udtryk for afdelingens officielle holdning.
Førende teoretikere siger »nu må vi koncentrere os om teknologiske problemer«. Det er at opgive fagets egentlige mål og videnskabelige grundlag på et tidspunkt, hvor dets resultater er enorme, mener kritikere. Værst går det ud over de unge forskere.
»Publish or perish« hed de unge forskeres valgsprog i datalogi for ikke så lang til siden: hvis man ikke få år efter sin ph.d. kunne fremvise en lang liste af videnskabelige publikationer i førende tidsskrifter, så kunne man glemme alt om at forblive i den akademiske verden. Der var ekstremt høje krav til lødighed, kvalitet og relevans, og fagets evne til at lokke nogle af de kvikkeste unge mennesker til kagen, øgede konkurrencen og kvaliteten.
Sådan er det ikke længere. Juris Hartmanis, en af kompleksitetsteoriens fædre, beskriver i sit Turingprisforedrag fra 1993 den nye verdensorden fyndigt som »demo or die«: forskningen skal have direkte teknologisk anvendelighed og resultatets brugbarhed som før blev demonstreret med et matematisk bevis om fx en algoritmes udførelsestid skal nu helst sandsynliggøres af en implementation og empiriske resultater.
Fagets oprindelige videnskabelige motivation (erkendelse) og dens videnskabelige metode (abstraktion) er en saga blot.
Hartmanis¹ foredrag førte til en del reaktioner og en hel konference om »beregningskompleksitet og datalogiens natur«, som man kan læse om i Computing Surveys. Det bør man, hvis man interesserer sig for videnskaben datalogi, selvom forfatternes videnskabsteoretiske overvejelser ofte virker plumpe.
Men der er sket mere i år. En flok af ansete forskere omkring Richard Karp har udgivet en rapport om mål og strategier for teoretisk datalogi, hvis tenor gentager opfordringen i Hartmanis¹ foredrag til at lade den teoretiske datalogi styres mere af den teknologiske udvikling. Denne sidste rapport har givet en del mere genlyd i feltet og er stødt på kraftig opposition hos et mindretal.
Jeg finder diskussionen vigtig og giver derfor et par smagsprøver på de indgående argumenter, som også skulle have interesse for ikke-teoretikeren. Jeg har i fremstillingen ikke fundet anledning til at skjule mine sympatier og kan kun opfordre læseren til at danne sig et eget billede. Alle bidrag til debatten i Karprapportens farvand kan man finde i elektronisk form.
En indledende kommentar mere: Det amerikanske begreb theory of computation dækker, hvad vi herhjemm kalder algoritmik og kompleksitetsteori, altså hvad der på Daimi introduceres i dAlg og delvist i dAds og dFM. Det danske begreb teoretisk datalogi er bredere og dækker fx felter som semantik for programmeringssprog, som på Daimi introduceres på dSem. Alligevel vil jeg bl.a. i oversættelser af citater i det følgende sætte lighedstegn mellem theory of computation og teoretisk datalogi, da mange overvejelser i høj grad er relevante for hele feltet (jeg har også fulgt den almindelige praksis at sætte lighedstegn mellem science og videnskab).
En af Karprapportens hovedopgaver er at identificere fagets hidtidlige bedrifter. Dette defineres som (i) resultater, der øger vores forståelse for beregning, og (ii) teknologiske fremskridt, der kan betragtes som direkte affødt af forskning i teoretisk datalogi. Det sidste er så absolut Karpgruppens fokus.
Et oplagt eksempel er effektive algoritmer. Den hurtige Fouriertransformation (som man lærer om på dAlg) kan nøjes med 2nlog n operationer på flydende tal, i sammenligning med 2n¤ operationer i den naive implementation. Det betyder, at man kan behandle ti sekunders tale på en moderne maskine 11000 gange hurtigere (!) tal fra 1995. Forskellen er kvalitativ: Teoretikernes algoritme kan behandle tale i realtid, selv på en hjemmedatamat, mens den naive algoritme ikke ville kunne det på verdens hurtigste processor.
Som ekspempel på, at hele datalogiske discipliner er udsprunget af teoretisk datalogi, kan vi nævne betydning af teorien for formelle sprog, som på Daimi introduceres på dFM, for konstruktionen af oversættere.
Kompleksitetsteori, der nok er den mest teoretiske disciplin, de fleste ikke-teoretikere kommer i kontakt med, er først og fremmest erkendelsesmæssigt relevant; vi kommer senere ind på dens tværvidenskabelige betydning. Men også den er grundlag for et af vores mest uundværlige teknologiske fund: kryptologien. Uden fx sikker dataoverførsel og elektroniske signaturer ville en stor del af tidens it-udvikling, hvis blomster multimediefolkene for øjeblikket smykker sig med, være ganske utænkelig.
»Jeg tror, at vi kun har set toppen af isbjerget. Alene kryptologiens økonomiske betydning er sandsynligvis mange hundrede gange større end, hvad der nogensinde er investeret i teoretisk datalogi som helhed.«
Man kan konkludere, at teoretikerne har været for dårlige til at udpege den teknologiske anvendelighed af deres forskning både til deres lærerkolleger udenfor teorigruppen, og til dekaner, rektorer og forskningråd. Det kan hænge sammen med, at fagets udvikling for blot 25 år siden var velsagtens alle dataloger matematikere med fokus på fx formel sprogteori er gået hurtigere end den interdisciplinære kontakt har kunnet holde til.
En anden grund er, at informationsteknologien har skiftet fokus. Mens anvendeligheden af fx kombinatoriske algoritmer var oplagt, da datamater først og frememst blev brugt til at løse store, professionelle problemer, så er det ikke klart for enhver i dag, hvor teknologiens og økonomiens fokus er hjemmemarkedet: underholdning, multimedier og tekstbehandling. Raghavan kalder det sidste et paradigmeskifte, hvilket dog ikke skal tages som indikator for debattens øvrige niveau.
Så meget om de teknologiske bedrifter. Og så langt rækker enigheden i teoretikernes debat. For det er kerneargument i Karprapporten, at der skal være mere teknologisk afkast og at teoretisk datalogi aktivt bør øge sin indflydelse på de praktiske områder. Her er begrundelsen:
»Hvis vi [øger kontakten], så vil bevillingerne strømme til teoretisk datalogi fra et mange forskellige kilder, unge dataloger vil have gode jobmuligheder og vores felt vil have del i de revolutionære omvæltninger, som edb-verdenen sikkert vil opleve i fremtiden.«
For problemet er penge. I USA er bevillingerne til grundforskning faldet drastisk, og for Karpgruppen ser det ud, som om det er svært at få midler til den type forskning, teoretikerne tidligere har søgt om.
Goldreich og Wigdersons indlæg betegner Karprapporten som en dødsdom for faget. Dets holdning finder de opportunisktisk og naiv og dens anbefalinger forkerte og ekstremt farlige. Den tvinger (specielt unge) forskere til at opgive fagets oprindelige videnskabelige mål ved at legitimere dekaners, afdelinglederes og forskningsråds hensigter i den på kort sigt måske mere profitable retning.
Ifølge Goldreich og Wigderson bør teoretiske dataloger gøre alt andet end at beskæftige sig med »konkrete problemer fra det virkelige liv«. Opgaverne i feltet at forstå begrebet beregning og hvad deraf følger er kæmpestore. De kan kun løses ved anvendelse af de klassiske matematiske dyder: grundigt studium, høje krav til forskningskvalitet, stringent bevisførelse og specielt ved abstraktion bort fra fx konkrete programmeringssprog og arktitekturer.
Mens Karpgruppens anbefaling er at kaste sig over praktiske problemer, så siger Goldreich og Wigderson »Studér teorien!«. Dét er vigigt, og der er mere end nok at rive i.
At man ved denne forskning støder på resultater, der kan anvendes i informationsteknologien som i andre videnskaber , er selvsagt. Disse resultater vil være enorme, men dukke op overraskende og sjældent. Og det rækker feltet til ære, at der altid har været teoretikere, der af sig selv har prøvet at fx implementere en lovende algoritme.
Et andet eksempel er dette årtis imponerende fremskridt i forståelsen af approksimationsalgoritmer. Dette er et kærkomment skoleeksempel. Den oprindelige forskning bag disse resultater, undersøgelsen af interaktive bevissystemer, virkede på de fleste som intellektuel masturbation med udelukkende videnskabelig relevans: den stillede et oplagt og interessant spørgsmål om interaktion mellem forskelligt stærke (men forresten komplet urealistiske) Turingmaskiner.
Det har siden affødt en komplet teori for approskimationsalgoritmer. Det er algoritmer for problemer, som typisk er NP-fuldstaendige, men som man alligevel har brug for at løse, fx Handelsrejsendeproblemet (traveling salesman problem). I stedet for at sætte sig ned og græde over problemets NP-fuldstændighed leder man så efter effektive algoritmer, der kommer tæt på den optimale løsning. Det er ret svært, men selv små forbedringer sparer millioner af dollars i fx flybranchen.
Det viser sig nu, at kompleksiteten af at finde approksimative løsninger for disse problemer lagdeler verden mellem P og NP på en nydelig måde: een gruppe af problemer kan approksimeres vilkårlig godt, mens det i den sværeste klasse er beviseligt lige så svært at approksimere resultatet som at finde den eksakte løsning. Specielt findes der fuldstændige problemer for de enkelte klasser i den forstand, at algoritmer for disse problemer kan oversættes til algoritmer for alle andre problemer i den gruppe.
Den teknologiske gevinst: vi behøver ikke længere at finde ad-hoc løsninger til hvert enkelt problem i klassen men kan udnytte den fælles struktur til algoritmekonstruktion i konkrete situationer. Desuden kan der pga. kendskabet til, hvad der gør approksimationen svær, være mulighed for at ændre den oprindelige problemspecifikation vi ved nu, at Handelsrejsendeproblemets kompleksitet afhænger drastisk af, om afstandsmetrikken er euklidsk eller blot opfylder trekantsuligheden. Det kan være vigtigt at vide for den, der formulerer den konkrete model. Det seneste resultat fra i år kunne faktisk blive en effektiv approksimationsalgoritme for Handelsrejsendeproblemet. I bekræftende fald vil det økonomiske afkast af denne forskning igen være enormt.
Der er flere eksempler på ultrateoretisk forskning, der totalt uventet har givet teknologisk pote vi har allerede nævnt kryptologien. Debattens deltagere kommer med en række andre, hvis fællestræk er
Men der er stor fare i at motivere teoretisk datalogis eksistensberettigelse ud fra dens mere eller mindre tilfældige teknologiske sidegevinster. For i stedet for at betragte sig som hjælpefag for teknologien, bør den teoretiske datalogi betragte sig som hjælpefag for videnskaben som helhed.
For det første studerer mange videnskaber problemer, der udover den oplagte, teknologiske nødvendighed for at konstruere ikke-trivielt programmel på en eller anden måde kræver et formaliseret beregningsbegreb, fx fysikeres behov for at forstå begrebet tilfældighed og simuleret tilfældighed til at konstruere og analysere modeller. Men vi behøver ikke blive i den matematisk-fysiske faggruppe.
Karpgruppen betegner NP-fuldstændighedsteorien som datalogiens kulturelle ambassadør til andre videnskaber (den lærer man om på dAlg). Årligt offentliggøres henved 6000 artikler i 20 andre videnskaber end datalogi felter som biologi, økonomi eller statskundskab med NP-fuldstændighed som nøgleord. Det ville være interessant at sammenligne teoriens udbredelse med andre felters store teorier som Kvantemekanikken eller Evolutionsteorien.
Alligevel er forståelsen for og begejstringen ved begrebet hos studenter og ansatte udenfor teorigrupperne lav. Igen ville det være interessant at drage paralleller til den respekt, andre fags store teorier nyder også blandt fagenes empirikerne eller gymnasielærere.
Goldreich og Wigdesons selvforståelse som dataloger favner endnu bredere. »Hvad kan man finde ud af? beregne? bevise? skrive ned? formalisere?« er fundamentale spørgsmål i den menneskelig søgen efter erkendelse. Et spørgsmål, som man har stillet siden civilisationens begyndelse, og som den teoretiske datalogi i de få år, den har eksisteret, har bidraget enormt til. Det favner fra Turings stopproblem til Chomskys formelle grammatikker til de seneste års resultater om probabilistiske beviser.
Man skal da heller ikke bladre længe danske avisers aktuelle kulturdebat, før man støder på ofte ganske underlødige og misforståede referencer til Gödels eller Turings sætninger. Hvad der kan beregnes er en lige så vigtig del af den offentlige debat som evolutionsteori og kvantemekanik. Men i skarp kontrast til biologi eller fysik gør den teoretiske datalogi intet for at motivere vigtigheden af sine problemstillinger for kulturen og hele samfundet, hverken i den offentlige debat eller overfor bevillingshavere. I dag, d. 23 sept., mens jeg redigere disse linjer, fylder en sådan debat netop det meste af dagbladet Informations videnskabsside ‹ med Turingmaskiner, stopproblem, osv. Men skrevet af en fysiker om en anden fysiker ‹ ordet datalogi forekommer intet sted på siden!
Man bør nok være forsigtig med at opfatte den sidste, »kulturdatalogiske« vinkel som et konstruktivt forslag til at finde flere bevillinger for faget, humaniorakagen er ved at blive lille nok i forvejen. Det er da heller ikke meningen. Meningen er fx at vise en vej til at placere datalogi som fag i skolen (hvorfor har jeg lært om Heisenbergs uskarphedsrelation i stedet for Turings stopproblem i gymnasiet?), men også at ændre datalogiens selvforståelse og billede udadtil. Det sidste turde i lyset af den dalende tilgang til faget på den ene side og begavede unge menneskers forståelige interesser for store spørgsmål på den anden måske gøre det interessant for bevillingshaverne alligevel?
Hvis en personlig relativisering og perspektivering er på sin plads, kan man tilføje, at israelerne Goldreich og Wigderson eksponerer et videnskabssyn og et dannelsesideal, der ikke er kompatibelt med det nytteorienterede amerikanske, der har udbredt sig i den vestlige verden i dette århundredes anden halvdel. Et ideal, vi gerne kalder tysk eller romantisk, og som efter min egen (ganske uvidenskabelige) erfaring stadig stortrives i dagens Israel. Man kan se dette som konsekvens af, at folket Israel i totusinde år i diasporaen har overlevet på sin eneste resurse: kundskab, og der derfor er accept af videnskabens kulturelle nødvendighed. En accept, jeg ikke finder i andre landes samfundsdebat, selv hvor som herhjemme den eneste resurse er viden.
Michael Loui gør den modsatte holdning ganske eksplicit: »Ligesom Molieres Monsieur Jourdain, som til sin overraskelse opdager, at han hele livet brugt prosa og ikke poesi som talesprog, kan det tænkes, at datalogerne en dag opdager, at de er ingeniører og ikke videnskabsmænd«. Ifølge Loui er formålet med videnskab at forstå naturen, mens ingeniørsvæsen direkte kommer samfundet til gode i form af fx fremstilling af datamater. »Forskning i teoretisk datalogi kan sammenlignes med andre grundforskningsområder i ingeniørsvæsenet: forskningen er videnskabelig, men den er ikke videnskab.«
Louis observation er hverken kættersk eller original, selvom den kan være svær at spise for dataloger med en tung matematisk baggrund. Kenneth Galbraiths definition på teknologi, »den systematiske anvendelse af videnskabelig eller på anden måde organiseret viden på praktiske områder«, er helt kompatibel med Louis.
For at tage velfunderet stilling hertil burde vi interessere os for definitionerne af begreberne videnskab og teknologi, omkring hvilke der er en del uenighed. Dertil fattes jeg både plads og kompetence. Vi vil have mest nytte af distinktionen mellem erkendelse versus praksis, dvs. »know-how« og »know-why«. Der er mange andre. Et sidespor, som dog er værd at betræde, definerer de to begreber ud fra deres output, papir (artikler, bøger) versus ting (broer, medikatmenter, etc.). Men det dur ikke,.ifølge en dansk grundbog i videnskabsteori, for indenfor »sektorer af moderne industriel teknologi, [bl.a.] datalogi [...], bliver der således faktisk produceret mange artikler af lignende type som de, der findes inden for videnskabelige discipliner« (min kursivering). Her bliver en definition altså forkastet, fordi den kommer til at definere datalogi som videnskab!
Men man skal holde sig for øje, at hvis datalogiens formål er at producere informationsteknologi, så er den ikke videnskab (hertil skulle den skabe erkendelse). Det kunne man for 20 år siden være ligeglad med, men i dag har den slags afgørelser direkte indflydelse på, hvad der må udgøre en bevillingsansøgning indenfor faget.
Visionen er, at de teoretiske, erkendelsesorienterede discipliner i datalogien om føje år vil være absorberet af de matematiske institutter, hvor de vil være i samme faggruppe som grafteori, kombinatorik og logik. Resten af datalogi vil da være ingeniørsvæsen, der intet har at gøre på et naturvidenskabeligt fakultet. Vi vil senere komme tilbage til udviklingens betydning for uddannelsen.
Uanset, hvor man står i debatten, er man langt hen ad vejen enig i det øgede krav om formidling til kolleger, studerende, andre videnskaber og verden. Mål og midler er dog forskellige.
En af Karprapportens mest fremhævede anbefalinger er konstruktionen af en »algoritmisk værktøjskasse«, altså et bibiliotek af datastrukturer og algoritmer, der implementerer komplekse algoritmer i et moderne programmeringssprog på en »plug-and-play« facon. Det mest fremtrædende eksempel er Ledaprojektet ved Max Planck-instituttet for datalogi i Saarbrücken omkring Kurt Mehlhorn, der blandt meget andet stiller et hav af graf- og strengalgoritmer til rådighed.
Dette er del af en større pakke af anbefalinger, som vi kan sammenfatte som transfer eller flytning af viden til de praktiske områder. Ved siden af programbiblioteker bør der skrives introducerende artikler og bøger om nye teoretiske (algoritmiske) resultater og gøres en større indsats for at give praktiske dataloger et større teoretisk fundament.
Men det er slet ikke så nemt, på grund datalogiens videnskabelige system. Der mangler nemlig tidsskrifter og konferencer, der muliggør publicering af dette arbejde. Idet sådanne resultater diskvalificerer sig fra at blive publiceret i de mest respektable fora, er dette arbejde ikke videnskabeligt meriterende. Debatten er interssant, men sprænger denne artikels rammer. Jeg nøjes her med at nævne bidragene af Goldreich og af Fich, der har gode observationer omkring meriteringssystemets infrastruktur.
På mange måder kan vi i Danmark betragte udviklingen i USA med sindsro. Herhjemme er der med oprettelse af Grundforskningsfonden ikke grund til at tro på, at midlerne til grundforskning skulle beskæres så drastisk som ved NSF. På Daimi er dette synligt med oprettelsen af Brics.
Og dog.
Centraliseringen og politiseringen af forskningsstyringen har også fundet sted i Danmark, med stor fart siden anden verdenskrig. Statens almindelige Videnskabsfond i 1952, forskningsrådene i 1968, Forskningspolitisk Råd i 1989 og endelig et egentligt forskningsministerium i 1993 overtog på forskellige niveauer gradvist hhv. uddelingen af bevillinger og egentlig strategisk styring fra de enkelte universiteters konsistorier. Prisen for dette tab af frihed har været en betydelig forøgelse af de samlede midler, men først og fremmest i form af programbevillinger (dvs. penge, der er fx er knyttet til et specifikt forskningsprojekt, i modsætning til en lektorstilling). Hvis man leder efter en aktuel fremstilling af denne udvikling herhjemme, kan man have glæde af at læse Johan Fjord Jensens essay, hvis fremstillende passager er interessante.
Og Danmark har da også fået sin strategiplan for naturvidenskab fra Forskningsministeriet i 1996. Her er også et afsnit om datalogi, hvor faget defineres som følger: »Datalogiens formål er at etablere en videnskabelig basis for udviklingen og udnyttelsen af informationsteknologien.« Om teoretisk datalogi, lidt senere: »Omvendt finder datalogisk grundforskning af oprindelig udelukkende erkendelsesmøssig karakter ofte overraskende anvendelser«. Det er altså svært at placere rapportens anbefalinger entydig hos hverken Karpgruppen eller Goldreich og Wigderson.
Men der er andet, som kan vække større bekymring. Fra januar 1997 vil der på Daimi blive oprettet en forskerskole i teoretisk datalogi (læs mere om dette i næste nummer af daimiposten). Dens ansøgning falder helt i tråd med Karpgruppens anbefalinger: »Den aktuelle internationale trend mod at indsnævre gabet mellem teori og anvendelser i datalogi er en ledetråd for skolens emnevalg og studieplan.« Og videre, i ansøgningens eneste specielt fremhævede afsnit (p.6): »Brics ph.d.-skolen vil udstyre sine studerende med en solid baggrund i det teoretiske fundament af en række kerneområder med udgangspunkt i Brics¹ aktiviteter. Fra dette fundament vil de studerende blive opfordret til at studere områder af mere anvendt eller eksperimentel natur som mulige områder for afhandlingen.«
Ansøgninen er på disse punkter fuldt på linje med Karprapportens anbefalinger.
Sidste ændring: søndag d. 28. december 1997.