Considering that the answer does't look like a "basic question", I'll move it out of the "basic questions" thread. Also going to change S to K to prevent further confusion.dvgrn wrote: ↑June 23rd, 2023, 1:34 pmOops. Sorry, reading on a small laptop screen, and not looking close enough. I did wonder why it was 5 in particular...I'm very inclined to guess that the answer is "no", on the grounds that basically you're building a base-S counter with M*N digits, and any reasonable way to do that will require carry operations that affect neighboring digits farther away than range 1.wirehead wrote: ↑June 23rd, 2023, 12:54 pmSo, here is the revised question: For an arbitrary rectangular box patch in a plane, dimensions MxN, can there be a constructed rule using the range-1 Moore neighborhood with S states, and a pattern in that rule that fits in the box, that oscillates with a period of S^(M*N) ?
I didn't want to rule out some clever way of implementing some improbable 2D equivalent of a superpermutation -- but see below...
Quite possibly we can dispose of the not-a-torus case easily:
- If the MxN oscillator has to have S^(MxN) states, then one of the states is the all-cells-OFF state. Let's call that PHASE0.
- The state following all-OFF MxN has to be some state other than all-OFF MxN. Let's call that phase of the oscillator PHASE1.
- However, a non-toroidal infinite universe has an unbounded number of all-OFF MxN boxes.
- CA rules are deterministic, so all of the all-OFF MxN boxes that overlap with the target box must also go to the same PHASE1.
- The only way that that is possible is if all cells in PHASE1 are the same state.
- Therefore we're going to run into trouble as soon as we've cycled through every all-state-k MxN boxes, for all k in S.
I think the same argument applies on a torus, actually. The "what happens after PHASE0" question has the same exact problem when you consider shifted rectangular areas on the torus.
That puts an extremely low lower bound on the question: we can achieve a period-S oscillator! How much higher we can push the lower bound... is a much more interesting question.
So here are the constraints:
- Moore neighborhood, range-1, standard square grid.
- Unbounded universe outside of the box.
- Box is a MxN rectangle.
- Rule has K states, but the behavior can be anything.
- The pattern can be anything, but it cannot escape the box during the entire period.
- Find the maximum period of an arbitrary pattern in an arbitrary rule following the above constraints.
H. H. P. M. P. Cole's results spreadsheet