Kategoriarkiv: Matematik

Matematik og datalogi – og krig

p9

På det seneste er jeg begyndt igen for alvor at tænke over de etisk betingede problemstillinger, der er forbundet med forskning, efter at det er kommet frem at der har været samarbejde mellem Aalborg Universitet og BAE Systems, der laver våben og overvågningssoftware og har samarbejde med diktaturstater. Det er underligt at opleve mine kollegers reaktioner og at opleve at AAU fra centralt hold tilsyneladende finder samarbejdet uproblematisk og endda nævner BAE Systems som en officiel samarbejdspartner. I dag opdagede jeg tilmed, at BAE Systems har et opslag oppe på mit institut, hvor de søger efter en studenterprogrammør, der vil hjælpe dem. Jeg talte med den studerende, der havde sat opslaget op. Han måtte indrømme, at det var lidt problematisk, “men det er jo ikke den danske afdeling, der laver den slags ting”, sagde han. Men det er det jo faktisk – det er endda afdelingen i Nørresundby.

I 1992 skrev den danske videnskabshistoriker og fysiker Jens Høyrup fra Roskilde Universitet en artikel, Matematik og krig, og det er en artikel, jeg ofte vender tilbage til. Den er en grundig historisk gennemgang af forholdet mellem matematikkens udvikling og militær teknologi. Artiklen er særdeles kritisk i sin analyse  – dengang for 24 år siden kunne man stadig slippe af sted med at lave kritisk forskning. Høyrup kommer også kort ind på forholdet mellem datalogi (som han betragter som en gren af matematik) og militæret.

Mange vil hævde, at denne forbindelse mellem matematik (bredt anskuet) og krig ikke er et problem. Nogle konkluderer dette ud fra en holdning om at militæret i sig selv er til gavn for samfundet – de færreste (heller ikke jeg) vil f.eks. se det som et problem at Alan Turing bidrog til kryptanalysen af Enigma. Det er dog som bekendt ikke alle anvendelser, der er så tilsyneladende entydigt gavnlige. Andre vil hævde at forbindelsen reelt er “tilfældig” og derfor ikke noget problem.

I artiklen fra Information optræder således dette citat fra AAU:

»En kniv kan bruges til at slå ihjel med. Men det betyder ikke, at vi ikke vil omgås knive, for de kan jo også bruges til meget andet,«

»Jeg tror godt, jeg kan stå inde for, at mine folk ikke har været ude at slå nogen ihjel. De beskæftiger sig med nogle generelle datalogiske metoder, og metoder kan jo bruges til alting.«

Dette er en ofte hørt holdning: Teknologien er neutral og videnskabelig erkendelse er neutral. Måske kan den videnskabelige erkendelse endda drage nytte af militærets interesse?

Men anvendelserne i militæret har, netop fordi de er militære, en negativ indvirkling på videnskaben – og det ikke fordi de kan bruges til at lave våben med, men på grund af denne videns natur. Høyrups har to indvendinger, som jeg synes er vigtige:

  • For det første er militære anvendelser af teknologi produktudvikling og det, som Høyrup kalder “punktuelle”. Der er tale om et udgangspunkt i nogle her-og-nu-behov, der som oftest ikke fører til ny grundforskning.
  • For det andet er militære anvendelser omgærdet af stor hemmeligholdelse. Det står i direkte modsætning til den åbenhed, som altid har været et ideal i den akademiske verden. Et nu legendarisk eksempel er at RSA-kryptosystemet faktisk allerede blev udviklet af den britiske militære efterretningstjeneste GCHQ i 1973, flere år før Rivest, Shamir og Adleman kom på samme idé om en udnyttelse af egenskaber ved endelige ringe i modulær aritmetik.

Det er derfor også på denne måde, at der er noget problematisk ved det samarbejde, som har været mellem AAU og BAE Systems. Historien bag overvågningssystemerne gør det samtidig klart, at de ikke er en “hyldevare” (som en kniv jo er), men tværtimod er udviklet direkte til Saudiarabiens hemmelige politi.

