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.

Banebrydende og banalt?

I dag læste jeg en klumme af Susan Knorrenborg, der nu forlader stillingen som debatredaktør på dagbladet Information til fordel for en stilling hos UNICEF. I klummen ser hun tilbage på nogle af de kronikker og andre debatindlæg, hun antog og som siden valgte genklang. Her har hun en meget interessant betragtning, der (så vidt jeg kan se) er fuldstændig generel:

Det slående er, at de mest geniale indlæg; dem, der for alvor vender op og ned på ens verdensbillede, ofte er dem, der hurtigst bliver banale. Det ligger i selve konceptet. De er som et par briller, man ikke kan lade være med at tage på. Man forundres. Hvorefter man vænner sig til sit nye udsyn. Det, der for et øjeblik siden var en afgørende ny tanke, bliver nu ens udgangspunkt. Noget, man tager for givet.

Jeg kom her til at tænke på, at jeg i går igen underviste studerende i det, der kaldes delmængdekonstruktionen i automatteori. Ideen bag konstruktionen er enkel at forklare, og heldigvis lykkes det de fleste studerende at forstå den.

Men hele ideen bag var engang dristig og nyskabende. Det var tilbage i 1959, den amerikanske matematiker Dana Scott og hans polsk/israelske kollega Michael Rabin, der begge var ved Princeton University, publicerede artiklen Finite Automata and Their Decision Problems.   Det var dette arbejde, der mange år senere, i 1976, gav dem Turing-prisen, der er datalogiens svar på Nobelprisen. I denne lille artikel dukker mange af de helt grundlæggende resultater om endelige automater op for første gang.

Derfor er det meget fascinerende at tænke på de dybe ideer fra for knap 60 år siden nu virker så banale, at de er blevet en del af det tidlige pensum på datalogiuddannelserne, ikke kun på Aalborg Universitet, men verden over. Men ideerne er jo netop slet ikke banale; hvis de var det, havde de ikke overlevet.

Derfor er det bedste kriterium for om et forskningsresultat er vigtigt, formodentlig ikke en måling af antal citationer mm. men om resultat en dag ender med at fremstå fuldstændig banalt.

Hvordan lærer man rekursion?

Når jeg holder eksamen i et kursus, kommer jeg altid til at overveje nye tilgangsvinkler til faget, for eksamen markerer ved sin blotte tilstedeværelse, at endnu et undervisningsforløb er slut. Da jeg i efteråret igen, efter et års pause, igen skulle være en af kursusholderne på kurset Programmeringsparadigmer, ved vores kandidatuddannelser i datalogi og software, begyndte jeg igen at overveje hvordan man kan undervise i begrebet rekursion. Rekursion er nemlig helt centralt for dette kursus. Og i disse dage, hvor jeg taler med de studerende om kurset ved mundtlig eksamen, dukker overvejelserne op til overfladen igen. Nogle gange virker det som om rekursion er et stedbarn på vores datalogiske uddannelser på Aalborg Universitet; emnet dukker op mange gange rundt omkring, men det det bliver formodentlig aldrig rigtig grundigt belyst.

Mange mennesker uden for datalogi og matematik kender rekursion fra naturfænomenet selvsimilaritet. Se bare dette romanesco-kålhoved:

Kålhovedet består af en masse mini-kålhoveder, der har samme form som det store kålhoved. Og mini-kålhovederne består af endnu mindre mikro-kålhoveder, der har samme form som mini-kålhovederne. Og så fremdeles.

Christian Rinderknecht, der er en fransk datalog, fik i 2014 publiceret en rigtig interessant oversigtsartikel om de mange forskellige overvejelser og tilgange, der er blevet gjort til at undervise i rekursion.

Det vil selvfølgelig føre alt for vidt at gentage artiklens hovedpointer her; de er mange. Især Rinderknechts redegørelse for undersøgelserne af hvordan børn, unge og voksne forstår rekursion gennem mentale modeller er interessante.

Men to af hans konklusioner slår mig. Den første er at kålhoved-eksemplet i sig har et problem: Det får det til at se ud som om rekursive strukturer er uendelige. Det er de jo ikke; kålhoveder er meget endelige størrelser; et kålhoved kan sagtens være i en stor gryde, et sted i kålhovedet er vi nede på molekyle-niveau, og et kålhoved-molekyle består selvfølgelig ikke af endnu mindre kålhoved-molekyler (faktisk stopper rekursionen jo længe før).

Den anden er at der faktisk er to måder at tænke på rekursion på. Den ene er den dynamiske/procedurelle, hvor man tænker på rekursion som “at kalde sig selv”. Den anden er den statiske/strukturelle, hvor man definerer rekursion strukturelt: At en rekursiv størrelse indeholder “en kopi af sig selv”. Når jeg tænker tilbage, er det nok aldrig lykkedes mig at gøre dette helt klart i min undervisning – men det er vigtigt at skelne og at gøre forbindelsen helt klar. I det sprog, jeg har undervist i, nemlig Haskell, dukker der både rekursive programmer op (og de er dynamiske) og rekursive data op (og de er statiske, Haskells svar på kålhovederne, de rekursive datatyper). Når man skal gennemvandre en statisk rekursiv struktur, f.eks. for at spise et kålhoved, skal man bruge en dynamisk rekursiv strategi, der passer til: Spis kålhovedet ved først at spise hvert af de små kålhoveder. Og så fremderes.