(\mu\)-Limit Sets of Cellular Automata from a Computational Complexity Perspective

This paper concerns \(\mu\)-limit sets of cellular automata: sets of configurations made of words whose probability to appear does not vanish with time, starting from an initial \(\mu\)-random configuration. More precisely, we investigate the computational complexity of these sets and of related dec...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2015-06
Main Authors: Boyer, Laurent, Delacourt, Martin, Poupet, Victor, Sablik, Mathieu, Theyssier, Guillaume
Format: Article
Language:English
Subjects:
Automata theory
Cellular automata
Complexity
Computation
Configurations
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper concerns \(\mu\)-limit sets of cellular automata: sets of configurations made of words whose probability to appear does not vanish with time, starting from an initial \(\mu\)-random configuration. More precisely, we investigate the computational complexity of these sets and of related decision problems. Main results: first, \(\mu\)-limit sets can have a \(\Sigma\_3^0\)-hard language, second, they can contain only \(\alpha\)-complex configurations, third, any non-trivial property concerning them is at least \(\Pi\_3^0\)-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:2331-8422