Wästlund om Newcombs paradox

Denna bloggpost är en uppföljare till mitt ett par veckor gamla inlägg Aaronson om Newcombs paradox, till vilket jag nu tillåter mig hänvisa för en sammanfattning av paradoxen. Med det inlägget lyckades jag uppmärksamma vännen och kollegan Johan Wästlund på Scott Aaronsons förslag till lösning, samt trigga honom att fundera vidare kring problemet; jag betraktar detta som inläggets överlägset viktigaste konsekvens så här långt (och vem vet, kanske det rentav visar sig vara det viktigaste inflytande min blogg haft överhuvudtaget... den som lever får se). För var och en som intresserar sig för Newcombs paradox och de filosofiska frågor denna ansluter till vill jag varmt rekommendera läsning av Johans nedteckning av sina funderingar, och nu syftar jag inte på hans initiala reaktion (som visserligen är väldigt rolig, men som istället för att på allvar ta sig an paradoxen snabbt spinner iväg i en diskussion om grammatik och genus), utan på hans andra bloggpost i ämnet, där han fördjupar sig i paradoxen och kopplar den till idén om självmedvetna datorprogram och en kanske ännu svårare paradox som sådana datorprogram verkar ge upphov till, via en variant av Turings halting problem. Jag kan här omöjligt göra rättvisa åt Johans bloggpost, men jag kan i alla fall klippa ut några små smakprov. Här är hans egen telegrafiska sammanfattning av vad bloggposten går ut på:

In this post I argue that the Newcomb experiment is not only feasible, but might very well be significant to the design of intelligent autonomous robots [...]. Finally, as requested by some readers of my previous post, I will reveal my own Newcombian orientation.

(Orden "some readers" syftar här, om jag förstått saken rätt, åtminstone delvis på mig.)

Beträffande Aaronsons förslag till hur Newcombs paradox kan lösas upp, kallar Johan detta "a very neat argument", men hans djupdykning i begreppet kausalitet leder honom till att avvisa förslaget:

Although I like this argument, I don't think it holds.

Jag hoppar här över den argumentation som leder Johan till denna ståndpunkt (men se hans bloggpost!), och nöjer mig med att konstatera att den är såpass bestickande att jag eventuellt tvingas ändra ståndpunkt igen rörande Newcombs paradox; jag har inte bestämt mig ännu. Istället vill jag citera hans sammanfattning av den patologiska situation för intelligenta och självmedvetna datorprogram som han kommer fram till - i hopp om att trigga läsaren att ta del av hur han når dessa slutsatser:

