Automi Cellulari e Reversibilità

Cellular automata are introduced in the work, as well as their principle properties. The main focus is on the reversebility of the global evolution law and its decidability, using de Bruijn graphs for the one-dimensional case, and Wang tiles for dimensions greater than one. Moreover many ways to construct reversible cellular automata are described.

Nel lavoro vengono presentati gli automi cellulari e ne vengono studiate le principali proprietà. In particolare è analizzata la reversibilità della legge evolutiva globale e la decidibilità di questa, utilizzando i grafi di de Bruijn per il caso unidimensionale, e o le piastrelle di Wang per dimensioni maggiori di uno. Vengono inoltre forniti vari metodi per costruire automi cellulari reversibili.