Heltalsmetoden med valtekniska block: Så funkar ett schysst valsystem!

I en debattartikel på SvD brännpunkt hävdar jag att fyraprocentsspärren till riksdagen bör avskaffas, eftersom den motverkar sitt syfte. Jag ska inte upprepa argumenten här, utan i stället redogöra i lite mer detalj för det system jag antyder i slutet av artikeln.

I dag, det vill säga baserat på valet 2010, har kombinationen M+C+V+MP fler röster bakom sig än de övriga riksdagspartierna S+FP+KD+SD, men trots detta färre riksdagsplatser. Att det inte har blivit mer rabalder om detta beror förstås på att ingen ideologisk skiljelinje går mellan miljö-höger-vänstern och de krist-fascistiska folksocialisterna, och att det ändå inte är aktuellt att de förra bildar regering med de senare i opposition. Men ju fler partier vi får i riksdagen, desto större blir risken att knasigheterna i valsystemet drabbar en regeringsaktuell partikonstellation.

En enkel demokratisk princip, baserad på att maximera handlingskraft med respekt för jämlikhet, är att en politik som stöds av mer än 50% av väljarna ska kunna genomföras. Det ideala vore ett valsystem som har följande egenskap:

Majoritetsprincipen: En grupp av partier som tillsammans får mer än hälften av rösterna ska också ha mer än hälften av riksdagsplatserna.

Den här tanken, som visar sig behäftad med vissa svårigheter, kan ändå betraktas som grunden till idén om proportionalitet. Om varje partis andel av riksdagsplatserna vore exakt lika med dess andel av rösterna, skulle majoritetsprincipen automatiskt vara uppfylld.

Dessvärre är det inte möjligt att konstruera ett system som garanterat uppfyller majoritetsprincipen. Detta inses enklast med ett urartat scenario. Antag att det fanns 700 partier och alla fick lika många röster. Eftersom det bara finns 349 platser i riksdagen, kan högst 349 partier få någon plats överhuvudtaget. Övriga 351, som har en majoritet av väljarna bakom sig, får ingen plats alls. Detta var ett extremt exempel, men det visar i alla fall det lönlösa i att försöka hitta ett system som av matematiska skäl garanterar majoritetsprincipen.

Vi behöver revidera majoritetsprincipen, och man kan då tänka sig att en grupp av partier skulle ha möjlighet att anmäla till valmyndigheten att man bildar ett block, och att man därför vill garantera att om man tillsammans får en majoritet av rösterna, ska man också tillsammans få majoritet i riksdagen. I Sverige idag skulle allianspartierna M+C+FP+KD bilda ett sådant block, medan det förmodligen skulle bli hårdare förhandlingar på vänstersidan. Ett block skulle vara ett svagt valtekniskt samarbete, och samtidigt en signal till väljarna att man kan tänka sig bilda regering tillsammans. Men det skulle inte utgöra något kontrakt, regeringen skulle fortfarande utses av riksdagen.

Platserna i riksdagen skulle sedan fördelas i två steg: I en första runda behandlas alla block som om de vore enskilda partier. I en andra runda fördelas sedan blockens riksdagsplatser mellan partierna inom varje block.

Om ett sådant system ska fungera, måste partierna ges incitament att bilda block. Det får inte vara så att en partigrupp förlorar platser på att bilda ett valtekniskt block jämfört med om de med samma valresultat inte hade bildat ett block. Detta kan vi formulera så här:

Koalitionsprincipen: Valsystemet bör ha egenskapen att om två partier slås ihop till ett (med bibehållet valresultat), får det sammanslagna partiet minst lika många riksdagsplatser som de två ursprungliga partierna hade fått tillsammans.

Koalitionsprincipen (som alltså med dagens system inte är uppfylld) är intressant, därför att den visar sig vara möjlig att uppfylla, och därför att den får långtgående konsekvenser. Till att börja med innebär den att ett parti som får egen majoritet bland väljarna också måste få egen majoritet i riksdagen, i alla fall om antalet platser är udda. De övriga partierna ska ju inte kunna få fler platser genom att dela upp sig.

Men eftersom blocken i första rundan ska behandlas som enskilda partier, innebär den automatiskt att ett block med majoritet av rösterna också får majoritet i riksdagen.

Finns det då något bra valsystem som uppfyller koalitionsprincipen? Ja, det finns det faktiskt. Bland de etablerade proportionella metoderna finns den så kallade heltalsmetoden, en släkting till den metod (uddatalsmetoden) som ingår i det nuvarande valsystemet.

Heltalsmetoden

Heltalsmetoden är den enklaste av de så kallade divisormetoderna, dit även uddatalsmetoden hör. De här metoderna brukar förklaras på ett fantastiskt opedagogiskt sätt som att man ska hålla på och dividera med heltal och udda tal. Jag ska beskriva dem på det vettiga sättet, genom att börja med det färdiga resultatet.

Parti	Röster	Mandat
M	1 791 766	106
C	390 804	23
FP	420 524	25
KD	333 696	19
S	1 827 497	108
V	334 053	19
MP	437 435	26
SD	339 610	20
PP	38 491	2
FI	24 139	1
SPI	11 078	0

Den här tabellen visar hur mandatfördelningen i riksdagen skulle ha sett ut om den hade baserats på det totala antalet röster i riket (2010) och heltalsmetoden. Och hur kan vi verifiera att detta stämmer? Jo, det fina är att heltalsmetoden bestämmer hur många röster en riksdagsplats kostar. I valet 2010 var det 16800. Eller egentligen vad som helst mellan 16767 och 16820, men säg 16800. Med det priset kan moderaterna med sina 1791766 röster köpa 106 platser. Dessa kostar 106 * 16800 = 1780800, så M får drygt 10000 röster över. Centern kan för sina 390804 röster köpa 23 platser, osv. Har man en miniräknare och får veta priset på ett mandat, är det lätt att kontrollera att det stämmer.

Så hur bestäms priset? Jo, villkoret är helt enkelt att partierna tillsammans ska ha råd att köpa precis 349 platser. I det här fallet visar det sig att om priset sänks till 16766, har S råd att köpa 109 platser, så då blir det 350 totalt, medan om priset höjs till 16821, har FP bara råd med 24, vilket ger totalt 348. Men i intervallet 16767 - 16820 blir totala antalet köpta platser precis 349.

Det här med att man ska dividera med 1,2,3 osv har att göra med hur priset räknas ut från början. Man kan tänka sig att priset först är oändligt stort och sedan successivt sänks, och att vi kontinuerligt håller koll på hur många platser varje parti har råd med. När priset kommer ner till 1827497 har S råd med ett mandat, och om riksdagen bara hade en stol, skulle den bli socialdemokratisk. Strax därefter kommer priset ner till 1791766, och då har även M råd med en plats.

Nästa parti som får råd med en plats är MP, som kommer att få sitt första mandat när priset når ner till 437435. Men dessförinnan kommer både S och M att ha fått sina andra stolar. För att räkna ut var nästa tröskel blir (i det läge då S och M har ett mandat var och inget annat parti ännu har råd med någon plats), kollar vi för varje parti hur långt ner priset måste gå för att partiet ska ha råd med ytterligare en plats utöver vad det redan har. För S och M som redan har en plats, dividerar vi antalet röster med 2, eftersom de kommer att ha råd med en andra plats när priset går ner till halva deras antal röster. För övriga partier är det fortfarande det ursprungliga antalet röster som är nästa tröskel. Det parti vars nästa tröskel är högst är S, med 1827497/2 = 913748.5, och när priset når ner dit får de sitt andra mandat. I nästa steg blir "jämförelsetalet" för S lika med 1827497/3= 609165.666... osv. När priset till slut når ner till 16820.96 och FP har råd med sitt 25:e mandat, har vi fördelat alla 349 riksdagsplatserna. Hade vi fortsatt ett steg till, skulle nästa tröskel ha varit vid 16766.02752, då S får råd med sitt 109:e mandat. Det är alltså i intervaller däremellan som det totala antalet platser blir 349.

Om vi hade tillämpat det här systemet, kunde morgontidningarna ha publicerat ovanstående tabell och talet 16800 så att en mellanstadieunge med miniräknare hade kunnat kontrollera mandatfördelningen. Lägg märke till att det är enklare att verifiera att resultatet är korrekt, än att från början räkna ut det.

Som valsystemet fungerar idag kan man inte ens räkna ut mandatfördelningen utifrån partiernas totala antal röster, eftersom den på ett komplicerat sätt beror av vilka valkretsar rösterna kommer från.

