1
$\begingroup$

Does anyone know of or is able to track down a 2-color, 1-D cellular automaton admitting an aperiodic initial configuration and a ruleset that is asymmetrical, and which has at least one (but not infinitely many) columns that are periodic or eventually periodic?

I realize that sounds like a lot, so a word on motivation. It's still unproven whether or not the center column of Rule 30 ever becomes periodic. (It doesn't, but a proof is elusive.) There are a couple of examples out there of rules that do have a central column which eventually or immediately cycles while other columns remain aperiodic (e.g. Rule 150), but every single one that I've seen has a symmetrical ruleset, meaning any symmetrical initial configuration can only reach states with the same axis of symmetry.

To keep things reasonable, I limit us to 2 colors (read: cell states) since if we add a third, there are no doubt uninteresting solutions which paint a line of the third color down the center, and then ignore it while carrying on processing actively with the other two colors. That said, I think we can allow range to be arbitrarily large without a similar pitfall, so rulesets could draw from e.g. the 5 cells above them instead of the typical 3, although going too high might turn out similarly unhelpful.

As additional clarification, such a CA would need to be on an open grid, not a torus. Periodic tiling in the initial row is fine so long as there's some finite, aperiodicity-seeding deviation from it at some point, e.g. the $0^\infty10^\infty$ classic start for Rule 30. (Someone please correct me if that is the wrong way to denote that.)

In short, I'm wondering if anyone knows of any example where an asymmetrical ruleset could maintain a periodic column, or has any thoughts on this issue as to why such an arrangement is or is not plausible. My guess is that such examples probably exist, but are rare. And again, another way to state the main constraint is that there must be one or more periodic columns along with aperiodic columns occurring both somewhere left and somewhere right of the periodic column—one whole side devolving into periodicity is not what we're after.

In lieu of a qualifying CA, I would also accept as an answer anyone with helpful insight/heuristic-based analysis/pointers to relevant material, etc.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Assuming there is a solution with 3 colors (I, too, believe that there are simple solutions when there are sufficiently many colors), it is sufficient to be able to simulate a given automaton $F$ with colors $0,1,2$ by an automaton $F'$ with colors $0,1$ (but with a larger range than $F$).

Associate equal length marker words $w_0=0000011, w_1=0000101, w_2=0001001$ to the symbols $0,1,2$ respectively: the essential thing is that occurrences of marker words in a configuration cannot overlap. Then, if $F$ maps e.g. the triplet $200$ to $1$, we define $F'$ so that whenever a configuration contains a block $w_2 w_0 w_0$, the middle $w_0$ is replaced by $w_1$ (this is well defined because markers cannot overlap), and similarly for other triplets of symbols. It does not matter how $F'$ is defined at locations where marker words do not occur. Then the action of $F$ e.g. on the configuration $0^\infty 10^\infty$ is simulated by running $F'$ on the configuration $(w_0)^\infty w_1 (w_0)^\infty$.

$\endgroup$
1
  • $\begingroup$ Nice idea. It also seems suggestive that color and range may be arbitrarily interchangeable in general given sufficient proportions, something akin to the tradeoff between states and symbols for Turing machines. $\endgroup$
    – Trevor
    Commented Jan 19, 2022 at 13:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .