Dagsaktuellt om termodynamikens andra lag

Olika områden av fysiken verkar lämpa sig olika väl för att belysa mer vardagliga företeelser. När någon försöker sig på att använda kvantmekaniken på det viset landar resonemanget oftast i ren bullshit. Hänvisningar till termodynamikens andra lag (som säger att ett isolerat systems entropi aldrig minskar, och att systemet istället tenderar att utvecklas mot ett tillstånd av maximal entropi - maximal oordning) brukar gå bättre. När datalogen Scott Aaronson nyligen tillgrep termodynamikens andra lag i en kommentar till det fortfarande chockerande faktum att Donald Trump lyckats bli vald till USA:s president,¹ så reagerade jag med omedelbar förtjusning. Så här förklarar han det kanske vanligaste och mest grundläggande fel de väljare gjort som fått för sig att det är i deras intresse att Trump blir president:

[O]ne of humanity’s tragic flaws is to take for granted the gargantuan effort needed to create and maintain even little temporary pockets of order. Again and again, people imagine that, if their local pocket of order isn’t working how they want, then they should smash it to pieces, since while admittedly that might make things even worse, there’s also at least 50/50 odds that they’ll magically improve. In reasoning thus, people fail to appreciate just how exponentially more numerous are the paths downhill, into barbarism and chaos, than are the few paths further up. So thrashing about randomly, with no knowledge or understanding, is statistically certain to make things worse: on this point thermodynamics, common sense, and human history are all in total agreement. The implications of these musings for the present [is] left as exercises for the reader.

Citatet är från Aaronsons bloggpost State den 1 januari i år, men jag är skyldig Luke Muehlhauser ett tack som via sin egen blogg uppmärksammat mig på det. Muehlhauser tillfogar följande skämtteckning som illustrerar samma poäng:

Fotnot

1) Lustigt nog sammanfaller denna Aaronson-hänvisning till termodynamikens andra lag nästan exakt i tiden med en annan sådan, i ett helt annat sammanhang. I hans välskrivna, lärorika och formidabelt kunskapstäta nyss släppta 121-sidiga översiktsuppsats om P kontra NP - måhända det viktigaste öppna problemet i hela matematiken - drar han i Fotnot 20 på sidan 24 en humoristisk men likväl träffsäker parallell mellan termodyamikens andra lag och P≠NP:

I like to joke that, if computer scientists had been physicists, we’d simply have declared P≠NP to be an observed law of Nature, analogous to the laws of thermodynamics. A Nobel Prize would even be given for the discovery of that law. (And in the unlikely event that someone later proved P=NP, a second Nobel Prize would be awarded for the law’s overthrow.)

Scott Aaronsons underbara bok om kvantdatorberäkningar

Jag har nyss läst ut den unge briljante datalogen Scott Aaronsons bok Quantum Computing since Democritus från 2013, och jag rekommenderar den å det varmaste. Utöver att behandla teorin för kvantdatorberäkningar är den i minst lika hög grad en introduktion för den gren av teotetisk datalogi som benämns komplexitetsteori, och som studerar hur resurskrävande (i termer av exempelvis antal beräkningssteg eller mängden minnesutrymme) olika beräkningsproblem är, vanligtvis asymptotiskt då problemstorleken växer mot oändligheten. Komplexitetsteorin kan sägas handla om vilka problem som kan lösas effektivt, och till väldigt stor del är den uppbyggd kring den viktiga men infernaliskt svåra matematiska frågeställningen P kontra NP.¹ Till bokens rikedom bidrar de många utvikningar författaren gör till angränsande områden, som kvantmekanik, relativitetsteori (inklusive avsnitt om huruvida tidsresor är möjliga och vad det i så fall kan väntas ha för konsekvenser för komplexitetsteorin), sannolikhetsteori, kryptologi, antropiska resonemang à la Nick Bostrom, mänskligt medvetande (med precisa och lätt lustfyllda sågningar av John Searles och Roger Penroses respektive bidrag till området), kreationism, och det fantasieggande tankeexperiment som benämns Newcombs paradox och som jag skall återkomma till i morgondagens bloggpost. Mer än en gång ser sig Aaronson manad att leverera disclaimern att han inom fysiken blott är en amatör, men det står klart att i den mån detta överhuvudtaget är sant så är han en extraordinärt bildad sådan. Referensen till Demokritos - den grekiske filosof som verkade under 400- och 300-talen före Kristus och som införde atomteorin - är givetvis en anakronism av rang, men Aaronson begår den av goda skäl.

