# Computational complexity of finding a (1D deterministic) CA that achieves a desired spacetime history “patch” after $t$ iterations

Question description:

Consider the problem of finding a minimum $n$-color $k$-state one-dimensional cellular automata (minimizing $k$ for some fixed value of $n$ or vice versa), with communication between cells defined by a 3-neighbor von Neumann relation, that recreates some fixed-size spacetime history "patch" (http://www.wolframscience.com/nksonline/page-960b-text) of an unknown cellular automata (e.g. some output of Wolfram's pseudorandom Rule 30 CA: http://en.wikipedia.org/wiki/Rule_30) initiating from a known seed of some specified size and geometry and evolved for $t$ iterations. Informally speaking, provided an array corresponding to an unknown n-color k-state CA evolved for a known number of iterations from a defined seed specifying initial conditions, can you provide me a sufficiently minimal CA to create given pattern (with the full understanding that there may be a diverse and non-unique set of solutions)?

Now let me make a strong (and possibly false) statement: "There is no known computational complexity for this problem, and in the general case, exhaustive search must be employed over the set of all possible $n$-color $k$-state cellular automata (with communication between cells defined by a 3-neighbor von Neumann relation) to find a minimal cellular automata capable of recreating a specified spacetime history provided an initial seed of some defined size and geometry. This is true even if we specify that $n = 2$, as for example Wolfram does for all of his elementary CA patterns. This is true regardless of any guarantee about the properties of the initial seed as long as $r$, the number of cells in the seed, is $<<N$, the number of cells in the specified spacetime history."

To what extent is the above statement true, and are there any good literature references that make any strong statements about the computational complexity of this problem? I've been able to find a lot of papers in the literature that talk about, say, using evolutionary algorithms to solve this so-called "cellular automata inverse" problem, but almost nothing that touches on the general case computational complexity of the problem.

Motivation: In Stephen Wolfram's "New Kind of Science", the central argument of the book seems to be that one can "mine the computational universe" for cellular automaton rules that at least emulate everything from patterns appearing on seashells and stripes on a zebras, to local deterministic models of reality (proven aphysical in Scott Aaronson's review of NKS (section 3.2): http://www.scottaaronson.com/papers/nks.pdf).

Saying nothing about whether emulating some pattern or process in nature yields insight into the underlying rules for the process, I'd like to be able to say something specific about the "hardness" of trying to actually actually emulate some fixed sized pattern with a sufficiently simple $n$-color $k$-state CA.

Update: Why is this problem not the Configuration REachability Problem (CREP)?

Quickly, and to simplify matters, I'd like to further specify that the one-dimensional CA we consider here should be deterministic in one direction, though not necessarily invertible (i.e. they could involve cumulative XOR calculations). Initial conditions (i.e. seed values) are always defined.

Now, the Configuration REachability Problem (CREP) asks if a given cellular automaton in one state, $X$, can evolve in some number of iterations $t$ to reach a state $Y$. This diverges from my question in two important ways:

(1) I'm not specifying a cellular automata. The problem is to find one that is sufficiently simple to reproduce some provided (finite) spacetime history (i.e. where the number of states or colors is restricted or minimized). This is not a straightforward decision problem.

(2) I'm interested in finding a CA that not only reaches the current state of a given spacetime history, but the entirety of the spacetime history. For example, if I run Wolfram's Rule 30 for some number of iterations from a one-dimensional seed of length $L$, making a triangle with a pseudo-random pattern, I would then simply give you an array encoding this triangle, and your job would be to find a simple $n = 2$ state cellular automata (minimizing for colors) that reproduces the triangle starting from the same initialization conditions.

In any case, for a deterministic one-dimensional CA starting from known initial conditions, determining reachability should be a matter of simply simulating the CA for a sufficiently time to generate the provided finite spacetime history.

The CONFIGURATION REACHABILITY PROBLEM:

Given a cellular automaton and a pair of configurations $\langle X,Y \rangle$; does exist an instant $t \geq 0$ such that starting from configuration $X$, the cellular automaton reaches configuration $Y$ after $t$ iterations?

is PSPACE-complete.

If you drop $t$ from the input then you can achieve any r.e. degree of unsolvability:

Theorem 3.1: For any recursively enumerable degree $d$ there is a one-dimensional celullar automaton whose Reachability Problem for finite configurations is of degree $d$

I'm not an expert, but I think there are a lot of work on restricted classes of CAs, too; for example:

Andrea Clementi and Russell Impagliazzo, The Reachability problem for finite cellular automata

Abstract: We investigate the complexity of the Configuration REachability Problem (CREP) for two classes of finite weakly predictable cellular automata: the invertible and the additive ones. In both cases we prove that CREP belongs to the "Arthur-Merlin" class CoAM.

EDIT

If you give the full spacetime history then the problem seems easy.

Given a full spacetime history $X_1,X_2,...,X_t$ you want to find a CA having $k$-neighbourhood, $k \in \{ 1,\ldots,max\{|X_i|\}\}$ that reproduces it (with $k$ as little as possible).

The minimum number of colors $c$ needed are obviously the number of colors that appear in the history (because there are no missing iterations).

You start with $k=1$ (1-neighbourhood) and with an empty ruleset $R$.

You examine each iteration from left to right and add to $R$ the required rules. For example if we have $c=2$ and during the scan of the $X_1\rightarrow X_2$ iteration you find:

  X_1: ...122....
X_2: ....1.....


then $R = R \cup \{ 122 \rightarrow 1 \}$. During the scan of each iteration you check that the new rules added are not in conflict with those already in $R$, otherwise you restart with the first iteration, $R = \emptyset$ and $(k+1)$-neighbourhood.

If you reach $X_t$ without conflicts the you can fill the missing rules randomly. The resulting CA is minimal with respect to the given spacetime history. The time complexity is $O(|n|^2)$ (assuming $O(1)$ access/update time to the current ruleset $R$).

• Isn't the REACHABILITY PROBLEM, while related to the question, asking about the ability to check if a given cellular automata can give rise to some defined, finite spacetime history? My question is more about the complexity of looking at some pair of configurations <X, Y> and then asking: "What minimal cellular automata can reach Y from X after 't' iterations? The REACHABILITY PROBLEM is more related to how fast we can scan through possible CA's during an exhaustive or restricted search, right? – WShon Dec 14 '13 at 12:38
• And of course, thank for reading through my question! – WShon Dec 14 '13 at 12:40
• Of course, intuition says that this problem should also be PSPACE-complete, however, I'm not quite sure how to prove it! – WShon Dec 14 '13 at 12:45
• @WShon: indeed you are right, I'll give a look to the papers I have. Perhaps the problem is also interesting (and probably hard enough :) even if you drop the minimality constraint: "Does exist a k-neighbour CA that can reach Y from X after t iterations?" – Marzio De Biasi Dec 14 '13 at 15:03
• Thanks for your help with this. Right, I'm of course open to knowing that a more constrained version of the problem I pose is hard or impractical in the general case. My aim here is to be able to make the statement that there isn't some efficient e.g. polynomial time solution to finding a simple CA that creates a fixed spacetime history pattern. – WShon Dec 14 '13 at 15:53