Topological Entropy and Universal Cellular Automata

Abstract

Modern cellular automata theory distinguishes two genuinely different notions of computational capacity: local universality and global universality. The latter is known to be a strictly stronger property, as no reversible cellular automaton can be globally universal, whereas reversible locally universal cellular automata do exist. Our results further explore the gap between these fundamental computational classes, for which general structural results remain scarce. We introduce a new independent separation through topological entropy. We prove that, in dimension one, there exist locally universal cellular automata with zero topological entropy, while no globally universal cellular automaton can have zero topological entropy. In each dimension larger than one, every globally universal cellular automaton must even have infinite topological entropy. Topological entropy thus links an asymptotic property from topological dynamics with the computational-theoretic notions of universality for cellular automata.