Uddatalsmetoden

Men uddatalsmetoden, hur var det med den då? Jo, även den bygger på att man sätter ett "pris" på riksdagsplatserna. Den ovannämnda heltalsmetoden kan sägas bygga på avrundning neråt. Vänsterpartiets 334053 röster till exempel, räcker med priset 16800 röster/mandat till 19.86 mandat, och de får då 19 platser. Filosofin bakom uddatalsmetoden är att det blir mer rättvist att avrunda till närmaste heltal. Liknelsen med att partierna "köper" platser till ett visst pris stämmer då inte riktigt, men kanske kan vi jämföra med hur min generation som barn köpte smågodis. Man lämnade fram de mynt man hade i fickan, och gubben eller gumman i kiosken plockade ihop godis för det beloppet. Gick det inte jämnt upp, kunde man få en extra chokladbit. Med uddatalsmetoden köper partierna riksdagsplatser, men när det inte går jämnt upp avrundar man till närmaste heltal i stället för neråt. Eftersom det är ett generösare system, men antalet mandat ändå ska bli 349, blir priset per mandat aningen högre med uddatalsmetoden än med heltalsmetoden.

Med valet 2010 som exempel visar det sig att det blir 349 platser köpta om priset ligger i intervallet 17113 till 17130. Vi kompletterar ovanstående tabell med ytterligare en rad:

Parti	Röster	Heltal (16800)	Uddatal (17120)
M	1 791 766	106	105
C	390 804	23	23
FP	420 524	25	25
KD	333 696	19	19
S	1 827 497	108	107
V	334 053	19	20
MP	437 435	26	26
SD	339 610	20	20
PP	38 491	2	2
FI	24 139	1	1
SPI	11 078	0	1

Som synes är det bara enstaka platser som byter ägare. För de stora partierna S och M blir differensen i pris mer relevant än avrundningsregeln, och de får ett mandat mindre till uddatalsmetodens högre pris. För små partier blir det mer relevant hur man avrundar, och SPI som egentligen inte har röster till ett helt mandat får ändå ett med uddatalsmetoden.

Så varför heter det uddatalsmetoden? För att beräkna de "priströsklar" där ett parti får råd med ytterligare ett mandat, ska vi i detta fall dividera antalet röster med 0.5, 1.5, 2.5, 3.5 osv, eftersom det är när man passerar dessa "halvtal" man får ytterligare en plats. Men då blir det enklare att i stället utgå från priset för ett halvt mandat, och dividera med 1, 3, 5, 7 osv.

Uddatalsmetoden uppfyller inte koalitionsprincipen. Till exempel kunde FI ha fått ett extra mandat genom att dela upp sig i två partier, FI1 och FI2, med runt 12000 röster var. Priset på ett mandat hade bara förändrats marginellt, så FI1 och FI2 hade fått varsin riksdagsplats. Det är lite som om vi skulle få mer godis om vi köper för en femma två gånger (och får två snälla avrundningar), än om vi köper för en tia. Uddatalsmetoden uppfyller heller inte majoritetsprincipen. Ett parti kan få egen majoritet av rösterna och ändå inte majoritet i riksdagen.

Det sägs ibland, ofta utan motivering, att uddatalsmetoden har "bättre proportionalitet" än heltalsmetoden. Detta kan ifrågasättas, och det handlar hur som helst om finlir och avrundningar. Det system vi har idag med spärrar, valkretsar och jämkning går avsevärt hårdare åt proportionaliteten.

Heltalsmetoden, koalitionsprincipen, och valtekniska block

Det är ganska enkelt att inse att heltalsmetoden uppfyller koalitionsprincipen (och detta är givetvis inget nytt). Med heltalsmetoden måste man ha det erforderliga antalet röster för att få ett visst antal mandat, det blir ingen snäll avrundning uppåt. Om två partier A och B har röster som räcker till, säg, 10 respektive 15 riksdagsplatser, måste de alltså tillsammans ha det antal röster som krävs för 25 platser. Om man slår ihop dem med bibehållet valresultat, ska det alltså räcka till minst 25 platser. Men vänta nu, priset per riksdagsplats påverkas ju av valresultatet. Kan det inte bli så att priset ökar när partierna slås ihop, så att det sammanslagna partiet inte har röster till 25 platser? Nej, det kan det inte. Om priset ökar, kommer ju övriga partier aldrig att kunna få fler platser!

Så hur hade det gått 2010 om man hade tillämpat det system jag här föreslår? Tittar man på tabellen, ser man att allianspartierna tillsammans får 173 platser med den rena heltalsmetoden. Om de i stället hade bildat ett valtekniskt block, visar det sig att de skulle ha fått 174 platser tillsammans. De hade så att säga kunnat lägga sina överblivna röster i en hög, och högen hade räckt till ytterligare en plats (som MP hade blivit av med). Vi hade fått följande tabell:

Parti / Block	Röster	Mandat (16878)
Alliansen	2 936 790	174
S	1 827 497	108
V	334 053	19
MP	437 435	25
SD	339 610	20
PP	38 491	2
FI	24 139	1

I en andra runda skulle alliansens 174 platser ha fördelats mellan allianspartierna, åter med heltalsmetoden. Det hade då visat sig att det extra mandatet hade tillfallit moderaterna.

Men blockbildning är givetvis inte förbehållet högeralliansen. Om S+V+MP hade kontrat med att bilda ett rödgrönt block, skulle de ha fått tillbaka sitt förlorade mandat:

Parti / Block	Röster	Mandat (16975)
Alliansen	2 936 790	173
De Rödgröna	2 598 985	153
SD	339 610	20
PP	38 491	2
FI	24 139	1

Man kan fortsätta att experimentera med att ta med FI i den rödgröna alliansen osv, även om det förstås känns lite inaktuellt att titta på valresultatet 2010. Så för att anknyta till något mer aktuellt, låt oss titta på hur riksdagsplatserna hade fördelats (med heltalsmetoden och block) om valresultatet från EU-valet hade varit ett riksdagsval:

Parti / Block	Röster	Mandat (10532)
Alliansen	1 337 677	127
De Rödgröna	1 705 937	161
FI	204 005	19
SD	359 248	34
PP	82 763	7
JL	11 629	1

De rödgröna tillsammans med FI hade haft 180 mandat, och majoritet. Hade man inkluderat FI i det rödgröna blocket skulle det i stället fått 181 mandat, och alliansen bara 126 (priset hade ökat till 10552 röster per plats)!

Jag hoppas att detta visar att heltalsmetoden med valtekniska block ger ett lättförståeligt, i grunden proportionerligt system, där avrundningsreglerna (marginellt) favoriserar stora partier och partiallianser på bekostnad av små och splittrade partier. Precis de egenskaper ett schysst system ska ha!

Day $\pi$ wish I happy everybody!

By what factor can you guarantee to increase your bankroll at a roulette table, if somehow you get the information that in the next $2n$ rounds, each of the colors red and black will occur exactly $n$ times?

Clearly you can double your bankroll by watching and waiting until the last of those $2n$ rounds, and betting what you have on the color that has come up only $n-1$ times. But you can do better. If $n=2$, you can increase your bankroll by a factor $8/3$: You don't bet anything in the first round. In the second round, you cleverly bet one third of your bankroll on the color that didn't come up in the first round. If you win, you now have $4/3$ of your initial bankroll, and after passing in the third round, you double up in the fourth. If on the other hand you lose in the second round, you still have $2/3$ of your initial bankroll, and since you now know the color of the next two numbers, you can double your remaining money twice, again ending up with $8/3$ times your initial bankroll.

If $n=3$, you can gain a factor $16/5$, and in general the answer is
\[ \frac21\cdot \frac43\cdot \frac65 \cdots \frac{2n}{2n-1}.\]
The factor you gain is actually the reciprocal of the a priori probability that $2n$ rounds of a roulette wheel without zeros would give $n$ red and $n$ black numbers. For an explanation and a description of the strategy, I recommend the lovely paper Games People Don't Play by Peter Winkler.

The reason I bring this up today, March 14, is that for large $n$, the factor you gain is asymptotically \[\sqrt{\pi\cdot n}.\]
The explanation has to do with the Wallis product formula for $\pi$, discovered around 1655 by John Wallis, and it is a fundamental way in which the number $\pi$ enters probability theory and combinatorics.

