5
$\begingroup$

The game of life is one of the most famous cellular automata in 2D. It has a variety of objects, some of them are moving like gliders, some have an oscillating behavior and others do not change at all, i.e. are still lives.

I am interested in the computational complexity of finding still lives. Especially in a restricted setting: by adding constraints to fix some cells to be dead or alive. In this setting, it becomes an extension problem: Starting from an initial pattern and asking whether it can be extended to form a still life.

So far, I was able to prove the NP-completeness of the following decision problem (by reducing planar circuit SAT to it):

Problem: STILL-LIFE
Input: A pair of numbers $(n,m)$ denoting the size of a rectangular grid $G$ with $n$ rows and $m$ columns. Two disjoint subsets $S_{\mathrm{dead}},S_{\mathrm{alive}} \subseteq G$.
Output: Does there exists a pattern $p:G\to\{\mathrm{dead},\mathrm{alive}\}$ s.t. $p$ is a still life and $p$ is dead on $S_{\mathrm{dead}}$ and alive on $S_{\mathrm{alive}}$.

Now I am interested in the following questions:


Question 1+2: Let $S_{\mathrm{dead}} \cup S_{\mathrm{alive}}$ be a 1D subset of $k$ cells in $G$ i.e. we fix $k$ consecutive cells (either vertical or horizontal [see figure]). What is the computational complexity of STILL-LIFE-1D in that case? What about the more general case if $S_{\mathrm{dead}} \cup S_{\mathrm{alive}}$ is a rectangle?

Example still life, with crosssection in red.

The same can be asked for the infinite setting when the grid covers the whole plane ($G = \mathbb{Z}^2$). But I want to reformulate it a bit:

Question 3+4: Does every 1D pattern of cells appear as a cross-section of a still life? Here the input is a 1D pattern of length $k$ and the question to decide is whether there exists a still life extension or not (Note: There is no restriction on the size of the pattern). Is this question decidable? Same question for a rectangular initial pattern.

$\endgroup$
3
  • $\begingroup$ Did you try to construct suitable extensions and use induction? $\endgroup$
    – greybeard
    Dec 4 '21 at 21:20
  • $\begingroup$ What do you mean by "$p$ is a still life" when $p$ is a finite pattern? Do you mean that when you extend $p$ into an infinite configuration using only dead cells, you get a fixed point of the CA? $\endgroup$ Dec 5 '21 at 6:46
  • $\begingroup$ Yes, exactly. Sorry if I was unclear in my description of the problem. You are right, the CA is normaly defined on the infinite grid. With suitable boundary conditions you can define an analog CA on a finite grid. $\endgroup$
    – ortofoxy
    Dec 5 '21 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.