gol-agars: Python scripts for enumerating and analyzing self-forcing agars

For scripts to aid with computation or simulation in cellular automata.
Post Reply
Ilkka Törmä
Posts: 16
Joined: December 3rd, 2019, 4:16 am
Contact:

gol-agars: Python scripts for enumerating and analyzing self-forcing agars

Post by Ilkka Törmä » February 17th, 2022, 4:30 am

I and Ville Salo have published Python scripts for enumerating self-forcing agars of given periods (in both space and time). By "self-forcing" we mean that the agar has exactly one chain of predecessors. In other words, if the agar oscillates at period p and goes through configurations a(1), a(2), ..., a(p), then the sole predecessor of a(p) is a(p-1), the sole predecessor of a(p-1) is a(p-2), and so on, up to a(1), whose sole predecessor is a(p). This is true even if we don't require the predecessors to be spatially periodic. By default, the script prunes the search space by requiring a(1) to be lexicographically minimal among all the a(i) and their shifted, mirrored and/or rotated versions. You can also search for agars with various symmetries, but then this pruning needs to be (at least partially) suppressed. This functionality is not documented yet, unfortunately.

The scripts can also be used to determine the set of cells whose values a given pattern forces in its predecessors, and to find subpatterns that force themselves to occur in their predecessors, like the patch we found that solved the Unique father problem.

The repository is a companion piece to our recent preprint, and one of the scripts verifies our computations.

You'll need Python 3 and the PySAT library to run the scripts.

HartmutHolzwart
Posts: 840
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: gol-agars: Python scripts for enumerating and analyzing self-forcing agars

Post by HartmutHolzwart » February 17th, 2022, 4:52 am

Exciting! Could we have a sneak preview of some results?

Ilkka Törmä
Posts: 16
Joined: December 3rd, 2019, 4:16 am
Contact:

Re: gol-agars: Python scripts for enumerating and analyzing self-forcing agars

Post by Ilkka Törmä » February 17th, 2022, 6:19 pm

HartmutHolzwart wrote:
February 17th, 2022, 4:52 am
Exciting! Could we have a sneak preview of some results?
Our results, and their proofs apart from the SAT solver computations, are in the preprint (you can download a pdf from the top right). It hasn't gone through peer review yet, so take the details with a grain of salt. We are confident about the big picture, though.
  • We solve the Generalized grandfather problem: For each n, there is a finite pattern that has an n-tick predecessor but not an (n+1)-tick predecessor. We give two constructions of these nth-generation orphans, both of which are easy to compute. The first one produces patterns whose diameter grows linearly in n and that are exactly nth-generation orphans. The second one (due to Adam Goucher) gives patterns whose diameter grows like sqrt(log(n)), but we don't know the exact k ≥ n for which they are kth-generation orphans.
  • We solve the Unique father problem: There is a finite pattern p such that all its predecessors contain p in the same position, and it can be completed into a finite still life. In particular, this still life has no glider synthesis.
  • We show that it is PSPACE-hard to determine whether a given finite pattern is an nth-generation orphan for some n, or whether it can occur arbitrarily late in the evolution of a universe. This means it is computationally much more difficult than NP-complete problems like Boolean satisfiability or (generalized) Sudoku. We suspect that this property is not even computable, but we can't prove it yet.
  • Then we have some more technical results about the dynamics of Life and the structure of its "limit set", meaning the set of patterns that are not nth-generation orphans for any n. For example, we show that if you take two n×n patterns that are in the limit set and want to glue them together so that the resulting pattern is still in the limit set, for large n you sometimes need a gap of at least n/15 cells between them (but we don't know if that, or any finite gap, is guaranteed to be enough).

HartmutHolzwart
Posts: 840
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: gol-agars: Python scripts for enumerating and analyzing self-forcing agars

Post by HartmutHolzwart » February 18th, 2022, 8:21 am

Thanks for the link. I was more thinking in terms of sample results of your script. But I definitely need to read through your paper!

Ilkka Törmä
Posts: 16
Joined: December 3rd, 2019, 4:16 am
Contact:

Re: gol-agars: Python scripts for enumerating and analyzing self-forcing agars

Post by Ilkka Törmä » April 27th, 2022, 3:39 am

HartmutHolzwart wrote:
February 18th, 2022, 8:21 am
I was more thinking in terms of sample results of your script.
Sorry for the delay. The repository now contains a folder of search results for some small-ish parameters: self-forcing still life agars of spatial period up to 6x6 (possibly incomplete for 6x6), and self-forcing period-2 agars of spatial period up to 7x7. I also added the option to search for these in other Life-like rules.

Post Reply