Kategoriarkiv: Matematik

Journalist-algoritmer

algoritme

Nogle gange er det underligt at opdage, at et ord, man troede man havde i fred, dukker op i medierne. Inden for de seneste få år er journalister begyndt at interessere sig for – algoritmer. 

En artikel i dagbladet Information af Annegrethe Rasmussen 2014 hedder “Jeg hader algoritmer” – og nej, det var ikke en bandbulle mod quicksort, term-unifikation eller delmængdekonstruktionen for endelige automater. Det kunne nok ellers have været interessant. Nej, det vi får at læse, er en kritik af hvordan webtjenester målretter deres tilbud til brugerne på baggrund af en dataanalyse af brugernes vaner. I denne uge er der en klumme i Information om algoritmer – og denne gang handler den om præcis det samme.

Journalisterne har med andre ord opdaget det, der hedder recommender-algoritmer. Min fornemmelse er at denne meget specielle forståelse af algoritmebegrebet kommer til at dominere og nemt ender med at blive synonym med det for journalisters vedkommende.

Om det i sidste ende er godt, ved jeg ikke. Algoritmebegrebet bør være en helt central del af almen dannelse i vore dage og fortjener (som andre vigtige matematiske begreber) en ordentlig behandling i medierne.

Flattr this!

Matematik som jargon

math10

Nogle gange dukker matematisk terminologi op helt uden for matematiske sammenhænge, nemlig som “smart” jargon. Et amerikansk websted viser en række eksempler på hvordan denne uvane ytrer sig på engelsk. Billedet ovenfor er taget derfra.

Jeg kender også denne form for jargon fra min egen arbejdssammenhæng. Især før i tiden var der personer på mit institut, der talte om de muligheder som et forslag udspænder (et begreb fra lineær algebra) eller om en beslutnings randbetingelser (et begreb fra differentialligninger) eller om en afvigelse på et epsilon (et begreb fra reel analyse). Det har som regel været dem, der ikke selv har brugt matematik i deres akademiske virke, der har været glade for disse ord, og de kommer typisk fra bestemte steder i matematikken. Således har jeg aldrig hørt nogen tale om f.eks. naturlige transformationer (det kunne man nok ellers godt).

Jeg har altid undgået den slags jargon, for i min verden (og jeg bruger matematik stort set hele tiden i mit akademiske virke) betyder disse ord noget bestemt.

Nogle gange hører jeg matematikere bruge matematisk terminologi uden for matematik, men i de sammenhænge bruger de den faktisk korrekt (f.eks. når jeg hører dem tale om en “nødvendig, men ikke tilstrækkelig betingelse”).

Min fornemmelse er at den pseudomatematiske jargon er et forsøg på at lyde præcis uden at være det, dvs. det stik modsatte af hvad der er tilfældet i matematik, hvor tilsyneladende dagligdags ord tildeles meget præcise og veldefinerede betydninger. Måske er det derfor, jeg er så lidt glad for jargon, som jeg er.

Flattr this!

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!