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é.

Hello World!

Testing testing, $1, 2$!
If I'm going to be a blogger, I will certainly talk about mathematics from time to time. Fortunately, there is something called MathJax that allows me to type equations in LaTeX just like I'm used to, and have them displayed here. For instance I might want to talk about the cardinal number $\aleph_\omega$, or the identity \[\sum_{k=1}^\infty \frac1{k^2} = \frac{\pi^2}6.\]
Seems to work!