En af de sidste af slagsen?

Foto: Brian Flaherty/New York Times.

I New York Times’ netudgave er der i dag en lang portrætartikel om Donald Knuth, den (for mig og andre af min slags) legendariske amerikanske datalog og matematiker, der har så mange store opdagelser på samvittigheden. Jeg har skrevet om Knuth før her på bloggen; han er altid værd at vende tilbage til. Han er gammel nu – den 10. januar bliver han 81.

Knuth-Morris-Pratt-algoritmen til søgning i tekst (som alle, der søger i en tekst med CTRL-F bruger) ig dokumentbehandlingssystemet TeX (som jeg bruger dagligt – i form af LaTeX) er bare to af mange af Knuths bidrag.

Portrætartiklen er i det store og hele præcis (omend jeg ikke er så glad for forsøget på at forklare hvad et højniveau-programmeringssprog er), og den røber, at vi kan regne med snart at se næste bind af The Art of Computer Programming., Til ikke-fagfolk: Dette flerbindsværk er ikke er en bog om programmering, men derimod er en bog om algoritmeteori og langt hen ad vejen en lærebog i matematik (og en god én af slagsen).

Det, der slår mig for alvor, er dog at Donald Knuth måske er en af de sidste af sin slags. Knuth begyndte sin karriere, mens datalogi endnu blev set som en gren af anvendt matematik. Så alene her favner han bredere, end moderne dataloger som oftest gør. Han interesserer sig for musik, sprog, typografi og litteratur og har noget interessant at sige om hvert af disse områder. Og hans måde at publicere på har været en helt anden end den, man ser i dag. Han har ikke publiceret siden 2012 – ikke så sært, for det er meget længe siden, han gik på pension. Knuths publikationer op gennem årene er temmelig få, og også i hans egentlige aktive periode var der år, hvor han ikke publicerede. Andre år havde han kun én publikation, men den var så til gengæld en bog.

I dag laver vi (og jeg er medskyldig her) mere og mere specialiserede kandidater i alle universitetsfagene, og selvfølgelig også i datalogi. Men jeg ville ønske, at vi også kunne stimulere de studerende til også at have en anden slags forbilleder end de hyppigt publicerende og iværksætter-aktive kandidater med formuer af forskningsmidler, der så ofte bliver hyldet i disse år. Jeg tror selv, at det er dét. der skal til for at skabe en ny Donald Knuth-skikkelse.

Logicomix

For hele syv et halvt år siden skrev jeg her på  siden om Frege og nævnte da kort den grafiske roman Logicomix fra 2008, der er skrevet af Christos Papadimitriou og Apostolos Doxiadis og tegnet af Alecos Papadatos og Annie di Donna. Logicomix tager fat på fortællingen om matematikkens grundlagskrise og alt, hvad den afstedkom. Vi møder Gottlob Frege, Georg Cantor, David Hilbert, Kurt Gödel og Ludwig Wittgenstein – men først og fremmest Bertrand Russell. 

Jeg var tidligere i år blevet inviteret til at være gæsteunderviser for Aalborg Katedralskoles 2.k, som er den klasse, min datter går i. Planen var nemlig, at 2.k skulle læse Logicomix i forbindelse med et flerfagligt forløb. Og i dag besøgte jeg så 2.k. På vej dertil skulle jeg have en sandwich, og tilfældet ville, at jeg i sandwich-baren mødte Emil Ottosen, der er adjunkt i matematik (og gammel elev fra Aalborg Katedralskole)! Emil og jeg fik talt lidt om firefarveproblemet, der nok er det problem, der nemmest illustrerer hvorfor der var en grundlagskrise for matematikken sidst i 1800-tallet.

Besøget i 2.k gik vist ikke så dårligt; jeg fortalte om Cantors resultater om uendelighed, Russells paradoks og lidt om typeteori (i Russell og Whiteheads udgave). Eleverne stillede gode spørgsmål og virkede faktisk til at være interesserede. Jeg kunne undervejs ikke lade være med at bemærke, at alle de mest forstyrrede personer i Logicomix – Frege, Cantor, Hilbert, Gödel og Wittgenstein – alle talte tysk.

