Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2409.07065 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- Computing the configuration of any one-dimensional cellular automaton at generation $n$ can be accelerated by constructing and running a composite rule with a radius proportional to $\log n$. The new automaton is the original one, but with its local rule function composed with itself. Consequently, the asymptotic time complexity to compute the configuration of generation $n$ is reduced from $O(n^2)$-time to $O(n^2 / \log n)$, but with $O(n^2/(\log n)^3)$-space, demonstrating a time-memory tradeoff. Experimental results are given in the case of Rule 30.