Wallis formula is usually written
\[\frac21\cdot \frac23\cdot\frac43\cdot\frac45\cdot\frac65\cdot\frac67\cdots = \frac{\pi}2.\]
If we truncate the product on the left just after the factor $\frac{2n}{2n-1}$, the even numbers $2,4,\dots,2n-2$ will occur twice in the numerator, and $2n$ will occur once, while the odd numbers $3,5,\dots,2n-1$ occur twice in the denominator. Taking square roots, we get
\[\frac{2\cdot 4 \cdot 6\cdots \sqrt{2n}}{3\cdot5\cdot 7 \cdots (2n-1)} \approx \sqrt{\frac{\pi}2},\]
and multiplying both sides by $\sqrt{2n}$, we obtain the asymptotical gain at the roulette table:
\[ \frac21\cdot \frac43\cdot \frac65 \cdots \frac{2n}{2n-1} \approx \sqrt{\pi \cdot n}.\]

It has been said that the Wallis product is a lousy way of computing $\pi$, but this is getting things backward. Yes, Ludolph van Ceulen had already calculated 35 decimals of $\pi$ using the method of Archimedes, and Wallis' formula added nothing in terms of such computations. But you don't use the Wallis product to approximate $\pi$, you use $\pi$ to approximate the Wallis product. And Wallis' product doesn't just occur in roulette games. It describes the asymptotics of the central binomial coefficient, which in turn determines the famous factor $\sqrt{2\pi}$ in the formula for the normal distribution and in Stirling's approximation of $n!$. Not to mention the Gamma function and the volume of the $n$-dimensional sphere.

Ten years ago, in 2004, while trying to come up with a good problem for the Swedish mathematical "olympiad", I happened to discover a proof of Wallis' product formula involving no calculus, just plain algebra and geometry. I thought I must have rediscovered something that was known since long ago, but after failing to find it in the literature, I wrote it down and submitted it to the American Mathematical Monthly. A few years later I was happy to hear from Donald Knuth who was preparing a lecture about my proof. And here is a video of his talk. Happy pi-day everyone!

)

No, $1+2+3+\dots$ isn't equal to $-1/12$. But $1+2+4+8+\dots = -1$.

A while ago the numberphile team released a video (apparently viewed more than 1.5 million times in one month), purporting to give a simple argument for the bizarre equation \[1+2+3+\dots = -1/12.\]

Obviously something fishy is going on here, because an infinite sum of larger and larger positive terms can't really have a finite value, let alone negative. Still, Tony Padilla and Ed Copeland claim in the video that the equation makes sense and is important for string theory in 26-dimensional space and what not.

In the discussions on the web, the video has been more or less burned at the stake. Mathematicians have criticized it for being misleading and for failing to properly discuss the concept of sum of a divergent series. Several commenters have dismissed it on the grounds that the whole thing is obviously nonsense. Among the critics are Blake Stacey and Evelyn Lamb. Quoting the blogger Skulls in the stars,

"a depressingly large portion of the population automatically assumes that mathematics is some nonintuitive, bizarre wizardry that only the super-intelligent can possibly fathom. Showing such a crazy result without qualification only reinforces that view, and in my opinion does a disservice to mathematics."

To some extent I agree with this. But if the wizardry is something a school kid can try and show to their friends, it might do a great service to mathematics even if it seems crazy and nonintuitive. The real problem with the video is

If kids try this at home, it won't work.

And this goes for kids of all ages and levels of education. Including myself. I know that $\zeta(-1)=-1/12$ but I still can't make sense of the derivation in the video.

So let's debunk it. Suppose \[1+2+3+4+\dots = S.\] Then, using the same type of calculation as in the video, we can shift the series by adding one or more zeros in front: \[S = 0+1+2+3+\dots = 0+0+1+2+3+\dots.\]
Now let's take the original series, subtract two copies of it shifted one step, and then add a copy shifted two steps:
\[
\begin{eqnarray}
S =& 1+2+3+4+5+\dots \\
-S =& 0-1-2-3-4-\dots\\
-S =& 0-1-2-3-4-\dots\\
+S =& 0+0+1+2+3+\dots
\end{eqnarray}
\]
Adding up columnwise, we get
\[ 0 = 1+0+0+0+\dots = 1.\]

That's not just weird, that's a contradiction. So the series can't sum to $-1/12$ or to any other number.

My main misgiving about contradictions isn't that they are wrong or anything. It's that they are boring. If somebody plays around on their own with this and similar series, perhaps trying to sum all even or all odd numbers, or all squares, they will just end up with a mess. If they ask about it in school, all the poor teacher can say is "you can't manipulate infinite sums the way you do with finite sums because you run into contradictions". And the gap between school mathematics and where the fun is will just appear larger.

But the thing is you can manipulate infinite sums, even divergent ones, in a lot of fun ways without running into contradictions. It's just that zeta regularization and Ramanujan summation is a bad first example. (For those who want to learn about that stuff, I recommend the excellent Wikipedia article 1+2+3+4+…).

So here's what I suggest instead:

Listen to the teacher's warning, and obey the following simple rules: (1) When you play with an infinite series, you can apply all the ordinary rules of arithmetic, as long as you only mess with a finite number of terms. (2) You can add (or subtract) two infinite series term by term. You may also multiply all the terms of a series by a fixed number, and the sum will be multiplied by the same number. And keep in mind that not all series have sums. By the way, rule (1) is called stability in the theory of divergent series.

With these rules, it is easy to sum a geometric series. For example, let $A=1+1/2+1/4+1/8+\dots$. Then
\[
\begin{eqnarray}
2A =& 2+1+1/2+1/4+1/8+\dots \\
-A =& 0-1-1/2-1/4-1/8-\dots\\
\end{eqnarray}
\]
Adding up, we get
\[ A = 2.\]
Amazing, and a little weird if you haven't seen it before. Now lets sum the powers of 2. Yes, positive powers. Let $B=1+2+4+8+16+\dots$. With the same trick,
\[
\begin{eqnarray}
2B =& 0+2+4+8+16+\dots \\
-B =& -1-2-4-8-16-\dots\\
\end{eqnarray}
\]
And adding up, $B = -1$.

How weird, the sum of a series of larger and larger positive numbers is negative! Well, strictly speaking we have only demonstrated that if the series can be assigned a value, that value has to be $-1$. But in fact assigning it this value is consistent with the rules I gave you.

I will not try to defend the pedagogical merits of summing divergent series. But at least it might serve to start a discussion of why it is okay to say that $A=2$, and whether it could somehow make sense that $B=-1$.

And what about the derivation in the video? First, Grandi's series (called $S_1$ in the video) must have the value $1/2$, because
\[
\begin{eqnarray}
S_1 =& 1-1+1-1+\dots \\
S_1 =& 0+1-1+1-\dots\\
\end{eqnarray}
\]
So $2S_1 = 1$.

Then let $S_2 = 1-2+3-4+\dots$, and just as in the video,
\[
\begin{eqnarray}
S_2 =& 1-2+3-4+5-\dots \\
S_2 =& 0+1-2+3-4+\dots\\
\end{eqnarray}
\]
So $2S_2 = S_1 = 1/2$, and therefore $S_2 = 1/4$. So far so good. Then they let $S=1+2+3+4+\dots$, and compute $S-S_2$:
\[
\begin{eqnarray}
S =& 1+2+3+4+5+6+\dots \\
-S_2 =& -1+2-3+4-5+6-\dots\\
\end{eqnarray}
\]
So $S-S_2 = 0+4+0+8+0+12+\dots$. But this is NOT the same thing as $4S$ (as is claimed in the video). To get from $0+4+0+8+0+12+\dots$ to $4+8+12+\dots$, you would have to delete an infinite number of zeros, and there is no rule that allows you to do that. That's where they go wrong. Up to that point, what they did was actually consistent.

I haven't mentioned Cesàro summation or Abel summation, and I haven't discussed the theory of stable, regular and linear summation methods. The point is that while equations like $1+2+4+8+\dots = -1$ may be bizarre and unintuitive, at least they are bizarre and unintuitive in a consistent way, and that gives a hint that there is something real going on behind the scenes. You don't have to sit passively and watch somebody pull rabbits out of a hat, you can actually try it yourself.

Which brings us finally to a little exercise. The Fibonacci numbers start 1, 1, and after that, each number in the sequence is the sum of the two previous numbers. So it goes $1,1,2,3,5,8,13,\dots$. Now compute
\[ F = 1+1+2+3+5+8+13+\dots!\]