Flattr this!

Intuitionisme og ægteskaber

Intuitionismens fader L.E.J. Brouwer var gift.
Intuitionismens fader L.E.J. Brouwer var gift.

Her er en lille gåde fra The Guardian (oversat til dansk)

Jørgen kigger på Birthe, men Birthe kigger på Preben. Jørgen er gift. Preben er ikke gift. Er der en gift person, der kigger på en ugift person?

Mange er her tilbøjelige til at sige at “det ved vi ikke” – vi ved ikke om Birthe er gift eller ej. Men svaret er ja.

Ræsonnementet er dette. Birthe er enten gift eller ugift. Hvis Birthe er gift, kigger Birthe på Preben – og da er der en gift person, der kigger på en ugift person. Hvis Birthe er ugift, kigger Jørgen på Birthe. Og igen er der en gift person, der kigger på en ugift person.

Men gåden forudsætter det, der kaldes Det Udelukkede Tredjes Princip – for enhver påstand p har vi at enten p eller \neg p er sand. Dette princip afvises af intuitionistiske matematikere (og andre konstruktive matematikere). Begrundelsen er denne: For at en matematisk påstand skal kunne kaldes sand, skal der være et bevis for den. For at en matematisk påstand skal kunne kaldes falsk, skal vi have et modbevis for den.  Men tag et åbent problem i matematik (\mathrm{P=NP}, Riemann-hypotesen eller hvad nu) – for sådanne påstande kan vi ikke hævde at de enten er sande eller falske.

Påstanden “Birthe er gift” er nem at bevise eller modbevise, hvis Birthe er en eksisterende person. Så dette falder ikke ind under klassen af åbne problemer. Men her er en anden udgave, der viser problemet. “Birthe” er her \mathrm{P=NP} .

På et ark papir står der matematiske påstande på nogle af linjerne. Påstanden 2+2=4 står på linjen over \mathrm{P=NP}. Påstanden \mathrm{P=NP} står på linjen over påstanden 2+2=5. Er der en påstand, der står lige over en påstand med modsat sandhedsværdi?

Her vil intuitionisten kunne hævde at vi ikke har oplysninger nok til at kunne svare, mens den klassiske matematiker igen vil svare ja.

Flattr this!

Hvad er det største tal?

poster

På MIT afholdt man i 2007 en konkurrence om at navngive store tal. Nærmere bestemt var det en duel mellem logikerne Agustin Rayo og Adam Elga fra MIT om at kunne give en bestemt beskrivelse af så stort et naturligt tal som muligt. I konkurrencen ville det være usportsligt bare at tilføje “plus 1” til modstanderens bud. Det ville også være usportsligt at komme med beskrivelser som f.eks. “det mindste tal, der er større end noget andet tal som hidtil er blevet beskrevet af noget menneske”; man måtte kun bruge sædvanlig matematisk notation, ikke egne sproglige primitiver.

Og vinderen var… Agustin Rayo. Hans bud var

Det mindste tal større end ethvert endeligt tal som kan beskrives af et udtryk i mængdeteori, som anvender én googol symboler eller færre

Denne beskrivelse kan formuleres i andenordens-logik, og på konkurrencesiden kan man se hvordan dét skal gøres (det kræver Gödel-nummerering!).

Ideen til konkurrencen kom fra en artikel Who Can Name the Bigger Number? af Scott Aronson, der er professor i datalogi, også på MIT. I denne artikel (som bestemt er værd at læse!) kommer Aronson ind på nogle meget store tal, nemlig de tal som den såkaldte busy beaver–funktion definerer. Faktisk angiver denne funktion nemlig en øvre grænse for hvor store tal vi kan beregne.

