Still life (automa cellulare)
# 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").

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. 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.

Riguardo alle prima richiesta, si noti che esistono configurazioni infinite di celle vive che coprono stabilmente lo spazio; tali configurazioni sono dette agar, 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.

## Still life nel Gioco della vita

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).. 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à 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; in seguito, è stato possibile trovare soluzioni ottimali per quadrati di dimensione maggiore. Una lista delle densità massime è stata compilata da Yorke-Smith.

