RIP John Conway

Som mange af jer sikkert har hørt døde matematikeren John Conway forleden. Inden for computerkredse er han nok bedst kendt for Game of Life, en Turingkomplet cellulær automat. GoL er bruger simple regler til at opnå kompliceret opførsel, såkaldt emergent behaviour: I et kvadratnet kan hvert felt have eller ikke have et individ. Om der i næste tidsskridt er et individ i et felt afhænger af antallet af nabofelter (i alle otte retninger): Hvis der i forvejen er et individ i feltet, overlever dette individ, hvis der er 2 eller 3 nabofelter med individer. I et tomt felt opstår et nyt individ, hvis der er præcis 3 nabofelter med individer. Et eksempel på en udvikling kan ses i xkcds hyldest til John Conway.

Jeg stødte på GoL i en artikel i Scientific American fra 1970, der blev genoptrykt i en samling af Martin Gardners "Mathematical Games" klummer. Da jeg kom på gymnasiet og fik lov til at bruge deres RC7000 computer med COMAL, lavede jeg og nogle venner et program til at simulere Conways GoL. Da der ikke var skærm eller mus, og der ikke var voldsomt meget regnekraft, begrænsede programmet sig til et 10×10 kvadratnet, og kun de midterste 4×4 kunne initialiseres til at indeholde individer. Vi konkurrerede så om hvem, der kunne finde den 4×4 opstilling, der blev ved i længst tid, inden den gentog en tidligere position. Så vidt jeg husker, var rekorden dengang lidt over 100, men senere lavede jeg en simulering af alle 65536 kombinationer og fandt en bedre løsning. Jeg vil lade det være en opgave til læseren at finde denne. Det skal bemærkes, at der ikke var wraparound, så felter udenfor de 10×10 betragtedes som værende tomme. Jeg lavede også en simulering med wraparound, og den giver ikke overraskende et meget større antal generationer uden gentagelser.

Selv om der i 1970erne og 1980erne blev fundet mange interessante kombinationer, f.eks. en "glider gun", der skyder gliders ud med jævne mellemrum (se Wikipedias artikel om GoL), varede det mange år, før GoL blev bevist Turingkomplet.

Jeg har senere hen rodet med andre cellulære automater, både endimensionelle og todimensionelle, med mere end to mulige værdier i hver celle, med heksagonale grids, og mange flere. Jeg har f.eks. lavet en variant af det simple Game of Life, hvor sort og hvidt er symmetrisk, så et mønster af sorte felter på hvis baggrund opfører sig på samme måde som et mønster af hvide felter på sort baggrund, og jeg har også studeret reversible automater -- som kan køre både forlæns og baglæns.

Men John Comway er også kendt for andet end Game of Life. Han skev for eksempel bogen "Winning Ways for your Mathematical Plays" sammen med Elwyn Berlekamp og Richard Guy. Denne bog introducerer kombinatorisk spilteori på en letforståelig måde og anvender den på en række simple spil, inklusive GoL. Han har også fundet på surreal numbers, der er en udvidelse af de reelle tal med infinitismale og uendelige værdier.