BB(n) er defineret til at være det største antal skridt som kan foretages af et program med n linjer inden det standser. Funktionen BB(n) er ikke beregnbar – for hvis den var, kunne vi nemt finde ud af om et program standser på et givet input. Vi skulle bare finde ud af hvor mange linjer programmet har og så simulere det i højst BB(n) — hvis programmet så stadig ikke er standset, standser det nemlig aldrig. Og der kan ikke være nogen beregnbar funktion f der for alle n opfylder at f(n) > BB(n). For var der et program, der beregnede en sådan f, ville dette program have m linjer for ét eller andet m, men da ville det højst kunne foretage BB(m) skridt — og bad man så det problem om at beregne f(m) ville det ikke kunne nå at skrive tallet f(m), da det kun ville have BB(m) skridt til rådighed!

Ideen med konkurrencen om at finde det største tal var at gøre studerende interesseret i teorien om beregnelighed (som jeg selv har undervist i engang) og i de filosofiske aspekter af dette område. Det er en rigtig god idé. Hvis der engang bliver lavet en lignende konkurrence på dansk jord, stiller jeg gerne op.

Flattr this!

En travl onsdag

image

Det var en dag med mange møder. Vejledningsmøder først med specialestuderende, så med en gruppe, der laver bachelorprojekt. Sidstnævnte har så hektisk et kursusskema, at de knap nok har tid til at lave projekt endnu. Så fem minutter til at varme mad i, og derefter et frokostmøde på instituttet – det endte med at handle om ferieåret og om finansieringen af uddannelserne. Bagefter et møde med tre matematikstuderende, der følger en miniudgave af Beregnelighed og kompleksitet, der er et kursus jeg ellers ikke holder mere. De havde et snedigt spørgsmål om en opgave, som også jeg måtte gruble en del over inden jeg fandt en god forklaring. Så over til auditoriet og en præsentation af mulighederne for kandidatuddannelser til de studerende på 6. semester.

Til sidst kunne jeg tage mig af korrespondance, cykle hjem og pakke kuffert til morgendagens rejse til Malta. Dagen sluttede med en koncert med Love Shop, som jeg har fulgt siden 1991. Jens Unmack er, som nogle vil vide, en mangeårig ven af mig, og det var godt at se ham og de andre. Det var i øvrigt også en rigtig vellykket koncert.

I morgen kl. 4.30 går det løs igen. Men først skal jeg skynde mig at få sovet. Nogle onsdage er travle. Pyh.

Flattr this!

På tur med Turing

image
Natasja fra UNF i Odense viser kataloget over foreningens mange aktiviteter.

Sidste år fik jeg et brev (et rigtigt brev i en kuvert) fra Ungdommens Naturvidenskabelige Forening (UNF) i Odense. De ville invitere mig til at holde et foredrag om Alan Turings liv og virke; det er et emne jeg tidligere har talt om i UNF i Aalborg og såmænd også på AAU.

I dag var det så tid for mig at rejse til Odense for anden gang i denne måned – første gang var til DM i poetry slam. I weekenden er det så forresten min hustrus tur til at besøge Fyn!

Foredraget var pænt besøgt, og min svigerfar og min svoger, der bor på de kanter, dukkede endda også op. Det er interessant at tale om Alan Turing, og i modsætning til da jeg først holdt et foredrag om ham tilbage i 2012 (100-året for hans fødsel) kan jeg nu henvise til The Imitation Game og til hvad denne film får skildret godt og i nogle tilfælde også mindre godt. Og jeg genså en af mine gamle studerende fra helt tilbage i 1992 (jeg kunne faktisk først ikke genkende ham); han bor nu i Odense.

Efter foredraget snakkede jeg med UNF-folkene og hørte om deres mange aktiviteter. De to næste aktiviteter er dels et foredrag om vigtigheden af sund kost og motion, dels ølsmagning på Fuglsang Bryggeri. Jeg anerkender som bekendt betydningen af alt dette.

Flattr this!

Marvin Minsky er død

Marvin_Minsky_at_OLPCb

