Descriptive Complexity of Sensitivity of Cellular Automata
Descriptive Complexity of Sensitivity of Cellular Automata
We study the computational complexity of determining whether a cellular automaton is sensitive to initial conditions. We show that this problem is $\Pi^0_2$-complete in dimension 1 and $\Sigma^0_3$-complete in dimension 2 and higher. This solves a question posed by Sablik and Theyssier.
Tom Favereau、Ville Salo
计算技术、计算机技术
Tom Favereau,Ville Salo.Descriptive Complexity of Sensitivity of Cellular Automata[EB/OL].(2025-04-07)[2025-04-27].https://arxiv.org/abs/2504.05012.点此复制
评论