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

•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. This paper concerns μ-limit sets of cellular automata: sets of configurations made of words whose probabili...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2015-12, Vol.81 (8), p.1623-1647
Main Authors: Boyer, L., Delacourt, M., Poupet, V., Sablik, M., Theyssier, G.
Format: Article
Language:English
Subjects:
Arithmetical hierarchy
Cellular automata
Computer Science
Discrete Mathematics
Rice theorem
μ-Limit sets
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•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. This paper concerns μ-limit sets of cellular automata: sets of configurations made of words whose probability to appear does not vanish with time, starting from an initial μ-random configuration. More precisely, we investigate the computational complexity of these sets and of related decision problems. Main results: first, μ-limit sets can have a Σ30-hard language, second, they can contain only α-complex configurations, third, any non-trivial property concerning them is at least Π30-hard. We prove complexity upper bounds, study restrictions of these questions to particular classes of CA, and different types of (non-)convergence of the measure of a word during the evolution.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2015.05.004