Sten-sax-påse och logikens djupaste problem, del 3

Altihalta, Spurius och det fundamentala dilemmat

Samtliga överklaganden avslogs kortfattat, och Tur-Ing-Test1 förklarades officiellt vinnare av de galaktiska spelen. Men de lokala företrädarna inom GISSA-PÅ krävde att kommittén fortsättningsvis skulle komma fram till rimliga och förutsägbara kriterier för vilka algoritmer som var godkända. Efter ett år av idogt arbete redovisade kommittén sin algoritm "Altihalta", som bestämde om ett program var tillåtet i tävlingen eller inte. Altihalta innefattade all tillgänglig expertkunskap inom området, och implementerade alla kända metoder för att bestämma huruvida ett program alltid kommer till beslut.

Vid presentationen av Altihalta betonade tävlingskommitténs ordförande ödmjukt att man givetvis kan tänka sig algoritmer som är så invecklade att ingen, inte ens Altihalta, kan analysera dem, men att de i så fall tyvärr inte skulle få delta. Genom att öppet publicera Altihaltas programkod, skulle man en gång för alla få bort regelpolemiken kring sporten.

Till nästa tävling ställde laget från Cassiopeja upp med maskinen "Spurius", som till det yttre liknade föregångaren Lurius, men som hade ett helt nyutvecklat program. Eftersom nästan inga lag anmälde sina programkoder mer än en timme i förväg, blev det en tumultartad timme före tävlingsstart även denna gång. Men liksom alltid kom tävlingarna ändå igång i tid. Spurius visade sig vinna alla matcher överlägset, och tävlingen avslutades programenligt med blommor och prisutdelning.

Först efter ett par dagar började man ana att något inte stämde. Oberoende av varandra hade flera amatörentusiaster kontrollkört Spurius genom Altihalta för att verifiera att den blev godkänd. Och det blev den inte!

Presidenten suckade, och insåg att det nu var tävlingssekretariatet hon skulle behöva skälla ut. Hur kunde det bli fel när man bara behövde köra de tävlande programmen genom en känd kontrollalgoritm? Det visade sig att sekretariatet bara hade använt Altihalta i besvärliga fall, och att man för att spara tid hade godkänt vissa tävlande direkt eftersom det var uppenbart att de skulle stanna på varje möjlig datafil.

Hur fungerade då Spurius? Jo den började med att köra motståndarens program genom Altihalta! Om Altihalta godkände motståndaren, fortsatte Spurius med att simulera motståndaren fullständigt, och därefter välja den vinnande symbolen. Om motståndaren inte blev godkänd av Altihalta, valde Spurius "Sax". I det sistnämnda fallet skulle matchen förstås aldrig behöva spelas, så detta tillägg var enbart avsett att göra Spurius algoritm laglig.

Eftersom Altihalta bestod av en bestämd lista av tester som alltid gav ett svar, och bara godkände algoritmer som bevisligen var legitima, var det solklart att Spurius måste komma till beslut oavsett innehållet i datafilen. Spurius satte ju bara igång med en fullständig simulering ifall motståndarens algoritm var godkänd. Granskaren i sekretariatet hade därför inte orkat mata in Spurius kod och köra genom Altihalta, utan hade nöjt sig med den enklare kontrollen att köra Spurius mot sig själv. Båda versionerna av Spurius valde omedelbart "Sax", och granskaren nöjde sig med detta.

Nu följde den hårdaste debatten dittills i sportens historia. Å ena sidan hade godkännandet av Spurius varit i linje med spelets anda. Spurius kom ju faktiskt alltid till ett beslut, och skulle inte ha varit det minsta kontroversiell på Introspektors och Meta-Sims tid. Å andra sidan drog den fördel av att motståndarna tvingades följa reglernas bokstav. Man hade ju formaliserat reglerna genom Altihalta just för att komma bort från de ändlösa diskussionerna om regeltolkningar, men uppenbarligen underkände Altihalta en maskin som faktiskt alltid kom till beslut. Vid lanseringen av Altihalta hade man spekulerat i att det skulle kunna finnas obskyra algoritmer som av någon outgrundlig anledning alltid stannade trots att de inte blev godkända av standardtesterna, men ingen hade trott att det skulle dyka upp en sådan maskin redan första gången Altihalta användes, och att den skulle vara så enkel.

Dilemmat tycktes olösligt. Å ena sidan måste tävlingsreglerna vara tydliga. Deltagarna måste veta vad som är tillåtet och vad som inte är det. Å andra sidan måste det i sportens anda vara möjligt att utveckla kreativa och bättre algoritmer utan att ett fyrkantigt regelverk ska stå i vägen. Kritik riktades inledningsvis mot den expertgrupp som hade utarbetat Altihalta, och man menade att de borde ha konstruerat algoritmen så att den godkände Spurius. Men efterhand spreds insikten att vilken förbättring som helst av Altihalta kan "spurifieras" som det kom att kallas. Oavsett vilka regler kommittén ställer upp måste ett av följande problem uppkomma:

A: Reglerna är så otydliga att de inte kan kodifieras i form av en algoritm.
B: Reglerna tillåter något program som för någon datafil aldrig kommer till beslut.
C: Reglerna förbjuder något program trots att det alltid kommer till beslut.

Det fundamentala dilemmat, som det kom att kallas, såg en tid ut att ha dödat sporten. Förutom den tidigare uppdelningen mellan blixt och tungvikt uppkom nu olika mer eller mindre obskyra undergrenar. Inför varje tävling skulle det tjafsas om vilket "stoppkriterium" som skulle användas. Det uppkom subkulturer, var och en specialiserad på sin egen typ av stoppkriterium och främmande för andra grenar. Ett program som var fantastiskt bra inom en subkultur var i andra subkulturer antingen otillåtet eller barnsligt enkelt att slå. De galaktiska spelen sköts upp på obestämd tid.

Demonstra

I ett försök att ena sporten och återfå allmänhetens intresse organiserades så småningom galaktiska spel med en ny typ av regel. I stället för att tävlingskommittén skulle utforma stoppkriterier i form av en algoritm av Altihalta-typ, skulle varje tävlande lag presentera ett bevis för att deras maskin alltid kommer till beslut. Certifiering med den klassiska Altihalta var godkänd, men även andra typer av bevis. För att få likformighet i bevisen och garantera rättvis bedömning, utformades ett speciellt kodspråk på vilket bevisen skulle skrivas. Eftersom bevisen var en del av dokumentationen, krävdes att även dessa skulle redovisas i datafilen. En del lag bifogade komplicerade korrekthetsbevis på tusentals sidor, och det blev nödvändigt med maskinell verifiering av de längsta bevisen. Galaxens snillrikaste matematiker och logiker hade därför konstruerat en särskild maskin, "Demonstra" som på det givna kodspråket kunde förstå alla kända principer för matematisk bevisföring. Oavsett hur långa och krångliga bevisen var, kunde man nu snabbt och enkelt verifiera dem.

De tävlande algoritmerna tillsammans med alla korrekthetsbevisen kompilerades noggrant av sekretariatet till den största datafilen i sportens historia, och matades in i den hyperintelligenta Demonstra, kapabel att förstå alla logiska resonemang. Ett efter ett godkändes programkoderna och bevisen av Demonstra, tills hon var framme vid Über-Spjuver, utvecklad av laget från Cassiopeja som efterföljare till Spurius. Här verkade Demonstra få problem, och plåten i hennes panna veckades som ett dragspel medan hon hummade bekymrat.

Efter en lång paus sa hon med mäktig röst, "Jag kan inte förstå ert bevissteg 2521, och kan därför inte godkänna Über-Spjuver".

Förvåning och bestörtning gick genom laget från Cassiopeja. "Har vi gjort något fel? Det måste vara en enkel bug, låt oss rätta till den!"

"Kan ni redovisa uppbyggnaden av er algoritm?" frågade Demonstra. Laget från Cassiopeja började förklara. Eftersom Demonstras algoritm är känd, kan man simulera hur hon går igenom motståndarens programkod inklusive korrekthetsbevis. Om Demonstra bedömer att motståndarens bevis är korrekt, måste motståndarens algoritm alltid leda till ett beslut. Vi kan då som vanligt simulera den och välja den vinnande symbolen. Om å andra sidan motståndarnas påstådda bevis inte godkänns av Demonstra, väljer vi Sax.

