Regel 110

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Regel 110 vanuit 1 cel.

Regel 110 (Engels: Rule 110) is de enige elementaire cellulaire automaat waarvan Turingvolledigheid is bewezen. Regel 110 werd voor het eerst besproken door Stephen Wolfram.

Regel 110 maakt gebruik van de volgende regels:

huidig patroon 111 110 101 100 011 010 001 000
nieuw toestand voor middelste cel 0 1 1 0 1 1 1 0

Volgens de door Wolfram bedachte naamgeving bij elementaire cellulaire automaten krijgt regel 110 zijn naam doordat het binaire getal 01101110 in het decimale stelsel gelijk is aan 110.

Turingvolledigheid[bewerken]

Het bewijs van Turingvolledigheid werd geleverd door Matthew Cook. De Turingvolledigheid van regel 110 werd voor het eerst vermoed door Stephen Wolfram in 1985. Cook presenteerde zijn bewijs op de CA98 conferentie op het Santa Fe Institue voordat het boek A New Kind of Science van Wolfram was uitgegeven. Hierdoor beschuldigde Wolfram Research Cook van het verbreken van zijn geheimhoudingsverklaring en dit zorgde ervoor dat het bewijs niet gepubliceerd werd na afloop van de conferentie.

Het boek A New Kind of Science werd in 2002 uitgegeven met daarin de algemene lijn van het bewijs. In 2004 publiceerde Cook zijn bewijs in Wolframs tijdschrift Complex Systems.

Externe links[bewerken]