|
|
|
|
La teoria degli automi cellulari è stata inventata alla fine degli anni '40 da Stanislaw Ulam (1909-1984) e da John von Neumann (1903-1957).
La scoperta di Life da parte di John Conway è del 1970. Verso la metà degli anni '80 Stephen Wolfram pubblicò una serie di articoli contenenti i risultati di ricerche molto innovative e fruttuose, ottenuti in parte attraverso l'uso di un grandissimo numero di esperimenti al computer. Wolfram all'epoca studiò principalmente il caso degli automi unidimensionali.
Nel caso a 1 dimensione possiamo immaginare le celle disposte lungo una retta; un intorno di raggio r di una cella è costituito dalle r celle immediatamente a sinistra più le r celle immediatamente a destra alla cella stessa. Pertanto se r=1 l'intorno è costituito da 3 celle.
Quante sono le possibili leggi di automa cellulare unidimensionale con r=1?
Data una cella nella posizione x per decidere lo stato di x nell'istante successivo (1 o 0, cioè acceso o spento) dobbiamo considerare la terna di celle di posizioni x-1, x, x+1. Questa terna può essere in 1 di 8 diversi stati che possiamo rappresentare con i numeri decimali 0, 1, ..., 7 corrispondenti rispettivamente alle loro espressioni binarie di 3 bit 000, 001, ... , 111.
Osserviamo la tabella sottostante:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Nella riga centrale ci sono gli 8 possibili stati delle 3 celle contigue di posizione x-1, x, x+1; nella prima riga ci sono i corrispondenti valori decimali. Una legge è specificata in modo univoco se nella terza riga si mette una stringa di 8 0 od 1. Nel caso della tabella di sopra, per esempio, se x-1 è accesa, x è spenta, x+1 è spenta (terna 100 corrispondente al numero decimale 4), leggiamo il bit che sta sotto a 100 e troviamo 1; questo significa che all'istante successivo la cella sarà accesa, e così per tutti gli altri casi.
Poiché una legge è identificata da una stringa di 8 bit vi sono 28=256 leggi unidimensionali con r=1.
Queste leggi si possono identificare con un numero. Nel caso dell'esempio se scriviamo di seguito i bit della terza riga otteniamo 01011010. Interpretiamo questa scritta come la rappresentazione binaria di un numero la cui espressione decimale sarà quindi (si legge da destra a sinistra)
Esamineremo ora gli automi cellulari unidimensionali di Wolfram con:
|
|
|
|