Genremässigt är boken, som ett slags lite egensinnigt mellanting mellan lärobok och populärvetenskap, en smula svårkategoriserad. Såsom akademiker med min huvudsakliga utbildning inte i datalogi men i ett annat matematiktungt STEM-ämne tror jag att jag har precis rätt sorts bakgrund för att få maximalt utbyte av boken. Det jag framför allt tar med mig från boken är vilket fantastiskt rikt tankebygge komplexitetsteorin utgör, med alla dess intrikata samband i den djungel av olika komplexitetsklasser (jämte ovan nämnda P och NP) som definierats. För mig fungerar också bokens originella stil utmärkt, men jag kan föreställa mig att en och annan läsare kan komma att reta sig på Aaronsons drivna jargong, där ironin sällan är långt borta. Smaka t.ex. på följande inledningsmening på det kapitel i vilket komplexitetsteorin först introduceras:

By any objective standard, the theory of computational complexity ranks as one of the greatest intellectual achievements of humankind - along with fire, the wheel, and computability theory. That it isn't taught in high schools is really just an accident of history. [s 44]

Eller följande inledning till kapitlet om kvantmekanik:

There are two ways to teach quantum mechanics. The first way - which for most physicists today is still the only way - follows the historical order in which the ideas were discovered. So, you start with classical mechanics and electrodynamics, solving lots of grueling differential equations at every step. Then you learn about the "blackbody paradox" and various strange experimental results, and the great crisis these things posed for physics. Next you learn a complicated patchwork of ideas that physicists invented between 1900 and 1926 to try to make the crisis go away. Then, if you're lucky, after years of study you finally get around to the central conceptual point: that nature is described not by probabilities (which are always nonnegative), but by numbers called amplitudes that can be positive, negative, or even complex.

Look, obviously the physicists had their reasons for teaching quantum mechanics this way, and it works great for a certain kind of student. But the "historical" approach also has disadvantages, which in the quantum information age becomes increasingly apparent. For example, I've had experts in quantum field theory - people who've spent years calculating path integrals of mind-boggling complexity - ask me to explain the Bell inequality to them, or other simple conceptual things like Grover's algorithm. I felt as if Andrew Wiles had asked me to explain the Pythagorean Theorem.

As a direct result of this "QWERTY" approach to explaining quantum mechanics - which you can see reflected in almost every popular book and article, down to the present - the subject acquired an unnecessary reputation for being complicated and hard. Educated people memorized the slogans - "light is both a wave and a particle," "the cat is neither dead nor alive until you look," "you can ask about the position or the momentum, but not both," "one particle instantly learns the spin of the other through spooky action-at-a-distance," etc. But they also learned that they shouldn't even try to understand such things without years of painstaking work.

The second way to teach quantum mechanics eschews a blow-by-blow account of its discovery, and instead starts directly from the conceptual core - namely, a certain generalization of probability theory to allow minus signs (and more generally, complex numbers). Once you understand that core, you can then sprinkle in physics to taste, and calculate the spectrum of whatever atom you want. This second approach is the one I'll be following here. [s 109-110]

Fotnot

1) Det som gör sambandet mellan komplexitetsteori och kvantdatorberäkningar särskilt hett är att ett kvantdatorgenombrott kan komma att utöka klassen av problem som vi kan lösa effektivt. Här finns dock utbredda vanföreställningar om hur radikal denna utökning kan väntas bli. Aaronson plockar ned dessa:

From reading newspapers, magazines, and so on, one would think a quantum computer could "solve NP-complete problems in a heartbeat" by "trying every possible solution in parallell," and then instantly picking the correct one.

Well, arguably that's the central misconception about quantum computing among laypeople. [s 145]

