The War On Drugs

Midt i 1980’erne blev Bruce Springsteen omsider verdensberømt. Omtrent samtidig var der et noget mindre kendt britisk band, der hed The Woodentops. De spillede hektiske små rocknumre med akustisk guitar og billig synthesizer.

For få uger udkom så Slave Ambient af det amerikanske band The War On Drugs. På “Baby Missiles” ovenfor er vi præcis midt mellem Springsteen og Woodentops. Nummeret er ikke karakteristisk for albummet, hvor numre med et traditionelt rockfundament (læs: Springsteen, Dylan, U2, The Verve) ét efter ét dukker op og siden forsvinder i en elektronisk ambient-dis. Værd at lytte til – på én gang tilgængeligt og udfordrende.

Flattr this!

Hvem ejer dine bøger, og hvem må læse dem?

Vi har vores billeder til at ligge på Picasa, og der redigerer vi dem også. Vores dokumenter behander vi hos Google Docs. Vi køber Kindle-bøger hos Amazon. Vi har data, der skal deles, på Dropbox. Snart opretter Apple en iCloud, hvor vi kan placere e-mail, musik osv. Cloud computing, skybaserede tjenester eller hvad man nu skal kalde det, er kommet – og formodentlig for at blive.

Men hvem ejer indholdet af skyen, og hvem må læse med? I en artikel i Technology Review behandler Simson L. Garfinkel dette mildest talt ømtålelige problem. Ligesom det er tilfældet i andre sammenhænge, er lovgivningen ikke klar til at håndtere de problemer, som informationsteknologien har ført med sig.

Et eksempel, som Garfinkel nævner, er en Kindle-bog, som Amazon tilbagekaldte, da der viste sig at være problemer med ophavsretten. Amazon slettede simpelthen bogen hos alle, der havde den i deres Kindle-bibliotek. Tænk, hvis en boghandler gik ind i alle hjem for at hente en bog på reolerne. I dette tilfælde var bogen forresten 1984 af George Orwell.

Der er andre problemer – f.eks. må en Kindle-bog ikke overdrages til andre efter endt læsning, mens antikvariater for fysiske bøger som bekendt har været en realitet længe. Og ejerne af Dropbox-serverne må gerne slette de filer, der ligger der.

En løsning er påkrævet. Måske er det mest oplagt, som Garfinkel da også nævner, at udstrække eksisterende love om opmagasinering til også at omfatte data i “skyerne”. Om dette er en holdbar løsning, er jeg desværre ikke jurakyndig nok til at kunne vurdere.

Flattr this!

Ramsey og de andre

Ligesom rockmusikken har matematikken sine “unge døde”. De fleste kender Galois og Abel, men der er også bl.a. Ramsey. Frank Plumpton Ramsey (1903-1930) var en engelsk matematiker fra Cambridge, der interesserede sig for lidt af hvert – matematisk økonomi, filosofi og matematisk logik. I hans artikel “On a problem of formal logic”, der omhandler afgørbarheden af et fragment af første-ordens-logik, optræder et lille kombinatorisk lemma, som i dag kendes som Ramseys sætning og endte med at danne grundlaget for et område af grafteori, som i dag kendes som Ramsey-teori.

Én måde at formulere Ramseys sætning på er denne (vi antager at $latex 0$ ikke er et naturligt tal).

Lad $latex n \in \mathbb{N}$ og $latex c \in \mathbb{N}$. Lad $latex C = \{ 1,..,c \}$. Betragt $latex \mathbb{N}_n$, mængden af alle delmængder af $latex \mathbb{N}$ med $latex n$ elementer. Betragt en vilkårlig farvningsfunktion $latex f$, der giver hver delmængde én af $latex c$ mulige farver, dvs. $latex f: \mathbb{N}_n \rightarrow C$. Da findes der en uendelig delmængde $latex \mathbb{M} \subseteq \mathbb{N}$ og en farve $latex k$ således at for enhver $latex S \in \mathbb{M}$ har vi at $latex f(S) = k$.

Sagt på mere jævnt dansk, uanset hvordan vi farver $latex n$-delmængderne af de naturlige tal med endeligt mange farver, kan vi altid udvælge en uendelig delmængde af de naturlige tal, således at alle dennes $latex n$-delmængder har samme farve.

