Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.14569 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- We consider the problems of characterizing and testing the stability of cellular automata configurations that evolve on a two-dimensional torus according to threshold rules with respect to the von-Neumann neighborhood. While stable configurations for Threshold-1 (OR) and Threshold-5 (AND) are trivial (and hence easily testable), the other threshold rules exhibit much more diverse behaviors. We first characterize the structure of stable configurations with respect to the Threshold-2 (similarly, Threshold-4) and Threshold-3 (Majority) rules. We then design and analyze a testing algorithm that distinguishes between configurations that are stable with respect to the Threshold-2 rule, and those that are $ε$-far from any stable configuration, where the query complexity of the algorithm is independent of the size of the configuration and depends quadratically on $1/ε$.