New blog post: Motorcycle graphs and the eventual fate of sparse Life, https://11011110.github.io/blog/2018/12/27/motorcycle-graphs-eventual.html
Motorcycle graphs and the eventual fate of sparse Life
10 plus ones
Shared publicly•View activity
- Is there something interesting to conclude from the P-completeness of motorcycle graphs to this class of Life-like automata?
Just thought about extending the P-completeness proof of motorcycle graphs to Gilbert tessellations. For uniform speeds there is no way to confine the motorcycle gadgets. But with non-uniform speed one could simulate confined gadgets in the sense that the artifact rays emanated could be made arbitrarily slow. That is, the motorcycle gadgets can be approximated arbitrarily close. Hence, Gilbert tessellations with non-uniform speed – still a generalization of motorcycle graphs – are P-complete.3w
- P-completeness of some life-like cellular automata — for instance Life Without Death (https://en.wikipedia.org/wiki/Life_without_Death) — is interesting. The proof for LwoD is based on similar structures. But if this behavior happens for random fields in LwoD, they need to be significantly sparser than 1%, because at 1% the field gets filled by the growth of unstructured blobs before the faster-growing shoots take over.3w
- It appears that LwoD at super-low densities will be a mix of filled and empty rectangles, because some 3-cell constellations quickly turn into four-way shoots while others appear to fill space, and also because some crashes of shoots stabilize while others produce a blob that expands to fill space from the crash site.3w
Add a comment...