Man kan vise, at den udgave af Ramseys sætning, som grafteoretikere kender, er en konsekvens af ovenstående. Se f.eks. Wikipedia for en gennemgang heraf.

Hvorfor så hele denne smøre? Jo, man kan faktisk bruge Ramseys sætning i datalogi til bl.a. at bevise at algoritmer terminerer. Der findes ingen generel strategi i form af en algoritme; det ved vi fra Turing. Men der er nogle bevistaktikker, der ofte dukker op. Ofte bruger man en strategi, hvor man definerer en velordning $latex (\mathbb{O},\sqsubseteq)$, hvor punktmængden $latex \mathbb{O}$ typisk er en mængde af tupler af variabelværdier. Derefter definerer man en funktion $latex f : \mathbb{O} \rightarrow \mathbb{O}$ og viser at $latex f(o) \sqsubset o$ efter hvert gennemløb af algoritmens hovedløkke. Da $latex \sqsubseteq$ er en velordning, betyder det at der engang vil blive fundet en minimal $latex o$-værdi, og da terminerer løkken. Det bøvlede er her dels at finde frem til en god velordning, dels at finde en god $latex f$-kandidat.

Men Cook, Podelski og Rybachenko bruger altså Ramseys sætning til at bevise terminering. Læs deres artikel fra LICS (Logic in Computer Science) eller start med den korte introduktion, som Bill Gasarch har lavet – eller start med at læse indlægget herom på hans blog. Det gjorde jeg selv.

Ramsey nåede ikke at opleve noget som helst af alt dette. Han døde af gulsot få uger inden sin 27-års fødselsdag.

Flattr this!

Hjælp dem i nærområderne

Politiske diskussioner er fulde af afværgebemærkninger. En af de værste, jeg kender, dukker regelmæssigt op, når talen falder på flygtninge og asylsøgere. Den lyder: “Flygtninge skal hjælpes i nærområderne” og bruges typisk som et argument for at afskære adgangen af flygtninge til Danmark. Samtidig forsøger den talende at forsikre, at det skam er vigtigt at hjælpe flygtninge – bare ikke her hos os.

I en tv-debat d. 2. september demonstrerer Pia Kjærsgaard denne brug af afværgebemærkningen:

Med hensyn til asylansøgere er det meget, meget rimeligt, at man behandler i nærområderne. At man finder ud af, om de er berettiget til asyl. I stedet for, at de kommer herop og skal sidde i et asylcenter og får deres ansøgning afvist og derefter får deres sag prøvet igen og igen og igen (…).

(her citeret efter en artikel i Politiken i dag).

Men hvis vi ved et nærområde forstår et naboland til det land, man er flygtet fra, befinder de allerfleste af verdens 16 millioner flygtninge i verden i dag sig allerede i nærområderne. Hvis man også medregner de 27 millioner internt fordrevne (som er mennesker, der er flygtet til en anden del af deres land), er det endnu mere klart. Disse tal kommer fra Dansk Flygtningehjælps oversigt. Langt de fleste flygtninge i verden i dag findes i den fattige del af verden, det såkaldt globale syd. De læsere, der er i tvivl, kan se figuren ovenfor. Det mindretal af flygtninge, som flygter til lande i den rige del af verden, er i ikke ringe omfang de mest resursestærke – de bedst uddannede eller dem, der har kontakter i det land, de flygter til. Og er det ikke de flygtninge, “vi” helst vil have?

En dag bør Dansk Flygtningehjælp og andre, der arbejder for flygtninges vilkår, gør deres for at demontere afværgeflosklen om nærområderne ved at gøre den til navnet på en indsamling.

Flattr this!

Denne film skal jeg se

Jeg er ikke socialdemokrat, men jeg deler den bekymring om den globale opvarmning, som Svend Auken havde – og på mange måder var han en af de sidste fremtrædende idealister i sit parti. Det savner jeg også.

Flattr this!

I en klasse for sig selv

