A New Kind of Science: The NKS Forum (http://forum.wolframscience.com/index.php)
- Pure NKS (http://forum.wolframscience.com/forumdisplay.php?forumid=3)
-- Functions to find the predecessor states of a given CA state (http://forum.wolframscience.com/showthread.php?threadid=580)

Functions to find the predecessor states of a given CA state

Attached are two functions for finding the set of states that precede a given state in a cellular automaton evolution.

The first function is the obvious brute-force method.

The second function uses a pruned search to efficiently find all the states.

Reversing a CA is more like a nondeterministic multiway system. One appends each of the tentative previous conditions successively using Fold. Multiway systems are discussed in NKS on p.204.

I think it is a little simpler to view it that way.


NeighborsToRule[ls_] := Prepend[Most[ls], x___] -> Prepend[ls, x]

turns a neighbor list into a Rule for use in a multiway evolution. It is nondeterministic as it depends on the string of 0's and 1's in question.

NDMultiway[rn_,ic_]:=With[{rl=Table[NeighborsToRule/@IntegerDigits[Flatten[Position[Reverse@IntegerDigits[rn,2,8],i]]-1,2,3],{i,0,1}]},Fold[Flatten[Function[ls,ReplaceList[ls,rl[[1+#2]]]]/@#,1]&,Table[IntegerDigits[i,2,2],{i,0,3}],ic]]

Here is the cylic version.

CyclicNDMulti[rn_,ic_]:=With[{rl=Table[NeighborsToRule/@IntegerDigits[Flatten[Position[Reverse@IntegerDigits[rn,2,8],i]]-1,2,3],{i,0,1}]},Drop[#,2]&/@Select[Fold[Flatten[Function[ls,ReplaceList[ls,rl[[1+#2]]]]/@#,1]&,Table[IntegerDigits[i,2,2],{i,0,3}],ic],Take[#,2]==Take[#,-2]&]]

Those are interesting in their own right and more general. But not exactly the same as the backward CA problem.

A backward CA evolution may be impossible for a certain number of steps, from some initial condition. Some states are "garden of Eden" states, only possible as initial conditions. If a chain backward reaches one of these, it has no possible continuation, and that portion of the tree halts.

Now, if one gets a state by running a given CA forward for 100 steps, then of course there is some predecessor 100 steps before, at least one. But of any state of that width, in general, it is not true that it must have a predecessor n steps before under that CA rule.

One way one can starting looking at this, is to ask what portion of the possible sequences of a given width can still remain after some number of steps according to a given rule - as a measure of how the (forward) CA mapping "contracts" the possibility space. For example, what portion of the possible bit strings of lengths 1 to 16 can remain after say 4 steps of rule 90, with periodic boundary condition.

One finds (in this specific case, rule 90 etc) the answer depends on the length of the string and in particular on the number of times that length is divisible by 2. Start rule 90 from every possible initial condition up to a given length and run it forward for 4 steps, and then take the length of the union of the last steps of each run. You get the number of remaining distinct states -


{1, 1, 4, 1, 16, 16, 64, 1, 256, 256, 1024, 256, 4096, 4096, 16384, 256}


Which has minimums (as a portion of total possible states) at lengths 2^n, reductions when hitting a width divisible by a higher power of 2 (e.g. 12), etc. If you increase the number of steps to 8, the number of remaining states is the same for all of them except the last, which drops to 1.

If one asks exactly the same question of rule 110, after 4 steps one gets surviving states -


{1, 1, 1, 5, 2, 19, 36, 69, 145, 247, 496, 935, 1743, 3375, 6407, 12085}


And after 8 -


{1, 1, 1, 5, 1, 19, 15, 45, 109, 142, 320, 515, 937, 2017, 3526, 7021}


While these surviving state numbers are increasing, they go up slightly less fast than the total number of possible states (which doubles for each unit of extra length), so the whole "possibility space contraction" factor is slightly larger for the longer widths.
Plenty here to investigate, anyway.

One might see the same sort of thing in multiway systems that include reduction of possibilities, and also allow some replacement rules that specify a branch just halts, with successor state equal to the empty set.

I'm not completely sure what Jason is talking about, but the idea of looking at strings produced after n steps reminds me of Lydia Chilton's project at the NKS Summer School in 2003. This had been looked at previously, but I don't have a reference.

As for backward CA evolution, that is just a multiway evolution.

Use MultiStep[rn_,ls_]:=Union[Flatten[CyclicNDMulti[rn,#]&/@ls,1]]

and

MultiEvo[rn_,init_,k_]:=NestList[MultiStep[rn,#]&,{init},k]

Note that this is a multiway built up from multiways. I think the noncyclic version is more interesting (with NDMultiway).

Could there be a way to understand reducible multiway systems as being the backward evolution of some straightforward system like a CA?