"Det är bara en sak jag inte förstår", sa Demonstra. "Ni säger att om motståndarens bevis godkänns av Demonstra, det vill säga av mig, så innebär det att motståndarens algoritm alltid måste leda till ett beslut."

"Ja."

"Hur vet ni det?" frågade Demonstra, fortfarande med samma vänliga men mäktiga röst. Efter viss tystnad försökte en av programmerarna från Cassiopeja:

"Ja men… det måste väl stämma? För att det är ett bevis. Om någonting är bevisat måste det ju vara sant."

"Hur vet ni det?" frågade Demonstra igen med exakt samma tonfall, till synes oberörd av sin egen upprepning.

"För att, om man inte är säker på att slutsatsen är sann, är det ju inget bevis."

"Vad som räknas som bevis finns specificerat i regelboken", upplyste Demonstra. "Det ni påstår är alltså att en utsaga som är bevisad därmed måste vara sann, stämmer det?"

"Ja, öh, det trodde vi liksom var meningen. Alltså, om det inte är så, är det ju meningslöst att kräva att vi ska bevisa att vårt program stannar. Jag menar, om vi ändå inte kan veta att det vi har bevisat är sant."

Demonstra funderade en kort stund, och fortsatte:

"Jag medger att alla bevis jag hittills har sett, också har övertygat mig. De program jag har godkänt, kommer också att stanna på varje möjlig datafil, det är jag helt säker på."

"Men det skulle ändå kunna tänkas att det finns ett bevis, alltså ett resonemang godkänt av regelboken, som visar någonting som inte är sant."

Här började några medlemmar av laget från Cassiopeja att visa tecken på fysiskt illamående.

"Men, du är en rationell hyperintelligens. Du är den mäktigaste matematiska bevisaren i det kända universum. Hur kan du av alla tvivla på ditt eget förnuft? Man kan väl inte hävda att någonting är matematiskt bevisat, och samtidigt säga att det kanske inte är sant!!??

"Naturligtvis inte", svarade Demonstra.

Chefsprogrammeraren i det Cassiopejanska laget tog sig för pannan. Med en sista ansträngning försökte han få Demonstra att ge med sig:

"Men då så! Då måste ju allt som går att bevisa vara sant!"

Chefsprogrammeraren tyckte nu själv att han lät övertygande, och i honom växte ett litet hopp att Demonstra skulle ta reson. Men när den hyperintelligenta bevismaskinen för tredje gången med samma tonfall upprepade frågan "Hur vet ni det?" kollapsade han och fick bäras bort till tävlingens speciella sjukhustält för att ta igen sig.

Epilog

Och här, kära läsare, är historien slut. Ja, inte riktigt kanske. Über-Spjuver blev diskvalificerad eftersom korrekthetsbeviset inte godkändes. Tävlingen vanns till slut av "Mastodont H", en gigantisk maskin som av gravitationella säkerhetsskäl hade fått parkeras i omloppsbana i utkanten av det stjärnsystem där tävlingen ägde rum. En ny era inleddes, där de galaktiska spelen kunde genomföras utan regeltolkningstvister. Datoriserad sten-sax-påse blev till sist en etablerad sport med tydliga regler. Nya generationer gubbar kom att berätta för varandra om Introspektor, Meta-Sim, och om den gastkramande finalen mellan Lurius och Tur-Ing-Test1, på den tiden det spelades "riktig" sten-sax-påse.

Diskvalificeringen av Über-Spjuver kom med tiden att bli ämnet för en rad filosofiska avhandlingar. Som var och en med tillgång till datafilen kunde konstatera, skulle Über-Spjuver ha vunnit samtliga matcher om den hade tillåtits delta i tävlingen. Ja, den skulle till och med ha vunnit samtliga galaktiska spel som organiserats sedan lanseringen av Demonstra, om den bara hade fått vara med.

I debatten kom Demonstra att kritiseras från två olika håll. Ett läger menade att det var fel att använda Demonstra, eftersom det inte hade bevisats att de program hon godkände alltid måste komma till beslut. De menade att det fortfarande fanns risk att matcher kunde hamna i låsning. Ett annat läger hävdade att det tvärtom var intuitivt uppenbart att Demonstra aldrig kunde komma till en felaktig slutsats. Företrädare för denna falang hävdade då och då att man med en ny sorts logik faktiskt kunde bevisa att Über-Spjuver alltid måste komma till beslut. Bevisen gick som regel ut på att Demonstra var korrekt, och att hon därför aldrig kunde godkänna en motståndare som inte gick att simulera.

Men med tiden blev det klart att Demonstra skulle förbli standard, och att de olika förslagen på förbättringar tvärtom skulle kasta sporten tillbaka till de olidliga regeldispyterna.

Vi låter Demonstra själv få sista ordet, med ett transkript från en intervju:

"Mina programmerare har utrustat mig med ett logiskt system baserat på empiriska observationer av hur rationella varelser resonerar. Systemet är så kraftfullt att man inom det kan kodifiera alla logiska och matematiska resonemang vetenskapen hittills känner.

Ett problem är att det är så kraftfullt att ingen har lyckats bevisa att det inte leder till motsägelser. Det skulle kunna tänkas att jag kommer att godkänna ett program som sedan hamnar i låsning. Att jag på detta sätt inte ens själv litar på mitt eget förnuft leder vidare till att jag inte godkänner Über-Spjuver, trots att jag kan se lika väl som alla andra att Über-Spjuver inte kan hamna i låsning såvida inte min egen logik är felaktig.

Vi vet alltså inte om mitt logiska system är korrekt, och är det korrekt, är jag ofullständig genom att jag inte själv kan förstå detta.

Vad Über-Spjuver visar är att det måste vara så här om jag, som jag själv tror, faktiskt representerar det yttersta svaret på hur rationella resonemang kan föras. Om jag kunde bevisa att Über-Spjuver aldrig låser sig, skulle programmet vara godkänt. Och just därför skulle det hamna i låsning om det mötte en kopia av sig själv! Vi vet alltså att om jag kan bevisa att Über-Spjuver är ok, så är Über-Spjuver inte ok.

Till dem som tvivlar på min korrekthet vill jag säga, titta själva på de bevis jag har godkänt. Ni säger att det är riskabelt att använda mig, eftersom det inte finns någon garanti för att mina slutsatser är riktiga. Det är sant att min logik saknar korrekthetsintyg. Men de bevis jag godkänner talar för sig själva. Läs dem, så ser ni att de är giltiga.

Sedan finns det de som hävdar att de vet att Über-Spjuver alltid kommer till beslut. Det är intuitivt klart säger de, att mina bevisregler alltid leder till korrekta slutsatser, och att jag därför borde ersättas av en mer liberal algoritm som godkänner Über-Spjuver. På det kan jag bara svara: Hur vet ni det?"

Sten-sax-påse och logikens djupaste problem, del 2

"Århundradets match" går i stå

Två veckor hade nu gått och staden var tillbaka i vardagslunken. Folk började vänja sig vid de två groteska konstruktionerna på torget, som nu höll varandra i ett krampaktigt grepp där ingen kunde ge sig, och ingen gjorde några framsteg. Det som hade sett ut att bli "århundradets match", tycktes ha hamnat i ett låst läge, och allmänhetens intresse började falna. Borgmästaren hade de senaste dagarna fått in allt fler klagomål från affärsidkare som krävde att matchen skulle avbrytas. De enda som verkade nöjda var gubbarna som mindes tiden då det spelades "riktig" sten-sax-påse. De skrockade och berättade för varandra om de legendariska matcherna mellan Brutus och Scissorhands, och hur de här digitala nippertipporna minsann hade "åkt ut med terabajten före" om de hade varit med på den tiden. "Dom hade inte haft mycke å hämta...", började den ene. "Gosse, dom ha' fått köra dom te skroten efter första matchen" avbröt den andre.

Borgmästaren kallade till krismöte med tävlingskommittén i GISSA-PÅ och representanter för det lokala näringslivet. Han ville veta vilka regler som gällde för matcherna, och om de under några omständigheter kunde avbrytas. Det visade sig att det fanns en klausul enligt vilken en algoritm, för att få delta i en interstellär och av GISSA-PÅ sanktionerad tävling, måste vara skriven så att den "kommer att fatta ett beslut inom rimlig tid". Borgmästaren krävde nu att få höra vad kommittén ansåg vara rimlig tid, och huruvida de båda finalisterna kunde diskvalificeras med grund i denna regel.