Det er bestemt ikke meningen, at jeg vil skrive om partipolitik her; denne blog er uafhængig af partipolitik – det vigtige for mig er refleksionen og at finde de gode argumenter, så mine indlæg ikke degenererer til indignation eller nedladenhed. Men jeg er nødt til at indrømme det: Jeg er en af dem, der tit har siddet og skummet af vrede, når Dansk Folkeparti har været i medierne eller gjort deres indflydelse gældende. Dansk Folkeparti hævder på den ene side at være “den lille mands parti” og en slags opposition mod “eliten”, mens de på den anden side gør meget ud af at have afgørende indflydelse på beslutninger.

Den nationalistiske politik, Dansk Folkeparti har fået igennem, har fået to konsekvenser. Den første kender vi godt: Det er i dagens Danmark blevet sværere at være indvandrer, flygtning, asylansøger, udlænding eller såmand bare dansker med “anden etnisk baggrund”. Den anden tænker vi ikke på: Den nationalistiske dagsorden, hvor det hele handler om “kulturelle forskelle”, har flyttet fokus væk fra de sociale problemer, der faktisk er tale om i Danmark. Flygtninge på kontanthjælp bliver ikke set som mennesker på kontanthjælp, men som “kulturelt forskellige” og derfor knap nok som mennesker. Andre mennesker på kontanthjælp bliver slet ikke set. Til gengæld taler alle partier om middelklassen og appellerer til middelklassens værdier og bekymringer om boliglån og forbrug. Ironisk nok er middelklassen også truet. Fordi de fleste taler om “kulturelle forskelle”, er der ikke ret megen opmærksomhed om samfundsklasserne i vore dage. Alle vi, der er uenige med Dansk Folkeparti, er begyndt at bruge deres sprog om “kulturelle forskelle” og tror, at det hele handler om det.

Den nationalistiske dagsorden har Dansk Folkeparti selvfølgelig ikke patent på; andre partier herhjemme og andre steder i verden har også taget den til sig. Nationalismen er enkel og slagfærdig, men den skaber skel og gør det umuligt at føre socialpolitik.

I en artikel i The Guardian omtales en undersøgelse, der dokumenterer at den britiske middelklasse er truet på grund af en kombination af den økonomiske krise og en mangelfuld boligpolitik. Flere og flere, der engang tilhørte middelklassen, bliver tvunget ud i fattigdom eller endda hjemløshed i Storbritannien. Og i Politiken i dag skriver Lars Trier Mogensen at

Uligheden i Danmark er vokset gennem 00’erne mellem de kortuddannede ude i landområderne og de veluddannede inde i byområderne. Alligevel fastholder Socialdemokraterne og SF et snævert fokus på middelklassens boligøkonomi.

Protestvælgerne, der gennem mere end ti år har stemt på Dansk Folkeparti – som en forståelig reaktion på det globale jordskælv, der har ramt det danske arbejdsmarked – er blevet taget ved næsen.

Er det ikke på tide, at der bliver ført socialpolitik og måske endda noget så gammeldags som boligpolitik (der ikke handler om redning fra flexlån) i Danmark igen? “Den lille mands parti” gør det nemlig ikke.

Flattr this!

Opdatering: Skolen

I dag var der studiestart på Aalborg Universitet, og 135 nye studerende begyndte på datalogi/software-holdet. Jeg bød dem velkommen (det havde de allerede prøvet flere gange allerede her lige inden middag), og mine gode kolleger fortalte om de kurser, de skulle holde. Til allersidst spurgte jeg – som jeg havde lovet her på bloggen – ud i salen:

– Hvor mange tror I der er på skolen alt i alt?

En hel del hænder røg op og der kom en del forskellige tal.

– Mener du både elever og lærere? spurgte én.

Men til sidst rakte en kvik studerende hånden op – hun gav sig til at sige, at dette faktisk var et universitet, ikke en skole. Tak til hende for at gøre det nemmere for mig at fortælle hele det store hold, at Aalborg Universitet er et universitet og at de nye studerende fra i dag af er – studerende!

Flattr this!

Gödel – altid misforstået