The strange moral here is that once the program becomes aware of its own correctness (the fact that it never concludes that a program is safe if it isn't), it becomes incorrect! Also notice that we have no reason to think that the AI would be unable to follow this argument. It is not only aware of its own correctness, but also aware of the fact that if it thinks it is correct, it isn't. So an equally conceivable scenario is that it ends up in complete doubt of its abilities, and answers that it can't know anything.

The Newcomb problem seems to be just one of several ways in which a self-aware computer program can end up in a logical meltdown. Faced with the two boxes, it knows that taking both gives more than taking one, and at the same time that taking one box gives $1,000,000 and taking both gives $1000.

It might even end up taking none of the boxes: It shouldn't take the small one because that bungles a million dollars. And taking only the large one will give you a thousand dollars less than taking both, which gives you $1000. Ergo, there is no way of getting any money!?

The last paragraph illustrates the danger with erroneous conclusions. They diffuse through the system. You can't have a little contradiction in an AI capable of reasoning. If you believe that 0=1, you will also believe that you are the pope (how many popes are identical to you?).

Aaronson om Newcombs paradox

Igår berättade jag om Scott Aaronsons underbara bok Quantum Computing since Democritus, och om hans charmerande tendens att bjuda läsaren på spännande små utvikningar. En av dessa utvikningar rör det fantasieggande filosofiska tankeexperiment som bär namnet Newcombs paradox. Jag sammanfattade själv häromåret tankeexperimentet med följande ord:

An incredibly intelligent donor, perhaps from outer space, has prepared two boxes for you: a big one and a small one. The small one (which might as well be transparent) contains $1,000. The big one contains either $1,000,000 or nothing. You have a choice between accepting both boxes or just the big box. It seems obvious that you should accept both boxes (because that gives you an extra $1,000 irrespective of the content of the big box), but here’s the catch: The donor has tried to predict whether you will pick one box or two boxes. If the prediction is that you pick just the big box, then it contains $1,000,000, whereas if the prediction is that you pick both boxes, then the big box is empty. The donor has exposed a large number of people before you to the same experiment and predicted correctly [every] time, regardless of whether subjects chose one box or two.¹

Så vad väljer du, att ta den stora lådan, eller båda lådorna? Är du en så kallad one-boxer, eller en two-boxer? I en av de tidiga artiklarna om paradoxen, från 1969, skriver Robert Nozick så här:

To almost everyone, it is perfectly clear and obvious what should be done. The difficulty is that these people seem to divide almost evenly on the problem, with large numbers thinking that the opposing half is just being silly.²

Jag har själv (fram tills nu) inte riktigt kunnat ta ställning inför den spänning mellan å ena sidan kausalt och å andra sidan statistiskt-prediktivt tänkande som problemställningen lyfter fram, och därmed inte kunnat svara på om jag är en one-boxer eller en two-boxer. Därför triggades min nyfikenhet rejält av följande löfte från Aaronson:

I can give you my own attempt at a resolution, which has helped me to be an intellectually fulfilled one-boxer. [Quantum Computing since Democritus, s 296]

Och när jag ser hans argument så sliter jag mitt hår över att inte ha kommit på det själv, för argumentet föreslår ju praktiskt taget sig självt för den som är bekant med antingen Nick Bostroms simuleringsargument (vilket jag är) eller Stuart Armstrongs tankeexperiment med den aggressivt förhandlande nyblivet superintelligenta AI:n (vilket jag också är).

Now let's get back to the earlier question of how powerful a computer the Predictor has. Here's you, and here's the Predictor's computer. Now, you could base your decision to pick one or two boxes on anything you want. You could just dredge up some childhood memory and count the letters in the name of your first-grade teacher or something and based on that, choose whether to take one or two boxes. In order to make its prediction, therefore, the Predictor has to know absolutely everything about you. It's not possible to state a priori what aspects of you are going to be relevant in making the decision. To me, that seems to indicate that the Predictor has to solve what one might call a "you-complete" problem. In other words, it seems the Predictor needs to run a simulation of you that's so accurate it would essentially bring into existence another copy of you.

Let's play with that assumption. Suppose that's the case, and that now you're pondering whether to take one box or two boxes. You say, "all right, two boxes sounds really good to me because that's another $1,000." But here's the problem: when you're pondering this, you have no way of knowing whether you're the "real" you, or just a simulation running in the Predictor's computer. If you're the simulation, and you choose both boxes, then that actually is going to affect the box contents: it will cause the Predictor not to put the million dollars in the box. And that's why you should take just the one box. [Quantum Computing since Democritus, s 296-297]

I ljuset av detta argument ansluter jag mig härmed till lägret av one-boxers.

Fotnoter

1) Jag har här förvrängt mitt eget citat en smula genom att ändra "90% of the time" till "every time", för att bättre ansluta mig till hur tankeexperimentet vanligtvis (och så även i Aaronsons bok) framställs. För den centrala problematiken gör detta inte någon större skillnad. Skälet till att jag i mitt ursprungliga citat talar om 90% är att stycket är hämtat från min recension av William Eckhardts bok Paradoxes in Probability Theory, där författaren insisterar på 90%-formuleringen.

2) Nozicks påstående om "almost evenly" kan jämföras med David Chalmers opinionsundersökning 40 år senare om filosofers inställning till filosofiska spörsmål, där (bland 931 svarande) 21% säger sig vara one-boxers, mot 31% two-boxers (medan återstående 47% kategoriseras under det mer svårtolkade svaret "others").

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]

Sju paradoxer

Min recension av William Eckhardts Paradoxes in Probability Theory har nyss kommit i tryck i Notices of the American Mathematical Society. Paradoxer - överraskande och till synes motsägelsefulla fenomen - hör till det ljuvligaste man kan sysselsätta sig med, både som matematiker och som filosof. Eckhardt tar i sin bok upp sju av dem: domedagsargumentet, den spelande folkmassan, Bostroms simuleringsargument, Newcombs paradox, Newcombs paradox med öppen låda, Large Hadron Collider-spelet, och de två kuverten. Fem av paradoxerna (dem jag länkat till) är kända; de återstående två är sådana som Eckhardt själv formulerat i syfte att kasta ljus över några av de övriga. Alla sju är stimulerande och givande att fundera över. I min recension beskriver jag kort samtliga sju paradoxer, och ger mig in i fördjupade resonemang kring ett par av dem. Som sammanfattande omdöme om Eckhardts bok duger följande stycke ur recensionen:

Eckhardt has no ambition to provide complete coverage of the literature on the five previously known paradoxes. Rather, the task he sets himself is to resolve them, once and for all, and the review of previous studies that he does provide is mostly to set the stage for his own solutions. He claims to be successful in his task but realizes that not everyone will agree about that: in the introductory paragraph of his chapter on Newcomb’s Paradox, he writes that
there exist a variety of arguments both for and against one-boxing but, in keeping with the design of this book, I search for an incontrovertible argument. (Of course it will be controverted.)
The book is a pleasure to read, not so much for Eckhardt’s solutions (which, indeed, I find mostly controvertible) but for the stimulus it provides for thinking about the problems.