|国家预印本平台
首页|Descriptive Complexity of Sensitivity of Cellular Automata

Descriptive Complexity of Sensitivity of Cellular Automata

Descriptive Complexity of Sensitivity of Cellular Automata

来源:Arxiv_logoArxiv
英文摘要

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.点此复制

评论