Jeg blev tidligt fascineret af Kurt Gödels resultater om ufuldstændighed; jeg kan huske at jeg lånte en bog om grafteoriens historie, der sluttede af med nogle refleksioner over dette vigtige resultat. Kort tid efter udsendte min daværende Mat 1-vejleder Preben D. Vestergaard sin bog Løste og uløste matematiske problemer, og heri skrev han også om Gödels sætninger. Efterhånden blev jeg opmærksom på at også personer helt uden baggrund inden for matematik – ofte sociologer og andre – begyndte at inddrage Gödels ufuldstændighedssætning i deres diskurs. Alle mulige interessante konklusioner om Guds eksistens, umuligheden af et socialistisk samfund med total retfærdighed og umuligheden af metoder til systemudvikling væltede frem.

Til sidst kom dagen, hvor jeg selv blev i stand til at sætte mig ind i hvad Gödels sætninger udsiger, og fra da af har jeg været træt af misbruget af Gödels sætninger uden for det område, hvor man rent faktisk kan tillade sig at bruge dem. Det gik op for mig, at Gödels resultat om fuldstændighed af førsteordens-logik er et lige så vigtigt resultat inden for matematisk logik. Det er det resultat, der fortæller os at en førsteordens-formel $latex \varphi$ er bevisbar fra hypoteserne $latex \Gamma$ ud fra aksiomerne og reglerne i førsteordens-logik, skrevet $latex \Gamma \vdash \varphi$ hvis og kun hvis $latex \varphi$ er sand i alle de strukturer, hvor alle hypoteser i $latex \Gamma$ er sand, skrevet $latex \Gamma \models \varphi$. Dvs. at bevisbarhed er det samme som sandhed i førsteordens-logik; $\latex \models$ og $latex \vdash$ er den samme relation. Men det er en sætning, ikke ret mange, der ikke har fulgt egentlige kurser i logik kender til.

Men nu tilbage til ufuldstændighedsresultaterne, som der er flere af. Det, de fleste når til, og kløjs i, er det første resultat. Det er det, der siger at der i en “tilstrækkeligt stærk” teori inden for førsteordens-logik findes en formel $latex \varphi$ så $latex \Gamma \models \varphi$ men at vi samtidig har at $latex \Gamma \not\vdash \varphi$. Hvad er så en “tilstrækkeligt stærk” teori? Det er en teori, der ud over de rent logiske aksiomer, der fortæller om kvantorerne ($latex \forall$ og $latex \exists$) og konnektiverne ($latex \vee$, $latex \wedge$ og $latex \neg$) indbefatter Peanos aksiomer for de naturlige tal og principperne om at man kan definere de såkaldte primitive rekursive funktioner over de naturlige tal (eller rettere: funktioner af type $latex \mathbb{N}^k \rightarrow \mathbb{N}$ for alle $latex k$).

Gödels trick er at kode bevisbarhedsrelationen ved brug af de naturlige tal og primitive rekursion. På en måde er hans bevis et meget tidligt Haskell- eller ML-program!

Her er vi allerede langt væk fra sociologi og postmodernisme, som man kan regne ud.

Det bliver ikke bedre for sociologerne med det andet ufuldstændighedsresultat, der siger at man inden for en “tilstrækkeligt stærk” teori (i samme forstand som ovenfor) kan bevise at teorien er konsistent hvis og kun hvis teorien faktisk er inkonsistent.

Sociologiske teorier, politiske anskuelser, religion osv. er ikke formelle logiske teorier. Nogle af dem er ubestrideligt primitive, men der er ikke megen primitiv rekursion over dem af den grund.

Den svenske logiker Torkel Franzén, som jeg i sin tid fulgte på nyhedsgrupperne på Usenet (inden for alle mulige emner lige fra matematik til film) og nogle få gange e-mail-korresponderede med (om småting), var lige så træt af alle misforståelserne af Gödels resultater som jeg er. Men han havde kompetencen og energien til at gøe noget ved det; i 2005 skrev han en bog, Gödel’s Theorem: An Incomplete Guide to its Use and Abuse. Hvis man ikke har kræfter til at binde an med den, kan man starte med Franzéns lille, velskrevne artikel i Notices of the AMS.

Jeg nåede desværre aldrig at møde Torkel Franzén. Han døde i 2006, kun 56 år gammel.

Om Kurt Gödel kan der fortælles meget, men det må vente til en anden dag.

Flattr this!