Johan Wästlund: Sten-sax-påse och logikens djupaste problem, del 3

Johan Wästlund: Sten-sax-påse och logikens djupaste problem, del 3

Friday, December 6, 2013

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?"

Posted by Johan Wästlund at 1:47 AM

Email ThisBlogThis!Share to TwitterShare to FacebookShare to Pinterest

No comments:

Post a Comment

Newer Post Older Post Home

Subscribe to: Post Comments (Atom)

Blog Archive

►  2018 (5)

►  March (2)

►  February (1)

►  January (2)

►  2017 (12)

►  September (1)

►  July (1)

►  June (3)

►  May (1)

►  April (1)

►  March (1)

►  February (3)

►  January (1)

►  2016 (7)

►  October (1)

►  September (1)

►  June (1)

►  April (2)

►  March (2)

►  2015 (3)

►  July (2)

►  April (1)

►  2014 (6)

►  December (1)

►  November (1)

►  July (1)

►  June (1)

►  March (1)

►  February (1)

▼  2013 (5)

▼  December (2)

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

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

►  November (1)

►  June (1)

►  May (1)

MathOverflow About Me Johan Wästlund View my complete profile |

Simple theme. Powered by Blogger.