Det var også godt for mig at møde nogle af dem, vi måske en dag kan møde på universitetet. Desværre fik en elev et voldsomt ildebefindende i en pause og måtte hjælpes ud af klasselokalet. Forhåbentlig har hun det bedre nu.

Enten-eller

I dag, da jeg underviste i Beregnelighed og kompleksitet, undrede flere studerende sig uafhængigt af hinanden over en opgave, jeg stillede, hvor man skulle finde en beregnbar funktion mellem to mængder af strenge, A og B. Det eneste, opgaven fortalte, var at der fandtes strenge, som var elementer i B og andre strenge, der ikke var med i B.

Så kunne man derfor definere funktionen, så den på elementer fra A gav en fast streng u fra B som resultat og fra elementer uden for A gav en fast streng v uden for B som resultat. Funktionen er endda beregnbar, hvis man med en algoritme kan afgøre om strenge er elementer i A. Men de studerende, der undrede sig, syntes at det virkede som snyd. Vi får aldrig at vide, hvad u og v egentlig er. Så vi ved egentlig ikke, hvordan funktionen skal beregnes.

Og jeg måtte give dem ret. Hvis funktionen, som jeg har skrevet ovenfor, er en funktion over de naturlige tal, er den veldefineret og den er endda også beregnelig. Den er nemlig en konstant funktion, og konstante funktioner er nemme at beregne. Vi ved bare ikke, om dens værdi altid er 1 eller altid er 0. Men på en eller måde synes man, at beregningen af funktionsværdien kræver at vi skal vide om der er liv uden for solsystemet eller ej.

I det omfang jeg overhovedet kan siges at være matematiker, er jeg konstruktiv matematiker, og de studerendes betænkeligheder er helt rimelige, hvis man spørger mig. Det store underliggende problem er nemlig, at påstanden Enten er der liv i solsystemet eller også er der ikke har en sandhedsværdi ifølge klassisk logik, men er meningsløs i konstruktiv matematik. I konstruktiv matematik kan jeg nemlig kun bevise en påstand på formen P eller Q ved at præsentere enten et bevis for påstanden eller et bevis for påstanden Q. Så jeg skal enten bevise, at der er liv uden for solsystemet eller bevise, at der ikke er. (Det er lidt svært.)

Børn skal ikke lære at regne!

For en del år siden snakkede jeg med en ung mand i gymnasiealderen, der gik på en Rudolf Steiner-skole. Han havde ikke lært at læse, før han var 12. For indtil da havde han ikke haft brug for at kunne læse! Men nu læste han så til gengæld rigtig meget. Jeg var målløs – kunne han ikke have risikeret at gå gennem livet som analfabet? Men, som han sagde: En dag ville jeg jo alligevel få brug for at læse, og så skulle jeg nok lære det.

Den amerikanske skoleleder Louis P. Bénézet foretog fra efteråret 1929 og frem et eksperiment med ikke at undervise børn på sin skole i New Hampshire i regning, til de gik i 6. klasse – det ville i datidens USA sige, at han ventede til de var omkring 11 år gamle. De skulle til gengæld stadig lære at læse og skrive.

Hans bevæggrund var at børn ikke skal lære noget, før de får brug for det. Børnene skulle stadig lære om tallene, men undervisningen kom i forbindelse med at de blev undervist i de andre fag. På denne måde lærte de f.eks. om sidetallene i bogen. Der var ingen udenadslære af regneregler mm.

Det overraskende resultat var at børnene, der deltog i eksperimentet, faktisk blev bedre til mundtligt og skriftligt engelsk og faktisk også blev bedre til regning og til at ræsonnere om matematiske problemer på deres alderstrin.

Bénézets eksperiment er i sandhed radikalt. Sanjoy Mahajan fra Cavendish Laboratory ved Cambridge University har skrevet en kort artikel om det, og hans konklusion er at det er værd at forsøge igen. Jeg er i syv sind om det er en god tilgang; med de nuværende politiske strømninger med voldsomt fokus på tests vil det under alle omstændigheder næppe være muligt at gennemføre et tilsvarende eksperiment i Danmark.

