Solving the initial value problem for cellular automata by pattern decomposition
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909978806190080 |
|---|---|
| author | Fukś, Henryk |
| author_facet | Fukś, Henryk |
| contents | For many cellular automata, it is possible to express the state of a given cell after $n$ iterations as an explicit function of the initial configuration. We say that for such rules the solution of the initial value problem can be obtained. In some cases, one can construct the solution formula for the initial value problem by analyzing the spatiotemporal pattern generated by the rule and decomposing it into simpler segments which one can then describe algebraically. We show an example of a rule when such approach is successful, namely elementary rule 156. Solution of the initial value problem for this rule is constructed and then used to compute the density of ones after $n$ iterations, starting from a random initial condition. We also show how to obtain probabilities of occurrence of longer blocks of symbols. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_24337 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Solving the initial value problem for cellular automata by pattern decomposition Fukś, Henryk Cellular Automata and Lattice Gases Dynamical Systems 37B15, 68Q80 For many cellular automata, it is possible to express the state of a given cell after $n$ iterations as an explicit function of the initial configuration. We say that for such rules the solution of the initial value problem can be obtained. In some cases, one can construct the solution formula for the initial value problem by analyzing the spatiotemporal pattern generated by the rule and decomposing it into simpler segments which one can then describe algebraically. We show an example of a rule when such approach is successful, namely elementary rule 156. Solution of the initial value problem for this rule is constructed and then used to compute the density of ones after $n$ iterations, starting from a random initial condition. We also show how to obtain probabilities of occurrence of longer blocks of symbols. |
| title | Solving the initial value problem for cellular automata by pattern decomposition |
| topic | Cellular Automata and Lattice Gases Dynamical Systems 37B15, 68Q80 |
| url | https://arxiv.org/abs/2512.24337 |