Life e i numeri primi [Pillole]

Sicuramente conoscete Life di Conway. Forse avete anche sentito dire che è stato dimostrato che è equivalente a una macchina di Turing: detto in altro modo, qualunque tipo di computazione che possiamo fare con un qualunque computer può essere simulato da una opportuna configurazione iniziale di Life. Il risultato è teorico, il che significa che nessuno si preoccupa della velocità di esecuzione, ma soprattutto che nessuno si mette ad esplicitare quale configurazione corrisponde al nostro calcolatore di Conway.

Quasi nessuno, per la precisione. Dean Hickerson progettò nel 1991 un generatore di numeri primi. Come potete vedere nel video qui sopra, le 2953 celle della configurazione di partenza emettono alla generazione 120N+100 una “astronave leggera” (il nome di una configurazione in Life) per alcuni specifici valori di N: tutti e soli i numeri primi (diversi da 2 e 3). Esistono anche alcune versioni modificate: la più divertente è a mio parere quella che genera tutti e soli i primi di Fermat 🙂

Come può funzionare una cosa del genere? Come fa l’automa cellulare di Life a creare una successione a prima vista impredicibile come quella dei numeri primi? Il trucco è che applica il crivello di Eratostene, che è un algoritmo perfettamente definito. Se guardate il video, notate delle righe diagonali di astronavi in alto a destra: corrispondono per l’appunto ai numeri primi generati, che cancellano le astronavi relative ai loro multipli. Semplice a vedersi, un po’ meno a crearsi!

(H/T: Math Tango)