Jeg har netop læst at den amerikanske datalog Marvin Minsky døde i denne uge. Han blev 88. Marvin Minsky, der som mange andre af datalogiens pionerer oprindelig var matematiker, var ekstremt optimistisk omkring mulighederne for maskintelligens og var på denne måde en lidt kontroversiel figur inden for datalogi og kognitiv videnskab. Minsky var overbevist om at maskiner en dag ville blive lige så intelligente som mennesker, om ikke mere. Hvad han ville have sagt til denne uges offentliggørelse af at Googles go-maskine kan slå den tredobbelte europamester i go, ved jeg ikke. Enten viser dette resultat nemlig at maskinintelligens er kraftig eller at go faktisk ikke er så svært, som man troede.

Selv stødte jeg på Minskys arbejde gennem en anden side af hans arbejde, nemlig hans bog Computation: Finite and Infinite Machines hvori han formulerer en meget simpel model for beregnelighed, som man kalder Minsky-maskiner (selv kaldte han dem for program machines). En Minsky-maskine er et simpelt program, hvor der er to variable, C_1 og C_2, hvor hver linje har et nummer og der er to slags instruktioner:

l:  C_i :=C_i +1; goto l'

(* her er l: nummeret på programlinjen *)

og

l: if C_i = 0 then goto l' else C_i :=C_i - 1 goto l''

 (* her er l: nummeret på programlinjen *)

Denne simple form for programmer er faktisk tilstrækkelig til at beskrive enhver Turing-maskine og dermed, hvis man tror på Church-Turing-tesen, enhver algoritme.

Flattr this!

En doktordisputats

IMG_5209

I dag var der doktorforsvar på Aalborg Universitet; det sker ikke så tit. Det var min kollega fra Institut for datalogi, Radu Mardare, der forsvarede sin doktorafhandling om logikker og metrikker for Markovkæder – et emne der befinder sig i krydsfeltet mellem teoretisk datalogi og det, man i matematisk logik kalder for modelteori.

De to eksterne opponenter var Ernst Doberkat  fra Dortmund og Gordon Plotkin fra Edinburgh. Flere spurgte mig om jeg kendte Gordon fra min egen tid i Edinburgh for længe siden, og ja det gjorde jeg. Han var faktisk med til mit midtvejsseminar, da jeg var PhD-studerende i Edinburgh i forrige århundrede, og senest skrev han en anbefaling af min bog om strukturel operationel semantik. Netop dét vigtige emne er det faktisk Gordon Plotkin, som er ophavsmand til.

Selve forsvaret startede med et overbliksforedrag, og bagefter var der spørgsmål fra de to opponenter. Det hele varede omkring tre timer. Bestod Radu så? Ja, det gjorde han da.  Tillykke herfra!

(Var det noget for mig at lave en doktorafhandling? Tjo. Jeg vil måske komme med en udtalelse i løbet af de kommende dage/uger/måneder/år. Der er også så meget andet, man skal nå.)

Flattr this!

Teknologisk historieforfalskning alias En onsdag i Reykjavik

IMG_5158.JPGIMG_5160.JPGIMG_5159.JPGIMG_5162.JPGIMG_5156.JPGIMG_5161.JPG

Og så kunne NWPT begynde. Jeg tog bussen ud til Reykjaviks Universitet. Bybusserne i Reykjavik minder forbløffende meget om busserne i Aalborg, kunne jeg konstatere.

Universitetet i Reykjavik blev stiftet i 1988 og privat – det ligger i een stor bygning der ikke er mere end 5 år gammel. Der er også et statsligt universitet i Island, der blot hedder Islands Universitet. Det har jeg desværre ikke set endnu.

Konferencer og workshops er ofte en god lejlighed til at gense gamle kolleger, og denne gang var ingen undtagelse. Jeg fik hilst på Peter Mosses, der i 28 år var lektor ved Aarhus Universitet men nu er professor i Swansea i Storbritannien, hvor han oprindelig er fra. Peter har ydet en masse vigtige bidrag til forståelsen af programmeringssprogs semantik. Interessant nok har han faktisk også en indirekte forbindelse til Alan Turing – Peter var Christopher Stracheys sidste PhD-studerende, og netop Strachey var en af Turings kolleger.

