Sensitivity of Cellular Automata: The Case of Variable Length Shifts
Diego Luis Alberto
We study the problem of the sensitivity to initial conditions of onedimensional permutation cellular automata induced by maximal finite prefix codes, suggested in previous works as a conjecture. Despite the fact that we could not obtain a result for the general case, we get an important advance for the subclass of permutation cellular automata corresponding to the case that the permutations defining the automaton are all the identity function. These cellular automata are called variable-length shifts, and in previous works they were referred to as elector automata. The main contribution in the present work is the proof that any variable length shift is sensitive to initial conditions, which is done by obtaining a combinatorial property to equivalent to the sensitivity for the case of cellular automata.
Keywords: Permutation cellular automata. Variable length shifts. Sensitivity to initial conditions. Dynamical systems. Codes.