Det rigtig interessante ved Bénézets tilgang er at udenadslæren er elimineret og at de matematiske kompetencer bygger direkte ovenpå de sproglige – og så er der også en mulig fordel i at eleverne kan koncentrere sig om at opnå få, men store kompetencer ad gangen i stedet for at få hakket skoledagene i stykker.

Sig det med 1000 ord

Til den berømte internationale matematikkongres i Paris i 1900 sagde David Hilbert at

En gammel fransk matematiker sagde: “En matematisk teori anses ikke for fuldstændig før man har gjort den klar, at man kan forklare den til den første, den bedste mand som man møder på gaden”

– citatet er her min oversættelse fra engelsk, efter en artikel i Historia Mathematica af June Barrow-Green og Reinhard Siegmund-Schultze, der prøver at identificere hvem den gamle franske matematiker er. Jeg troede i mange år, at det var Poincaré, men der er faktisk tale om Gergonne, viser det sig.

Men hvor nemt er det egentlig at forklare sine ideer til den første, den bedste, man møder? Det kan såmænd også være svært nok, selv om der er tale om nogen, man kender i forvejen. Da jeg studerede matematik for mange år siden, kunne jeg aldrig forklare familien, hvad det var, jeg havde givet mig i kast med. Senere, da jeg studerede datalogi, blev det faktisk ikke nemmere.

Hvis sproget til forklaringen er engelsk, er der nu en helt konkret test i form en teksteditor, der undersøger om man kun bruger de 1000 mest almindelige ord på engelsk. Editoren skyldes Theo Sanderson, der er biolog og forsker i parasitologi.

Jeg har selv forsøgt at forklare min forskning inden for programmeringssprogsteori på den måde, men det er godt nok svært, for al terminologi er bandlyst. Ordet “program ” er ikke blandt de 1000 mest almindelige ord på engelsk! Det er “type” så til gengæld. Billedet ovenfor viser mit forsøg; det forbudte ord “program” seks gange. Nu spekulerer jeg så på, hvordan jeg kan undgå dét – noget godt svar har jeg desværre ikke fundet endnu. En tilladt udvej er at sætte ordet i anførselstegn, men det er egenlig lidt snyd.

Presburger og hans speciale på 9 sider

Her i ferien har jeg omsider fået tid til at få læst Anita og Solomon Fefermans biografi Alfred Tarski – Life and Logic færdig. Bogen giver et fascinerende indblik i det livlige miljø blandt matematikere og logikere i 1920erne og 1930erne. En af bogens mange sidehistorier er den om Alfred Tarskis studerende Mojzesz Presburger; Tarski var blevet interesseret i hvordan man viser at logiske teorier er afgørbare ved hjælp af den dengang nye teknik, der kaldes elimination af kvantorer. Og som en øvelse i sin undervisning gav han en af sine studerende, Mojzesz Presburger, den udfordring at prøve at vise at teorien for naturlige tal under addition er afgørbar. Dvs. at vise, at der er en algoritme, der kan fortælle os om udsagn som

\forall x. \exists y.y + 1 = x

er sande. Udsagnet ovenfor siger i øvrigt, at for ethvert naturligt tal findes der et naturligt tal, som er dets forgænger. (Dette udsagn er falsk, for det gælder ikke for det mindste naturlige tal.)

Presburger viste at teorien for naturlige tal under addition er afgørbar ved en snedig brug af elimination af kvantorer og den resulterende artikel på 9 sider blev til hans speciale. Nogle mente senere, at dette resultat burde være nok til at give ham en Ph.D. Dette ville i så fald have været en af de korteste Ph.D-afhandlinger nogensinde (det var allerede et kort speciale!).

Mojzesz Presburger forlod dog universitetet og blev ansat ved et forsikringsselskabet. Men man kalder i dag teorien for naturlige tal under addition for Presburger-aritmetik. Og I 2010 opkaldte European Association for Theoretical Computer Science en særlig pris, Presburger-prisen, efter ham. Prisen gives til en ung forsker inden for teoretisk datalogi for banebrydende resultater.

Den meget tragiske del af historien er, at Mojzesz Presburger aldrig nåede at opleve noget af dette. Han døde i Holocaust, formodentlig i 1943.

Bohr-fodbold

