Still life (automa cellulare)

Negli automi cellulari, si definisce still life (in inglese "natura morta", letteralmente "vita ferma") una configurazione di celle che non modifica il proprio aspetto nel corso delle generazioni. Per questo motivo, una still life può equivalentemente essere definita come un oscillatore di periodo uno (in gergo, "p1")[1].

Un nome equivalente per una still life è configurazione stabile (stable pattern).

Caratteristiche definitorie della still life

A rigore, una still life può e deve essere considerata tale solamente se soddisfa certe caratteristiche definitorie, che escludono dalla definizione alcune configurazioni banali; una still life:

  • consta di un numero finito di celle;
  • consta di almeno una cella viva;
  • non è una collezione di parti che sono esse stesse still life; ossia, non è composta.

Quest'ultima richiesta è la più peculiare; sono state scoperte configurazioni stabili che sono scomponibili in tre sotto-configurazioni stabili, ma non in due, oppure in quattro sotto-configurazioni stabili, ma non in due o in tre.[1][2] Per questo, si usa estendere la richiesta per definire una still life alla non-scomponibilità "totale" (che esclude anche la composizione di tre o quattro still life in una sola).

Ogni configurazione stabile composita viene denominata pseudo-still life, in contrasto con la still life in senso stretto (strict still life). Benché non sia affatto banale capire se una configurazione stabile sia una still life vera o composita, è stato dimostrato che è sempre possibile deciderlo in tempo polinomiale[3].

Riguardo alla prima richiesta, si noti che esistono configurazioni infinite di celle vive che coprono stabilmente lo spazio; tali configurazioni sono dette agar[4], e sono caratterizzati da una periodicità (o pseudo-periodicità) spaziale, come l'invarianza per traslazioni, riflessioni o glissoriflessioni. Esistono altresì configurazioni in grado di riempire l'intero spazio, generando un agar (essendo perciò un sottoinsieme delle configurazioni a crescita quadratica), che vengono chiamate space-filler.[5]

Still life nel Gioco della vita

Figura 1:
Il blocco (block).
Figura 2: La vasca (tub).

Nel Gioco della vita di Conway, le still life sono oggetti molto comuni. Si può facilmente dimostrare che il numero minimo di celle affinché possa esistere una still life in questo automa è quattro; in particolare, quattro celle disposte a quadrato, come in Figura 1, formano una configurazione detta block ("blocco"). Questa è la still life più ricorrente che si forma a partire da configurazioni casuali di celle, nonché la seconda in assoluto (la prima è il blinker).[6]. Se il quadrato è "ruotato", come in Figura 2, la configurazione è detta tub ("vasca").

Il numero di possibili still life in funzione del numero di celle è stato tabulato, per i primi n, da Niemiec e Koenig indipendentemente; per n da 1 a 15, tale numero è

0, 0, 0, 2, 1, 5, 4, 9, 10, 25, 46, 121, 240, 619, 1353, ...

L'esempio più celebre di space-filler in questo automa cellulare è Max, che con le sue 187 celle è anche il più piccolo esempio noto di configurazione in grado di riempire lo spazio. È stato dimostrato da Noam Elkies che non può esistere un agar stabile la cui densità[7] sia maggiore di 1/2; parlando invece in termini di configurazioni finite, sono possibili densità più elevate: per quadrati fino a 20x20 sono state trovate soluzioni di ottimo adoperando tecniche per la ricerca operativa tipiche di un problema con vincoli[8]; in seguito, è stato possibile trovare soluzioni ottimali per quadrati di dimensione maggiore[9]. Una lista delle densità massime è stata compilata da Yorke-Smith[10].

Galleria d'immagini

Esempi di still life nel Gioco della vita
Configurazione di massima densità in un riquadro 19x19.
Configurazione di massima densità in un riquadro 20x20.


Note

  1. ^ a b Eric Weisstein's Encyclopedia
  2. ^ Si può dimostrare, in forza del teorema dei quattro colori, che quattro è il massimo numero di sotto-configurazioni di cui può constare una configurazione stabile non scomponibile in meno di altrettante sotto-configurazioni.
  3. ^ Cook, Matthew, Still life theory, New Constructions in Cellular Automata, Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press, 2003, pp. 93–118.
  4. ^ Agar su LifeWiki.
  5. ^ Spacefiller su LifeWiki.
  6. ^ Most seen natural occuring ash objects in Game of Life.
  7. ^ Con questo termine si intende il rapporto tra celle vive e celle totali.
  8. ^ J. Larrosa, E. Morancho e D. Niso, On the Practical use of Variable Elimination in Constraint Optimization Problems: 'Still-life' as a Case Study, in Journal of Artificial Intelligence Research, vol. 23, 2005, pp. 421–440. URL consultato il 20 febbraio 2011 (archiviato dall'url originale il 16 luglio 2011).
  9. ^ G. Chu, P.J. Stuckey e M.G. de la Banda, Using Relaxations in Maximum Density Still Life, in Lecture Notes in Computer Science, vol. 5732, Springer, Berlin, Heidelberg, pp. 258–273..
  10. ^ Maximum Density Still Life (lista di N. Yorke-Smith).

Bibliografia

  • (EN) Andrew Adamatzky, Constraint Programming to Solve Maximal Density Still Life,, in Game of Life Cellular Automata, Springer, 2010, pp. 167-175, ISBN 978-1-84996-216-2.

Voci correlate

Collegamenti esterni