QED

In het oktobernummer van PC-Active staat een artikel van mij over Stephen Wolframs boek A New Kind of Science. In 2002 publiceerde Wolfram, de uitvinder van het populaire wiskundige programma Mathematica, dit controversiële boek op basis van 15 jaar monnikenwerk. In dit lijvige boek (1263 pagina’s) geeft hij een studie van computerprogramma’s met eenvoudige regels, zogenaamde cellulaire automaten. Wolfram beweert in het boek dat we met behulp van cellulaire automaten heel wat problemen in een breed gamma aan wetenschappen kunnen oplossen.

Het grootste deel van A New Kind of Science bespreekt voorbeelden van ééndimensionale tweekleurige cellulaire automaten, de zogenaamde “elementaire cellulaire automaten”. Er bestaan 256 automaten van deze soort en Wolfram geeft ze allemaal een volgnummer van 1 tot 256. Elke automaat heeft verschillende regels die de kleuren van een cel en zijn buren aanduiden en de nieuwe kleur van de cel in de volgende stap. Er zijn acht mogelijke patronen van drie cellen (de cel en zijn buren) en voor de nieuwe kleur bij elk patroon hebben we een bit nodig, dus elk van deze automaten kan volledig gespecifieerd worden door 8 bits. Hierdoor zijn er 256 (=2⁸) mogelijke elementaire automaten.

Wanneer Wolfram spreekt over de automaat met regel 110, kunnen we hieruit eenvoudig de regels afleiden: we schrijven 110 in het binaire talstelsel en bekomen 01101110. De meest rechtse bit staat voor het patroon 000, daarnaast voor 001, daarnaast voor 010, enzovoort. Hieruit leiden we af dat regel 110 de centrale cel op 1 zet in de patronen 110, 101, 011, 010 en 001. In de andere gevallen wordt de centrale cel op 0 gezet. Dit geeft de volgende regels:

Mogelijke structuren in de evolutie van deze automaat zijn te zien in de volgende afbeelding:

Van de 256 elementaire cellulaire automaten is “regel 110″ de enige waarvan bewezen is dat ze universeel is. Dit wil zeggen dat de automaat genoeg complexiteit heeft om alle mogelijke effectieve berekeningen uit te voeren. Het gedrag van de automaat toont verschillende lokale structuren die bewegen en met elkaar interageren op complexe manieren. Wolframs assistent Matthew Cook bewees dat deze structuren krachtig genoeg zijn om universele berekeningen uit te voeren. Regel 110 is dus even krachtig als de tweedimensionale cellulaire automaat Game of Life (waarover ik in PC-Active 199 schreef), waarvan ook een bewijs van universaliteit bekend is.

De cellulaire automaten die in Wolframs boek centraal staan hebben verrassende mogelijkheden. Zo zijn er automaten te vinden die berekeningen kunnen uitvoeren. In het artikel geef ik verschillende voorbeelden, zoals berekening van de rest bij deling door 2, kwadraten, priemgetallen en zelfs logische functies, zoals de of-functie:

Volgende maand duik ik dieper in de berekeningsmogelijkheden van eenvoudige programma’s. Ik bespreek dan eenvoudige Turingmachines en de prijs die Stephen Wolfram heeft uitgeloofd om te bewijzen dat een bepaalde berekeningsregel de eenvoudigste universele Turingmachine is.