Det danske landshold ved OL-finalen i 1908. Det er Harald Bohr på forreste række, hvor han er nummer tre fra venstre.

Nogle har hørt om Harald Bohr, fordi han var matematiker og bror til Niels Bohr. Andre (nok ikke så mange mere) kan huske hans og Johannes Mollerups bog om matematisk analyse, som engang var meget udbredt i Danmark. Mollerup og Bohr er forresten også ophavsmænd til en sætning, der bærer deres navn, og som siger at gammafunktionen er den eneste reelle funktion, der opfylder den funktionalligning, som fakultetsfunktionen ofte defineres ved.

Men inden Harald Bohr blev professor i matematik ved Københavns Universitet var han faktisk også en af sin tids store fodboldstjerner. Han spillede for Akademisk Boldklub, der er i dag er absorberet i FC København, og han var også på landsholdet. I 1908 nåede det danske landshold finalen ved de olympiske lege, hvor de desværre blev slået 0-2 af England. Da Harald skulle forsvare sin doktorafhandling, mødte der efter sigende flere fodboldfans end matematikere op i auditoriet!

Jeg ved, at Lars Bastrup, der i sin tid spillede for HSV i Bundesligaen, var cand.mag i dansk – og mange år senere stiftede han sin egen messianske sekt! Og Klaus Berggren, der også spillede mange kampe på det danske landshold, var cand.merc. Og den brasilianske stjerne Sócrates levede op til sit navn; han var uddannet læge og fik langt senere en PhD-grad i filosofi.

Men vore dages fodboldstjerner er anderledes ubelæste. Er f.eks. Ronaldo, Messi eller Neymar nogensinde blevet set med en bog?

Hilbert og de selvkørende biler

Hilberts syttende problem er

Givet et ikke-negativt multivariat polynomium, kan det da altid skrives som en sum af kvadrater af rationelle funktioner?

Svaret er ja, og beviset herfor blev fundet i 1927 af Emil Artin. Desværre var beviset ikke konstruktivt. Et konstruktivt bevis kom i 1940, og først i 1967 fandt man ud fra hvor mange rationelle funktioner, der skal optræde i kvadratsummen. Konrad Schmüdgen har en lille oversigtsartikel om netop Hilberts syttende problem.

Der er en interessant artikel i Wired, hvor udgangspunktet er en forbindelse til selvkørende biler. Det er nemlig rigtig nyttigt i optimeringssammenhæng at vide, om et polynomium kan antage negative værdier, og her er løsningen til Hilberts syttende problem guld værd – og især da de algoritmer, der giver en kvadratsum, hvis den findes. Og hvis man vil minimere et multivariat polynomium, kan man så prøve at forskyde det langs y-aksen og blive ved, til polynomiet ikke længere er ikke-negativt. Forbindelsen til selvkørende biler kommer fra behovet for hurtigt at kunne beregne minimum af multivariate polynomier, der dukker op i beskrivelserne af selvkørende bilers adfærd (f.eks. et polynomium, der beskriver afstanden til en forhindring).

Det rigtig interessante er egentlig, at det, der tilbage i år 1900 var ren matematisk grundforskning, nu her et århundrede senere har fået nogle meget konkrete anvendelser. Gad vide, om vores nuværende forskningsminister er klar over denne forbindelse mellem grundforskning og anvendelser? (Jeg tillader mig at tvivle.)

Nætter med Tarski

I går fik jeg Alfred Tarski: Life and Logic, biografien om den polsk-amerikanske logiker Alfred Tarski. Bogen er skrevet af Anita Burgman Feferman og hendes mand Solomon Feferman, der begge kendte Tarski godt. Solomon, der selv er logiker, var endda en af Tarskis PhD-studerende ved Berkeley University, hvor Tarski tilbragte det meste af sin karriere efter 1939.

Alfred Tarski rangerer helt deroppe med Kurt Gödel og Bertrand Russell som en stor skikkelse inden for matematisk logik, og hans arbejde inden for semantik af formelle sprog har også haft stor betydning for mit eget forskningsfelt, der er semantik af programmeringssprog. Tilfældet ville, at det faktisk var i dag, jeg holdt sidste kursusgang i “Syntaks og semantik”, hvor emnet var en sætning om eksistens af mindste fikspunkter, som Tarski var med til at finde frem til.

