Descriptive Complexity of Sensitivity of Cellular Automata

Abstract

We study the computational complexity of determining whether a cellular automaton is sensitive to initial conditions. We show that this problem is ${\hat{I}}_2^0$-complete in dimension 1 and $\hat{I}{\pounds }_3^0$-complete in dimension 2 and higher. This solves a question posed by Sablik and Theyssier.

16 pages, 4 figures, accepted to AUTOMATA 2025. Addressed referee comments