Jeg skulle holde to foredrag i dag, begge om artikler jeg har sendt ind til bedømmelse til konferencer i 2016.

Mit første foredrag var for langt; jeg måtte springe flere slides over og det gik lige vel hurtigt til sidst, syntes jeg. Da jeg en halv time senere skulle holde mit andet foredrag var jeg blevet lidt bekymret for om jeg ville komme til at bruge for megen tid. Men da jeg spurgte ordstyreren (Rocco de Nicola, som jeg havde snakket med dagen forinden mens vi ventede i Københavns lufthavn) kunne han fortælle mig at jeg faktisk havde ti minutter igen. Om foredragene gik godt, ved jeg ikke. Der kom især spørgsmål til det sidste af dem, og det er vel et godt tegn.

Der var foredrag lige indtil kl. 18. Et af de sidste foredrag var med Robin Karsgaard fra Københavns Universitet. Det handlede om reversibel beregning og om at give en kategoriteoretisk model af dette at kunne køre et program “baglæns”.  Det kræver en verden hvor alle beregnbare funktioner skal have en invers. Jeg kan godt mærke at min kategoriteori er rusten, men det var nu spændende.

Efter en lang dag med foredrag er det svært at bevare koncentrationen; det var godt at slutte med en reception og at få snakket med mine gamle kolleger fra Aalborg, Luca Aceto og Anna Ingolfsdóttir, der sammen er hoveddrivkræfterne bag årets workshop. Anna har jeg faktisk kendt siden vores studietid, dvs. helt tilbage til 1983.

Bagefter tog jeg bussen ind til midtbyen og spiste frokost på det lidt cafeteriaagtige men alligevel hippe Gló. Og så var det tid til en gåtur gennem den islandske hovedstad med et besøg i en boghandel. På hylderne med islandsk musik fandt jeg det nye album med – John Grant. Det havde jeg desværre allerede.  Den amerikanske sanger bor heroppe og er åbenbart allerede blevet taget til islændingens hjerter. (Han er nu også god.)

Da jeg nåede tilbage til hotellet, ville jeg skrive dette indlæg. Men min MacBook havde for anden gang i 2015 fået samme fejl. Kablet mellem startdisken og bundkortet var defekt.

Dette indlæg er derfor skrevet delvist på min telefon, delvist i halvmørket i en lokal netcafe om torsdagen på en Windows-computer med et ubekvemt islandsk tastatur og er af den grund udtryk for teknologisk historieforfalskning.

Flattr this!

Alan Turing og standseproblemet

turing-artikel

En af de almindeligste misforståelser i teorien om beregnelighed er at Alan Turing beviste at standseproblemet er uafgørbart. Jeg har desværre selv været med til at viderebringe denne fejlagtige påstand, og mange andre derude bliver ved med at gøre det også – i den bedste mening.

Her er et eksempel fra Benjy Weinbergers blog, der har undertitlen “Computer science and technology demystified”

Although the previous example may seem trivial, Turing applied similar thinking to a more far-reaching computability problem, known as the halting problem. In contemporary terms, the halting problem can be described thus: Left to run without interruption, some computer programs eventually stop running, while other programs continue to run forever. The halting problem asks:

Is it possible to write a computer program that can inspect other computer programs and tell if they run forever or if they eventually stop running?

Turing answered this question with an emphatic NO.

Men sådan er det faktisk ikke. Turing kendte slet ikke til “standseproblemet”. Hvis Det var først i 1958, det vi i dag kender som standseproblemet og som på engelsk kaldes The Halting Problem blev formuleret og vist uafgørbart. Det var den amerikanske matematiker Martin David, der gjorde det.

I den berømte artikel fra 1936, “On Computable Numbers With an Application to the Entscheidungsproblem”, viser Alan Turing at der findes et nummer \beta som ikke er beregnbart og bruger dette i et modstridsbevis for at der ikke findes en algoritme, der kan afgøre om en vilkårlig Turing-maskine er “cirkulær”. Men dette er bestemt ikke standseproblemet, og beviset for at \beta ikke er beregnbart er meget anderledes i sin struktur end beviset for at standseproblemet er uafgørbart.