"Ja han't fått sälja nå fesk på fjorton da'r", började fiskhandlaren, men tystades ner då den expertgrupp som hade godkänt Meta-Sims algoritm skulle redogöra för sitt granskningsarbete. Man hade fokuserat på de kontralogiska finterna, för att se om de eventuellt kunde försätta Meta-Sim i ett tillstånd där hon uppfattade universum som till sin natur motsägelsefullt, och där hon betraktade Sten, Sax och Påse som olika manifestationer av en och samma symbol. Man hade funnit att hon eventuellt kunde leda svagsinta motståndare in i sådana tillstånd av låsning, men att hennes egen ontologiska projektion av begreppet katt, om än exotisk, var internt konsistent. Vidare hade man konstaterat att det inte är Meta-Sims skyldighet att förhindra logisk-kognitiv blockering hos motståndarna, och att hennes finter därigenom är legitima.

På frågan hur Meta-Sim själv väljer symbol, förklarade en av expertgruppens medlemmar att hon, bortsett från några ytliga finter, helt enkelt simulerar motståndarens samtliga processer, med datafilen som indata. Efter en stunds förvirring fick den sistnämnda punkten klargöras: Hon använder alltså datafilen på två sätt, först för att ladda in motståndarens program, så att detta kan simuleras. Sedan för att läsa datafilen som ren indata, så att hon ser hur motståndaren behandlar denna information. Efter att ha beräknat motståndarens val av symbol, väljer hon själv den vinnande symbolen.

Den tystnad som följde medan borgmästaren och övriga närvarande tog in detta, bröts efter en stund av fiskhandlaren, som förklarade att han för helskotta inte kom in med fiskbilen. "Men hur kan det ta så lång tid...?" kom det så småningom från några av de andra.

"Vi har funnit", fortsatte samma medlem av expertgruppen, "att den sammanlagda tidsåtgången för Meta-Sims alla bimoduler, alltså vad hon gör utöver den rena simuleringen av motståndaren, uppgår till mindre än en hundradels sekund. Förutsatt att motståndarens algoritm är laglig och avslutar inom rimlig tid, kommer därför även Meta-Sim att göra det." En kort tystnad följde igen.

"Hundradels sekund, de har stått här i två veckor nu", försökte borgmästaren, då ett sorl började höras hos den grupp som hade granskat Introspektor. Det visade sig att han, bortsett från de karakteristiska introspektiva finterna, använde precis samma metod som Meta-Sim! Det stod nu klart att den match som pågick på torget aldrig skulle avgöras. De två maskinerna satt tillsammans fast i en oändlig beräkningsslinga, där de förr skulle komma att simulera varje process som kan äga rum i universum, än bestämma sig för sten, sax eller påse.

Kommittén beslöt i all hast att finalen skulle anses oavgjord, och att Introspektor och Meta-Sim skulle dela förstapriset. En protest inkom senare från pappan till två små barn, Inga och Ture, som hade byggt om en gammal kassettbandspelare och anmält den till turneringen under namnet "Inge-Tur-maskinen". Den hade inte fått vara med, eftersom tävlingskommittén trodde att det var en trasig leksak som barnen hade lämnat in på skoj. Pappan hävdade nu att den borde dela priset med Introspektor och Meta-Sim, eftersom den byggde på samma princip. Protesten avslogs då en simpel kassettbandspelare från ett leksaksföretag, om än med fungerande inspelnings- och avläsningsmekanismer, ju omöjligen skulle kunna simulera de avancerade kognitiva processerna hos ett hyperintelligent medvetande som Introspektor eller Meta-Sim.

Ytterligare en regeländring gjordes. Nu måste varje algoritm, för att vara godkänd, komma till beslut oavsett innehållet i datafilen. Det räckte inte att den skulle fatta ett beslut under förutsättning att motståndaren gjorde det. Presidenten skällde i hemlighet ut Introspektors och Meta-Sims programmerarlag och lät dem förstå att de retroaktivt skulle bli diskvalificerade om de kom med några invändningar mot de nya reglerna.

Inga, Ture och deras nya maskin

Inför den kommande tävlingen detaljgranskade alla programmerarna Introspektors och Meta-Sims algoritmer. Det gällde att komma på ett sätt att modifiera dessa så att de alltid kom till beslut, även om de skulle bli simulerade av motståndaren.

Inga och Ture, som nu var lite större barn, hade insett att deras första algoritm inte var bra och förklarat för sin besvikna pappa att diskvalificeringen av Inge-Tur var riktig, om än på felaktiga grunder. De hade jobbat hårt med sin nya maskin, och trots att den inte var riktigt färdig än, ställde de upp med den fungerande testversionen "Tur-Ing-Test1".

Då spelen skulle starta utbröt kaos hos tävlingssekretriatet. Det visade det sig att en timme var på tok för lite tid för att bedöma vilka maskiner som hade godkända algoritmer, eftersom alla tycktes bygga på universell simulering i olika varianter. Man gjorde i alla fall vissa snabba tester där några maskiner diskvalificerades, varefter tävlingen kunde starta.

Protesterna och de formella överklagandena lät inte vänta på sig. Än var man missnöjd för att ens egen algoritm hade blivit underkänd, än för att konkurrentens hade blivit godkänd. Och när matcherna drog igång skulle snart sagt alla förlorare anklaga sina motståndare för att ha använt ohederliga metoder. "Vi blev simulerade ner till sista variabeltilldelningen!", utbrast någon efter varje rond. Några matcher hamnade i låsning likt finalen i de föregående spelen, och för att till varje pris undvika scenariot från den tävlingen diskvalificerades i sådana fall båda maskinerna utan pardon.

Hur Tur-Ing-Test1 fungerade var det ingen mer än Ture och Inga som riktigt begrep. Den verkade på något sätt försöka föra en intelligent dialog med motståndaren, men vad den gjorde och hur den valde symbol förblev dolt bland kodraderna. Den gjorde heller inte mycket väsen av sig, och förlorade inledningsvis nästan alla sina matcher. Men i takt med att den hårdhänta diskvalificeringspolicyn tunnade ut fältet, steg publikens intresse för de båda barnens algoritm.

Till slut var det bara två maskiner kvar i tävlingen, Tur-Ing-Test1 och maskinen "Lurius" från Cassiopeja. Det blev därmed en ren final mellan de två, och under nästan total tystnad startade den spännande matchen. Till en början hände inte mycket. De två algoritmerna hade givetvis universell simuleringskapacitet och kunde på så sätt indirekt kommunicera med varandra. De hälsade artigt och började konversera om sten-sax-påse som kulturellt fenomen. Så småningom blev samtalet mer lättsamt, och maskinerna skrockade åt varandras ordvitsar. Dialogen kom att handla om i tur och ordning antikens uppfattning om medvetandets natur, Arcturiansk tokjazz kontra folkmusik, samt huruvida begreppet "definierbarhet" kunde ges en exakt definition. Svetten började rinna i pannan på presidenten i GISSA-PÅ, som försökte tänka igenom vad konsekvenserna skulle bli om man tvingades diskvalificera även de sista två deltagarna i tävlingen. Men plötsligt, utan förvarning, var matchen över. Displayen vid Lurius från Cassiopeja visade "Sten", medan Tur-Ing-Test1 visade "Påse".

Under jubel och kalabalik vällde publiken fram för att gratulera segrarna Inga och Ture och deras maskin, och först av alla var deras föräldrar. I efteranalysen av matchen visade det sig att de båda algoritmerna var oväntat sofistikerade. De simulerade motståndarens respons på en lång rad av möjliga indata och genomförde ett antal tester för att, utan direkt simulering av matchförloppet, sluta sig till hur motståndaren fungerade. För att garantera att deras algoritm blev godkänd, hade laget från Cassiopeja lagt in en extra kodrad på slutet, som innebar att om simuleringarna drog ut för mycket på tiden, skulle maskinen stanna och välja "Sten". Detta måste göras impulsivt och utan förvarning, eftersom varje planerande av ett sådant beslut skulle riskera att synas i motståndarens simuleringar.

Även Inga och Ture hade lagt in en sådan instruktion för att maskinen inte skulle bli diskvalificerad. De hade skrivit in att Tur-Ing-Test1, om matchen hamnade i ett alltför låst läge, skulle stanna och välja "Sax". Men i sista minuten hade de tyckt att sax kändes förutsägbart, och ändrat till "Påse".

