μ-Limit sets of cellular automata from a computational complexity perspective

作者：

Highlights：

• We characterize the set of μ-limit sets of cellular automata.

• We prove that the language of these limit sets can be Σ3-complete.

• We prove a Rice theorem for μ-limit sets of cellular automata.

摘要

•We characterize the set of μ-limit sets of cellular automata.•We prove that the language of these limit sets can be Σ3-complete.•We prove a Rice theorem for μ-limit sets of cellular automata.

论文关键词：Cellular automata,μ-Limit sets,Rice theorem,Arithmetical hierarchy

论文评审过程：Received 12 June 2014, Revised 23 March 2015, Accepted 18 May 2015, Available online 23 June 2015, Version of Record 25 August 2015.

论文官网地址：https://doi.org/10.1016/j.jcss.2015.05.004