Navicella (automa cellulare)

Negli automi cellulari, una navicella (o astronave, in inglese spaceship) è una configurazione di celle in grado di traslare nello spazio con lo scorrere delle generazioni.^[1] Formalmente, una configurazione è chiamata navicella se, in seguito a un numero finito di generazioni (chiamato periodo della navicella), essa si ripresenta nella medesima disposizione e orientazione, ma in una posizione spaziale differente.

Un automa cellulare molto famoso, in cui ritroviamo vari tipi di navicelle, è il Gioco della vita di Conway.

Le navicelle sono caratterizzate da due parametri: il periodo e la velocità.
Il periodo di una navicella è il numero di generazioni che essa impiega a ripresentarsi nella medesima disposizione iniziale (come per gli oscillatori). Ad esempio, la navicella più semplice, il Glider, ha un periodo di 4, ossia assume quattro differenti disposizioni durante la traslazione.
La velocità esprime il rapporto tra la traslazione della navicella a seguito del periodo e il periodo stesso (o, più semplicemente, ${\displaystyle {\frac {\Delta s}{\Delta t}}}$). Orientando il piano con assi cartesiani, si danno due tipi di velocità: la velocità orizzontale ${\displaystyle v_{x}}$ e la velocità verticale ${\displaystyle v_{y}}$.
Questi due tipi di velocità, di fatto equivalenti, si dicono genericamente velocità ortogonale. L'unità di misura della velocità nel Gioco della vita è chiamata velocità della luce (speed of light o speed of life, simbolo ${\displaystyle c}$), e corrisponde allo spostamento di 1 cella in 1 generazione; il nome velocità della luce è dovuto al fatto che questa velocità di traslazione non può essere in nessun modo superata.^[2][3]

Posto n come il numero di generazioni del periodo, (${\displaystyle x_{0}}$, ${\displaystyle y_{0}}$) come la posizione iniziale della navicella, e (x,y) come la posizione della navicella dopo un periodo, la velocità sarà dunque pari a:

${\displaystyle v_{x}={\frac {(|x|-|x_{0}|)}{n}}\,c}$

per la velocità di traslazione lungo l'asse x, e

${\displaystyle v_{y}={\frac {(|y|-|y_{0}|)}{n}}\,c}$

per la velocità lungo l'asse y.

La LWSS, ad esempio, ha una velocità di c/2 in una direzione, e di 0 nell'altra, cioè ha una velocità ortogonale di c/2.

Se una navicella si trasla sia lungo l'asse x sia lungo l'asse y, il suo movimento è detto diagonale, e la sua velocità diagonale si misura tenendo conto della velocità maggiore tra x e y (e non della loro somma). Il Glider, ad esempio, ha una velocità orizzontale e verticale di ${\displaystyle {\frac {c}{4}}}$, poiché dopo 4 generazioni (il suo periodo) esso risulta traslato di 1 casella in orizzontale e di 1 in verticale. La sua velocità diagonale è pertanto c/4.

Esistono 4 navicelle "base", ossia molto semplici e molto adoperate in reazioni e circuiti.

Il Glider, o Aliante, è l'astronave più semplice e comune; composto da 5 celle, si muove diagonalmente con velocità c/4. Esso viene spesso prodotto da reazioni casuali, ma esistono modi per crearne un flusso a periodo controllato tramite strumenti detti "cannoni" (guns; il più semplice è il Cannone di Alianti di Gosper, che produce un flusso p30 di Glider). I Glider possono interagire in vario modo fra di loro: due Glider che collidano in modo opportuno si annichilano, mentre l'unione di tre Glider porta alla creazione di una LWSS. Le macchine a stati finiti create usando il Gioco della vita utilizzano i Glider come byte di informazione; è possibile utilizzare flussi di Glider per operazioni di Boole.

La LWSS (Light weight spaceship, "astronave leggera") è formata da 9 celle, e si muove orizzontalmente o verticalmente (a seconda dell'orientazione) con velocità c/2. Si possono produrre flussi periodici di LWSS combinando tre flussi di Glider disposti opportunamente.

La MWSS (Medium weight spaceship, "Astronave di media stazza") è formata da 11 celle, e ha un movimento affine a quello della LWSS, con velocità c/2. Una MWSS si può ottenere modificando una LWSS tramite una scintilla. Un oscillatore può altresì essere usato per convertire un flusso di LWSS in un flusso di MWSS di uguale periodo.

La HWSS (Heavy weight spaceship, "Astronave pesante") è formata da 13 celle, e ha un movimento affine a quello della LWSS e della MWSS (velocità c/2). Si può ottenere modificando una MWSS tramite una scintilla. Un oscillatore può essere usato per convertire un flusso di MWSS in un flusso di HWSS di uguale periodo.

Le astronavi che lasciano dietro di sé un'emissione di detriti sono chiamate smoking ships, e la scia smoke ("fumo"). Il "fumo" può essere adoperato per perturbare altre astronavi, per esempio per deviarle, o può essere esso stesso perturbato per trasformare la navicella in puffer.

Un puffer è una navicella che emette una scia di still life (cioè oscillatori di periodo 1), oscillatori o navicelle. Esistono anche puffer che emettono cannoni (ad esempio, Cannoni di Alianti di Gosper), incrementando così la popolazione totale in modo quadratico; in questo caso, vengono chiamati breeder.

Le navicelle possono anche trasportare, scortandolo, un oggetto che sarebbe altrimenti incapace di muoversi, o addirittura di sussistere senza collassare. Questo oggetto viene chiamato tagalong (dall'inglese to tag along, "seguire passo per passo"), e può essere di varia natura. Un esempio di tagalong è il blocco.

• Gioco della vita
• Oscillatore (automa cellulare)
• Still life (automa cellulare)

• Wikimedia Commons contiene immagini o altri file su Navicella

• Spaceships in Conway's Game of Life di David I. Bell
• Gliders in "Life"-Like Cellular Automata di David Eppstein