Hvor fejltagelsen kommer fra, ved jeg ikke. Men den burde overbevise os om at vi nogle gange er nødt til at gå tilbage til de primære kilder.

Flattr this!

Upopulær matematik (og datalogi)

Zentralblatt für Mathematik und ihre Grenzgebiete er i vore dage både en tysk baseret database over artikler fra omkring 2300 matematiske tidsskrifter og en samling af abstracts fra artiklerne herfra. I USA har man det tilsvarende Mathematical Reviews (og dets Internet-udgave MathSciNet) som American Mathematical Society (AMS) står bag. Begge databaser bruger en alment anerkendt klassifikation af de matematiske områder, en 5-cifret klassifikation i hovedkategorier, underkategorier osv. Fordi et stykke forskning kan inddrage flere områder af matematik, kan en artikel have både en primær klassifikation og en sekundær klassifikation.

AMS står derudover bag tre tidsskrifter, Proceedings of the AMS, Journal of the AMS og Transactions of the AMS. Alle tre er generelle matematiske tidsskrifter, dvs. i princippet kan enhver tilpas god matematisk forskningsartikel uanset område blive publiceret.

I 2010 undersøgte den amerikanske matematiker Joseph F. Grcar (hvis område er algoritmiske metoder i matematik) om der er forskel på hvor mange artikler der produceres inden for forskellige matematiske discipliner og hvor mange der optages i de tre AMS-tidsskrifter. Dette gjorde han ved at tage fat i Zentralblatts artikeldatabase, og resultatet blev en artikel i Notices of the AMS.

Her er først et diagram, der viser hvor store procentdele forskellige områder bidrager med inden for Zentralblatts klassifikation.

generelt

Datalogi og partielle differentialligninger fylder godt i det matematiske landskab.

Men her er så en oversigt over hvilken procentdel, de forskellige områder fylder i Proceedings of the AMS.

ams

 

Billedet er et noget andet – det er kommutativ ringteori og abstrakt harmonisk analyse, man ser mest til i Proceedings of the AMS. 

Nogle vil her sige at det ikke er så underligt; mange dataloger sender ikke artikler ind til Proceedings of the AMS (jeg har heller aldrig gjort det; måske skulle jeg prøve?) men til specialiserede tidsskrifter om matematiske emner i datalogi. Men måske er der tale om en selvforstærkende effekt – hvis de “generelle” tidsskrifter skævvrider billedet af faget, kan det ende med at påvirke den almindeligt accepterede opfattelse af hvad der er vigtigt i faget. Dette er da også Joseph F. Grcars bekymring. De generelle publikationskanaler skulle give et overblik over faget, men gør det ikke reelt.

Fra teoretisk datalogi (dvs. datalogi med væsentligt matematisk indhold) kender jeg selv til tilstræbt generelle konferencer som ICALP (International Colloquium on Automata, Languages and Programming) og andre konferencer, der af navn er generelle som STOC (Symposium on the Theory of Computation) men reelt er endt med at blive specialiserede. STOC handler nu om dage kun om algoritmeteori og kompleksitetsteori.

Nogle gange er jeg alvorligt i tvivl om de generelle publikationskanalers berettigelse. Til de generelle konferencer i datalogi er der således kun en lille håndfuld tilhørere, der reelt er interesserede i det bidrag, man kommer med – men samtidig er det ofte de generelle konferencer, der har suverænt mest prestige. I matematik er det bestemt også tilfældet at de tre AMS-tidsskrifter har høj prestige.  Bulletin of the AMS havde i 2014 en impact-faktor på 2,107. Når man får en artikel publiceret i et prestigefyldt generelt tidsskrift, signalerer det at man har “vundet” både over kolleger fra sit eget forskningsområde og over kolleger fra andre områder. Men er det egentlig dét adfærdsmønster, vi gerne vil have, nemlig en konkurrence mellem underdisciplinerne i faget?

Flattr this!