Absoluut mee eens! Ik heb wel een technische achtergrond, maar ik volg maar de helft van de duscussie, maar vindt het wel erg interessant

De auteurs construeren een speciale Magic toestand die gekoppeld kan worden aan de werking van een door Rogozhin in de vakliteratuur beschreven Universele Turing Machine, namelijk de (2, 18 ) UTM. Afhankelijk van de begin-condities kan de UTM stoppen (overwinning voor speler A), of hij kan niet stoppen (remise, vanwege een oneindige loop). De auteurs concluderen hieruit dat Magic minstens zo complex is als het Halting probleem.

Deze conclusie gaat mij te ver. Je kunt deze analyse immers ook toepassen op allerlei aanzienlijk eenvoudiger spelen. Neem Rock, Paper, Scissors. De regels zijn als volgt. Spelers A en B kiezen tegelijkertijd R, P of S. Nu geldt: P wint van R, R wint van S, S wint van P. Indien de spelers dezelfde keuze maken is er geen score.

Ik organiseer een RPS computer toernooi. Er strijden steeds twee programma's (A en B) tegen elkaar. Wie het eerst 100 punten heeft gescoord, wint de partij. Beide computer programma's mogen initiele parameters gebruiken maar ook letten op het spelverloop (laatste X zetten bijhouden). Nu bouw ik een Turing Machine (d.w.z. een overkoepelend computer programma) die de zetten van spelers A en B berekent en uitvoert, en de overall score bijhoudt. Het kan zijn dat A uiteindelijk wint met zeg 100 - 91, of B wint, maar dat is aan de computer codes en de initiele parameters van de twee programma's niet zomaar af te lezen. Daarnaast is het mogelijk dat op een gegeven in de partij de twee programma's dezelfde zetten beginnen uit te voeren: PP, RR, RR, RR, SS, PP, SS, RR..... Die string zou in principe oneindig lang kunnen zijn (niet ondenkbaar wanneer twee versies van hetzelfde programma A tegen elkaar spelen). Als dat zo zou zijn, haalt geen van de spelers de 100 punten en is de partij onbeslist. Het is niet a priori te bepalen of de partij tussen A en B hiermee te maken krijgt. Dus heb je hier ook een Halting Probleem.

Betekent dit nu dat Rock, Paper, Scissors een complex spel is? Nee, de complexiteit schuilt in de onbeperkte strategische mogelijkheden van de twee programma's.

Het verschil zit hem in de onberekenbaarheid van RPS. Als twee spelers dit spel spelen, kan je nooit van een van beiden zeggen wat zijn volgende zet zou zijn. Dat is zijn strategie en hoe vaak je hem bekijkt, de speler kan zelf altijd besluiten iets anders te doen... Dat is waarom RPS werkt. Als je namelijk exact zou kunnen voorspellen wat je tegenstander doet, zou je altijd kunnen winnen. En dat kan je tegenstander ook. Dus wint iedereen ieder spel RPS en dat kan niet.

Een computer, of algemener een UTM, kan je wél voorspellen. Deze maakt, aan de hand van zijn programma, wat berekeningen en zegt dan wat hij gaat doen. Maar dit zal, met dezelfde input, altijd dezelfde output zijn.

Stel je voor dat je een computer hebt, genaamd "Pieter", die zo gebouwd is dat hij altijd een som voor je uitrekent. Geef Pieter de som 37+5, hij gaat rekenen, en geeft je 42. Pieter doet het perfect en maakt nooit fouten. En een andere computer, genaamd "Henk", die een stelling van een schaakbord als input heeft en altijd de beste zet voor wit geeft, en het ook nooit fout heeft. Henk kan perfect uitrekenen wat wit moet doen met schaken, en Pieter kan perfect rekenen.
Maar als je Henk de som 37+5 geeft, zal Henk vast lopen. En vice versa, Peter zal vastlopen als je hem het Siciliaans voorschotelt. Nu is de vraag: bestaat er een computer die twee inputs nodig heeft: namelijk een "blauwdruk van een computer" en een input, die perfect kan uitrekenen of de computer van zijn blauwdruk de input kan verwerken, of dat hij vastloopt? Stel, zo'n computer kan je bouwen. Noem deze computer dan even "Jan". Dus als je Jan de computer Pieter en de input 37+5 geeft, zal Jan zeggen "Ja hoor, dat lukt hem wel!" En Jan zal ook zeggen "Nope, die loopt vast!" als je hem Pieter en het Siciliaans geeft. Jan doet dat perfect en kan het met alle computers... Dus kunnen we een computer maken die precies hetzelfde als Jan doet, maar aan het einde vastloopt als Jan zegt "Ja hoor" en "Ja hoor" zegt als Jan "Nope" zegt. Die noemen we wel Klaas. Dus Klaas loopt vast als we hem Henk en een schaakbord geven, maar zegt "Ja hoor" als je Henk en een rekensom geeft.

Stel, we geven Klaas een blauwdruk van zichzelf, twee keer. Wat komt er dan uit? Klaas kan ofwel "Ja hoor" zeggen, of vastlopen. Aangezien Jan perfect is, kan Jan dit uitrekenen. Als Klaas vastloopt, zegt Jan "Nope". Maar dan zegt Klaas "Ja hoor" en had Jan het dus fout. En andersom, als Klaas "Ja hoor" zou zeggen, zou Jan zeggen dat het Klaas wel lukt, en dus loopt Jan weer vast. Dus Jan heeft het hoe dan ook fout.

Oftewel: er is een computer en een input waarvan Jan niet kan zeggen of het lukt voor die computer om het uit te rekenen. Maar Jan werkte perfect, dus kan Jan niet bestaan. Dus er is geen computer die uit kan rekenen of een bepaalde computer vast loopt op een bepaalde input, of niet. Dat is het Halting Problem: je kan geen algoritme geven wat voor je uitrekent of je computer vastloopt of niet.

De computer die je nu maakt bestaat uit anders gehackte Xathrid Necromancers en Rotlung Reanimators en de input is een bepaalde hoeveelheid groene en witte tokens die respectievelijk 3/3, 4/4, 5/5, etc. zijn en bepaalde creature types hebben. Er is hier geen "vrije wil": de spelregels van Magic bepalen exact hoe de rest van het spel gaat verlopen (wat dus anders is dan RPS). De computer doet een hele hoop rekenwerk met als output ofwel "ik win het spel" ofwel een oneindige loop, waardoor hij vast loopt. Er is geen manier om uit te rekenen welke van de twee gaat gebeuren, want anders konden we daar wel een computer van bouwen en had je eigenlijk laten zien dat Jan wél bestaat. Dus de judge kan niet bepalen wie er wint, of dat het een gelijkspel is omdat we allebei de boardstate niet kunnen veranderen, dat zou namelijk betekenen dat de judge uit kan rekenen wat een computer níet kan, en dan zouden we gewoon de hersenen van een judge in de computers stoppen. Dus is Magic minstens net zo moeilijk als het Halting Problem, want je kan niet bepalen wat er in een compleet geforceerd spel Magic gebeurt als je het Halting Problem niet op kan lossen.