Jeg har selvsagt ikke fået læst bogen endnu, men har selvfølgelig ikke kunnet nære mig for at bladre lidt. Bogen er fuld af anekdoter, kan jeg se. Ud over at være meget egenrådig og dameglad (hans hustru var bestemt ikke den eneste, der fik hans opmærksomhed), var Tarski tydeligvis arbejdsnarkoman, og vel også mere end dét – han var et ekstremt B-menneske, der holdt sig oppe hele natten takket være benzedrin (der er beslægtet med amfetamin). Og så var han storryger. En af hans PhD-studerende, Chen-Chung Chang, fortæller i bogen om hvordan han var hjemme ved Tarski til vejledning. Kl. 21 var Tarski som regel ved at komme op i omdrejninger. Der måtte ikke luftes ud, for den gode Alfred mente at røgen gavnede hans tankevirksomhed. Desværre var Chang astmatiker, men det var der ikke så meget at gøre ved. Ved to-tiden råbte Tarski på sin hustru. Lidt efter kom Maria så med kaffe til de to. Klokken halv fem om morgenen var Tarski stadig i fuld gang, og Chang kom først hjem og ud i den friske luft, når solen stod op!

(Uvilkårligt kommer jeg til at tænke på en polsk gæstelektor, jeg havde i min studietid. Han var storryger og røg hele tiden, mens han forelæste. Nogen Tarski var han dog ikke, men til gengæld var hans kursus ikke obligatorisk!)

Når jeg ser anekdoterne om Tarski i Feferman’ernes bog, kommer jeg til at føle mig usædvanligt almindelig. Der er næppe mange originaler som Tarski i dag, og det er både godt og skidt.

Fomenko

I går besøgte jeg Fredrik Bajers Vej 7G, hvor der er en del datalogi- og software-studerende, der har grupperum. Men indtil sidste år holdt Institut for matematiske fag til der, og jeg havde i den forbindelse selv et kontor der en overgang. Det er specielt at gå forbi den gamle frokoststue, der nu er halvtom, og se de tomme seminarrum med de mange hejsetavler, hvor jeg selv engang har stået og holdt et PhD-kursus i kryptografi. Et billede, jeg ofte har lagt mærke til før i tiden, er et litografi af Fomenko – og i går opdagede jeg at det stadig hang der. Nogen må have glemt det ved den pludselige flytning til Skjernvej. Så jeg tog et billede – helt bogstaveligt – og nu står det indtil videre på mit kontor på Institut for datalogi.

Men hvem er Fomenko så? Anatolij Fomenko er en ukrainskfødt matematiker (fra 1945), der er kendt for sit arbejde inden for differentialgeometri og topologi og i mange år har været professor på Moskvas Statsuniversitet. Og så skriver han også science fiction og tegner.

Noget, der kom bag på mig, er at Anatolij Fomenko også er en meget aktiv pseudohistoriker. Fomenko er nemlig overbevist om at verdenshistorien er fuldstændig løgnagtigt fortalt. Jesus skulle således have levet i det 11. århundrede og være blevet korsfæstet i Konstantinopel i 1086. Aristoteles skulle have levet i middelalderen, og faraonernes Egypten, antikkens Romerrige og Grækenland tilsvarende være frit opfundet af forfattere under Renæssancen! Beretningerne om kong Arthur og Englands tidlige historie er en forvrænget udgave af historien om det tidlige Byzans, der så selv er fabrikeret i den tidlige middelalder. Det der med fund fra oldtiden skal man ikke tro på, for kulstof-14-metoden er helt upålidelig ifølge Fomenko.

Hele denne omfattende konspirationsteori har han beskrevet i et værk på hele syv bind ved navn History: Fiction or Science? 

Dette giver det i forvejen lidt specielle sort-hvide billede endnu en dimension, for vi har i Fomenko endnu et eksempel på hvordan stor dygtighed inden for ét område kan leve sammen med himmelråbende galimatias på et andet. En af de personer, har udtalt sig positivt om Fomenkos pseudohistoriske arbejde, er i øvrigt den tidligere skakstjerne Garry Kasparov.