Message Boards Message Boards

0
|
1930 Views
|
0 Replies
|
0 Total Likes
View groups...
Share
Share this post:

Any example of periodic columns in asymmetrical 1D cellular automata?

Posted 3 years ago

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.) This would be a generalized attack on the problem, showing that whole class doesn't exist. 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.

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 do not exist or are very rare, partially based on having searched some and not found any, but I'd love to have someone else try their hand at finding one.

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.

POSTED BY: Trevor Cappallo
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract