The topological entropy of cellular automata is uncomputable

Abstract

Abstract There is no algorithm which will take a description of a celluar automaton and determine whether it has zero topological entropy, or for any fixed ε > 0 compute its topological entropy to a tolerance e. Furthermore a set of aperiodic Wang tiles arising from Penrose's kite and dart tiles is used to demonstrate specific examples of cellular automata with a single periodic point but non-trivial non-wandering sets, which furthermore can be constructed to have arbitrarily high topological entropy.