Och vad som kraftigt bidrar till denna "central misconception" är missförståndet att primtalsfaktorisering av stora heltal skulle vara ett NP-komplett problem. Det är visserligen sant att problemet tillhör NP, och att de snabbast kända klassiska (dvs icke-kvant) algoritmerna tar exponentiell tid på sig (något som, tack vare Shors algoritm, ett kvantdatorgenombrott skulle ändra på), men detta gör inte primtalsfaktorisering NP-komplett. Aaronson igen:

Over the course of my life, I must've met at least two dozen people who "knew" that factoring is NP-complete, and therefore that Shor's algorithm - since it lets us factor on a quantum computer - also lets us solve NP-complete problems on a quantum computer. Often these people were supremely confident of their "knowledge". [s 64-65]

Datalogi för nybörjare

Den svenska datavetenskapens främste folkbildare - och jag är frestad säga dess svar på Carl Sagan och Richard Dawkins - heter Thore Husfeldt. Missa för allt i världen inte det 26 minuter långa populärvetenskapliga föredrag med honom som Utbildningsradion nyligen spelat in, rubricerat

Utopier i science fiction och datavetenskap.

Föredraget riktas till, och är förmodligen allra bäst lämpat för, en publik som helt saknar bakgrundskunskaper i datavetenskap och matematik, men även för oss som kan lite mer är Thores pedagogiska framställning ytterst njutbar. I centrum för hans föredrag står den obesvarade frågeställning som är den i särklass viktigaste inom teoretisk datalogi - och en av de viktigaste inom vetenskapen över huvud taget - och som bär det något osexiga namnet P vs NP. Frågan gäller huruvida det för en viss, mycket omfattande, klass av problem (inklusive det kända handelsresandeproblemet) går att finna algoritmer som löser dem snabbt och effektivt.¹ Om så är möjligt säger man att P=NP; i annat fall är P≠NP. Det Thore har att berätta om detta hör enligt min mening till de främsta exemplen på sådant som rätteligen hör hemma i folks allmänbildning men som i allmänhet saknas. Två av hans pedagogiska grepp (utöver hans skickliga användande av audiovisuella hjälpmedel) förtjänar att särskilt lyftas fram. För det första har han modet att avstå från att veckla in sig i de formler som krävs för att ge en exakt definitionen av P=NP, och han nöjer sig med att på ett ungefär indikera vad det handlar om. För det andra ansluter han sig till Russells Impagliazzos färgstarkare och mer fantasieggande språkbruk, där P≠NP uttrcks som att vi bor i Kryptomanien, och P=NP som att vi bor i Algoritmika.² De flesta datavetare (inklusive Thore) tror att vi bor i Kryptomanien, men decennier av forskning har inte kunnat slå fast detta, och helt säkert är det måhända inte.

Thore hinner i sitt korta föredrag också ta upp det hypotetiska framtidsscenario som kallas Singulariteten, som innebär en mycket hastig utveckling i samband med att artificiell intelligens tar över människans roll som planetens vassaste tänkare, och som jag ägnat en del uppmärksamhet här på bloggen.³ Han har en stark intuition (om än inte något vattentätt bevis) som säger honom att om vi bor i Kryptomanien så är Singulariteten omöjlig, och han är därför inte särskilt oroad över Singularitetens eventuella följder. Jag delar inte Thores övertygelse på denna punkt, och våra divergerande uppfattningar i denna fråga kom till uttryck i ett meningsutbyte i kommentarsfältet här på bloggen för halvannan månad sedan.

Fotnoter

1) "Snabbt och effektivt" betyder här att det existerar en algoritm vars exekveringstid växer högst polynomiellt i storleken på indata.

2) Impagliazzos klassificering av världar är i själva verket något mer nyanserad än så, och omfattar även de tre intermediära världarna Heuristica, Pessiland och Minicrypt.

3) Thore avslöjar på sin blogg att mina skriverier om Singulariteten bidragit till att han tar upp saken i sitt föredrag. Jag känner mig stolt och smickrad över att ha inspirerat honom på detta vis, och gläds åt varje indikation på att projektet Häggström hävdar inte är förgäves.