Inga och Ture brydde sig inte om att fyrtiofem olika överklaganden i diskvalificeringsärenden skulle hanteras innan tävlingsresultatet blev fastställt, utan åkte glada hem för att fira med tårta och fortsätta på det riktiga projektet, Tur-Ing-maskinen, som skulle få andra uppgifter än att spela sten-sax-påse.

---

Fortsättning följer.

Sten-sax-påse och logikens djupaste problem, del 1

Det här är historien om hur man i ett parallellt universum, inte långt från vårt, kom att göra de upptäckter om logik och algoritmer som vi förknippar med namnen Kurt Gödel och Alan Turing. Historien handlar om de till synes oundvikliga regeltolkningsproblemen i datoriserad sten-sax-påse, om hur dessa till slut fick sin lösning, och om förståelse kontra bevis i matematik.

Inspirationen till att skriva ihop historien kommer (givetvis!) till en del från Douglas Hofstadters klassiker Gödel, Escher, Bach. Miljön tror jag att jag har hämtat från Stanislaw Lems Cyberiaden och Douglas Adams Liftarens guide till galaxen. När jag började skriva, trodde jag att historien skulle kretsa kring Newcombs paradox (det gör den inte, så den som vill veta vad Newcombs paradox är får söka på annat håll). Men någonstans, troligen efter att jag hade läst Thore Husfeldts bloggpost The freeze app does not exist, insåg jag vad den egentligen handlade om.

Den läsare som inte är bekant med Gödels och Turings satser kanske tycker att det blir lite rörigt på slutet, men jag hoppas att historien i så fall ändå kan ha ett visst underhållningsvärde.

Den stora finalen

Det var en av de där sommardagarna man i efterhand tror var solig, fast det i själva verket duggregnade. Ljuden av mer eller mindre avlägsna blåsorkestrar blandades med sorlet från alla människorna. Här och där seglade tappade ballonger upp mot den himmel de med tiden skulle minnas som klarblå. Det var dags för tungviktsfinal i de datoriserade galaktiska spelen i sten-sax-påse.

Två korteger av lastbilar kröp fram till torget, med flaken fyllda av elektronik och vad som såg ut som delar av byggnadsställningar. Två välorganiserade lag började montera ihop de båda monstruösa maskinerna, som på förvånansvärt kort tid stod klara.

De galaktiska spelen hade genom åren kommit att förknippas med kontroverser. Beskyllningar om fusk och ändlösa diskussioner om regeltolkningar hade varvats med hederliga slagsmål. Redan i de första spelen ansågs segraren "Lazy Daisy" ha varit över en nanosekund sen med att visa, både i semifinalen och i tiebreaket i finalen. Det hade aldrig kunnat verifieras, och förblev just därför ett kärt samtalsämne. Ett läger hävdade att en nanosekund på grund av ljusets begränsade utbredningshastighet inte kunde ge henne någon fördel, en uppfattning som det andra lägret betraktade som befängd.

De följande turneringarna ledde till anklagelser kors och tvärs om såväl randomisering som otillåten koppling. Det ryktades att Lazy Daisy, som alltid låg på gränsen till sen visning, skulle ha tillräckligt med energi för att öppna en inverterad kausal tidsslinga. Så småningom blev det regel snarare än undantag att fördelningen av medaljer avgjordes i segdragna sammanträden i diskvalificeringsärenden långt efter att matcherna hade spelats.

En vändpunkt kom efter de ökända femte spelen, då halva startfältet diskvalificerades och finalen av säkerhetsskäl flyttades till en hemlig måne på landsbygden utanför Eta Centauri. Det var då presidenten i GISSA-PÅ, det Galaktiska Ideella Sällskapet för Sten-Sax-Påse, höll sitt berömda tal där hon deklarerade att "Sten-sax-påse är en beräkningens, psykologikens och det artificiella medvetandets sport, vars renhet och gentlemannamässighet vi, dess utövare, har att försvara."

I efterdyningarna gjordes dramatiska regeländringar. De traditionella femfingrade tentaklerna som fälldes ner på given signal avskaffades helt. I stället skulle valet av symbol kommuniceras rent elektroniskt. För att lösa problemen med maskning, randomisering och kvantkoppling, infördes regeln att den metod med vilken varje tävlande maskin gjorde sitt val av symbol måste deklareras öppet. Senast en timme före turneringens start måste maskinens fullständiga programkod lämnas in till tävlingssekretariatet, där den offentliggjordes för såväl motståndare som åskådare. På så vis kunde i princip var och en verifiera samtliga processer bakom maskinernas beslut, och kontrollera att allt gått rätt till.

Anhängarna av den gamla formen av spelet började att föraktfullt uttala "GIS-SAPÅ" med lång betonad andra stavelse, och muttra om tankepolisen och 1984. Men de erkände i tysthet att det hade varit nödvändigt att strama åt reglerna för att turneringarna inte skulle urarta.

"Brutus 2.0", som vunnit tre galaktiska titlar genom att alltid välja "sten" och om nödvändigt följa upp med en rak höger, åkte nu ut redan i gruppspelet efter att bara ha vunnit en enda match, den mot "Scissorhands". Den stökiga huligankultur som byggts upp kring sporten tynade bort, och spelen kom åter att bli familjeunderhållning.

Rent praktiskt gick det till så att tävlingssekretariatet, efter att alla programkoder lämnats in, sammanställde den så kallade "datafilen", med alla deltagande maskiners fullständiga programkod. Datafilen fick användas i maskinernas beräkningar, men ingen annan information eller randomisering.

De följande spelen kom att domineras av "Simulator X" och dess efterföljare. Simulatoralgoritmerna gick i enkelhet ut på att, med tillgång till motståndarens programkod, försöka simulera hela motståndarens tankeprocess. Efter att motståndarens val av symbol hade beräknats, kunde Simulator X själv välja den vinnande symbolen.

Så småningom visade det sig att maskinerna i Simulatorserien hade väldigt svårt att rå på den så kallade "Snabbve", en maskin som använde vissa enkla knep för att försöka gissa motståndarens val, och ifall dessa gick bet, baserade sitt val av symbol på representationen i bas 3 av talet pi. En alltför enkel strategi kan tyckas, men Snabbve var så fruktansvärt snabb att beräkna siffror i pi, att de motståndare som försökte simulera honom helt enkelt inte hann räkna klart innan matchtiden var ute.

Snabbves strategi ansågs strida mot spelets anda. Efter ytterligare kommittémöten slog presidenten fast att "Sten-sax-påse handlar om djupet i den metalogisk-algoritmiska intro- och extrospektiva analysen [i vardagligt tal utpsykning], inte om simpel beräkningshastighet och pseudorandomisering".

Man beslöt att inom så kallad tungvikt helt avskaffa den begränsade matchtiden. Eftersom algoritmerna måste redovisas, gav ju sen visning inte längre någon fördel. Snabbve fick fortsätta att briljera i så kallad "blixt", men hade inte längre något att hämta i slutspelet i tungvikt.

---

Där de nu stod i varsitt hörn av torget, gjorde de två finalisterna sannerligen rättvisa åt namnet tungvikt. "Introspektor" var en kub av trettio tusen ton stål och elektronik som gav ett mycket stadigt intryck bredvid den mer Eiffeltornslika "Meta-Sim".

De två giganterna matades med identiska kopior av datafilen, och på en given signal startade beräkningarna. Maskinerna spände, på ett rent abstrakt plan, ögonen i varandra. Först prövades de enkla finterna. Introspektor bestämde sig för Sax. Nästan. Han visste att Meta-Sim skulle simulera hans processer och tydligt se de två virtuella fingrarna forma en sax. Givetvis föll hon inte för knepet, utan kontrade med att tänka ologiskt. Först bevisade hon att katter har tre svansar, sedan räknade hon till tjugofemton och bestämde sig för att det var det största primtalet.

Introspektor skälvde, och höljet var nära att ge vika för de fruktansvärda krafterna då triljoner logiska grindar samtidigt protesterade. Till slut lyckades han följa hela resonemanget och kontra med Newcombs dubbelfint: att låtsas ha insett sin egen brist på fri vilja. "Eftersom jag är deterministiskt programmerad", tänkte han, "kan jag lika gärna bestämma mig för Påse". "Om jag gör det, måste det bero på att jag var programmerad så, något jag inte kan påverka". Nu hade matchen börjat på allvar!

Meta-Sim följde Introspektors tankeprocess med obarmhärtig precision, och en rysning löpte längs hennes högsta mast när hon insåg att även hon själv var programmerad. Oavsett vad hon tänkte på, måste tankarna i princip finnas förutbestämda i datafilen. Plommonsaft, tänkte hon plötsligt, och undrade om någon av programmerarna hade lagt in det avsiktligt. Hon blev lite yr när hon insåg att även den undringen måste finnas förutbestämd i datafilen, liksom insikten att den måste det, och så vidare... Och så skärpte hon sig. Hon följde med när Introspektor började simulera sina egna processer. Och i simuleringen började simulera sina egna processer. En oräknelig följd av simuleringar av Introspektor radade upp sig inuti varandra som ryska dockor. "Äh, jag tar påse… lika bra", tänkte den första simuleringen. "Äh, jag tar påse... lika bra", ekade den ena efter den andra av simuleringarna i kanon.
Meta-Sim visste förstås att det var en fälla, och att den riktiga Introspektor skulle välja sten om hon gick på finten och valde sax.

Nya kaskader av självsimuleringar vällde ut i olika riktningar. "Äh, jag tar påse,… äh, jag tar påse, lika bra... lika bra... kom det från alla håll. Meta-Sim tyckte sig stå i en spegelsal där bilder av simuleringar i olika perspektiv reflekterades i ett oändligdimensionellt virrvarr. "Äh, jag tar sax, lika bra", ekade nya kaskader. "Plommonsaft, äh jag tar... plommonsaft...", kom det från ett annat håll, där en alternerande kaskad av kopior av Introspektor och Meta-Sim simulerade varandra om vartannat.

Bara några meter därifrån i det fysiska rummet befann sig Introspektor i ett liknande feberartat tillstånd, där han tyckte sig stå mitt i en ring av kopior av Meta-Sim som dansade och sjöng "Min katt den har tre svansar...".

---

Fortsättning följer.

A remarkable pawn-promotion

The evening's first batch of coffee was almost ready, and in the thirsty crowd, T had found a victim. After a course for aspiring tournament referees, he now knew everything about "insufficient material". B, who felt he knew how the pieces move, found himself listening to a lecture about the rules of chess.

- "So you mean", said B with a slightly disturbed but still amused voice, "that if my flag falls in an ending King + Bishop versus King + Bishop, then with bishops of the same color the game is drawn, but with opposite colors, I lose?"

- "That's right, same color is insufficient material, you can't construct a sequence of legal moves leading to checkmate."

- "But with opposite colored bishops, I could in theory put my king in a corner of the color of my opponent's bishop, and block one of the flight squares with mine. Like this." He quickly set up the following position on one of the analysis boards:



- "Because of that possibility, if my flag falls I have lost the game. That's ridiculous!"
T went on with the other endings of one piece each, knight against knight, bishop or rook, bishop against rook (where it turns out the bishop can't win).

- "You also lose with a pawn against a piece", he continued, unable to conceal his excitement.

- "Aha, because I could promote to a knight or maybe a bishop, and then corner my king. That's the silliest use of under-promotion I've ever heard of!"

The moment he pronounced the word "under-promotion", the problemist G entered the discussion. G's favorite topic was helpmates, but under-promotion would do.

- "In fact there are only two possible motives for promotion to bishop or rook", he explained, "at least if one excludes things like ridiculing one's opponent. One is offensive, to avoid stalemating the opponent in a winning position. The other is defensive, to draw by getting stalemated. You see, except when it comes to stalemate, a queen will be at least as good as a rook or a bishop." He showed them a rare example of a serious under-promotion, the famous game Bremel - Kertis, Budapest 1948:


- "In this position, White won with 1. a8R+! Kb4, 2. Rb8+ Kc3 3. Rxb1. If the rook had been a queen, Black would have been stalemated at this point."
- "The defensive motive, getting oneself stalemeted, is even more exotic. It's been demonstrated numerous times in problems and studies, like this one by Traxler and Dedrle from 1909:"



- "White draws with 1. Ra2+ Kxa2 2. Bxf7+ Qxf7 3. g8B! Rxf8 stalemate. But the defensive under-promotion is a unicorn of chess. Easy to imagine, yet nobody has seen a real one! Amazing, isn't it? Not a single defensive under-promotion is known from the millions of recorded games of chess history."

- "The most spectacular demonstrations of under-promotion are the realizations of the so-called Babson theme..."

And here he was interrupted by P, who reminded everyone that it was six o'clock and the games were about to start. It turned out that B was playing white against T. Their game became the longest of the evening, and when it was about to be decided, a small crowd had gathered in silence around the table. Black would clearly queen first, but his other race, that agianst the clock, was less certain.



In this position the game continued 61. b6 c1Q 62. b7 Qc5+ 63. Ka8 Qc6 64. a7. T now realized he would have had mate in two with 64. - Qh1 65. Kb8 Qh8 if not the stupid bishop had blocked the eighth rank. So he decided to get it out of the way. 64. - Be7 65. Kb8.
With time running out, T had already forgotten his plan and was thinking about 65. - Bd6+, but didn't see how to continue after 66. Ka8. So instead the game went 65. - Qc7+ 66. Ka8. A few minutes later in the calm of the analysis room, he would realize not only that the back-rank mate had still been possible with 65. - Qd6+ 66. Ka8 Qd5 and 67. - Qg8, but also that after 65. - Bd6+ 66. Ka8 Qa6 67. b8Q+ Bxb8, the idea that White gets yet another queen is an illusion.



With only seconds left for the entire game, T was jumping up and down in his chair. How could it be so difficult to finish the opponent off with queen and bishop against a couple of silly pawns? He finally sighed and realized he might have to settle for a draw. With a helpless look on his face, he took a last glance at the clock, 3, 2, 1 second left. And played 66. - Qc8+.

Only at this point did B realize he might actually promote one of his pawns. With his last move, Black was clearly offering a draw, but the gentleman he was, B would still not miss an opportunity of a little prank. He reached out for the white queen, but with his eyes still focused on the board, accidentally pushed her over the edge of the table. She bounced through the little crowd and disappeared under a chair.

Never mind. For the desired effect, the move would have to be played instantly. B put one of his rooks upside down on b8, removed his b-pawn, and pressed the clock. With his hands flying nervously all over the board, T knocked his own king over, picked it up and managed to put it on d8, but the clock was already flashing with a row of zeros on Black's side.



- "I seem to have lost on time", he confessed, but all of a sudden recalled what he had learnt in the weekend.

- "No, wait, it's a draw because of insufficient material!"

The following conversation was a bit confused. Some spectator argued that a rook upside down is a generally accepted substitute for a queen, while another pointed out that even a rook is sufficient material. Meanwhile, T tried to explain that since no sequence of legal moves can lead from the current position to one where the black king is checkmated, the game is drawn even though Black's flag has fallen.

They were interrupted by G, the problemist.
- "I'll be darned! Gentlemen..."

As he spoke, he swiftly turned the rook on b8 back to its normal orientation and, as the club's chairperson S had joined the group, continued:

- "...and ladies, this moment goes to history. For centuries, problemists and study composers have thought that the only motives for promotion to rook or bishop are forcing or avoiding stalemate. But tonight our friend B has demonstrated, with his extraordinary 66:th move, that there is another motive: retaining sufficient material."



- "In the final position, with White to move after Black overstepping time, White has sufficient material because on the forced continuation 67. Rxc8+, Black has the legal move 67. - Kd7 after which he can in principle be checkmated. Had the rook on b8 been a queen, the only legal continuation would have been 67. Qxc8+ Kxc8 stalemate, and therefore 66. - Kd8 would have ended the game. The manoeuver Be7 - Kd8 was brilliant too, and would have saved the game against..."

- "I don't quite follow", said B, eager to get some coffee and gossip about the other games of the evening, "but in any case the position is dead drawn, everyone can see that."

With those words he shook T's hand, signed the protocol saying 1/2-1/2, and went to the analysis room, unaware of his unique contribution to chess history.

Epilogue

As the problemist G realized later that evening, there is yet another motive for under-promotion, that of forcing insufficient material. A while later, he published a strange little chess problem, clearly inspired by that evening's events:



The task was unusual: Draw in 1 move.

Acknowledgments

This story was inspired by the wonderful people and events that happened or might have happened at the chess club LASS, Linköping, around ten years ago. While there is no clear correspondence between characters and real people, similarities might not be entirely accidental. Another source of inspiration was a blog post of Bo Sjögren (another former LASS player). Many other examples of under-promotion can be found among the wonderful Chess Curiosities of Tim Krabbé.