Discussion on question by Baaing Cow: Stabilization of a pattern in Conway's Game of Life

Feeds

18:47

Q: Stabilization of a pattern in Conway's Game of Life

Given a 8x8 array, return the number of generations in Conway's Game of Life that it will take for it to stabilize. "To stabilize" means to oscillate at a fixed period (including a period of 1) excluding all escaping gliders or spaceships. If an initial state does not stabilize in 2^20 generatio...

Quintec

If there is nothing left on the 10x10 array (but things moving outside of it), does it count as stable?

flawr

Do we just have to consider the 10x10 square for a repeating state? Why do you expect there to be another algorithm thatn bruteforce that just stops at the first recurring state? (I don't think fastest-algorithm is really a suitable criterion here.)

There seem to be a lot of open questions. Please use the sandbox for your challenges first, as advised when submitting a challenge.

Digital Trauma

It is (theoretically) possible to implement a Turing machine in Conway's Game of Life. Therefore I think this problem degenerates to solving the halting problem. In other words, there will be classes of input arrays for which you'll have to check an unbounded number of iterations to determine stabilization. That's before you even try to determine time complexity of a given solution.

Riker

I've edited this to make it re-openable (I believe) by limiting the bounding box and changing it to fastest-code with test cases you'll have to decide. Are you okay with these changes? (personally I'd make it code-golf and forgo the whole speed thing altogether, but this is more in line with what you had) If you are, I'll vote to reopen.

Anonymous

If an initial state does not stabilize in 2^20 (or a million flat) - is it 2^20 or one million for the limit? Stating both is unclear. Is there an upper limit we can assume for the period of a stable pattern (aside from the 2^20 or one million)?

user202729

18:47

@Riker Uh huh? How can you be sure that OP has some test cases to test?

Note that all algorithms will take O(1), because 2^20 is a fixed number.

Riker

@user202729 it's not hard to come up with some, I knew that when I edited it. OP needs to contribute some but I think they can do that.

Balzola

On a finite grid, Conway's game of life is not equivalent to a Turing Machine, that has infinite memory. After a number of iterations, this degenerate game of life will necessarily enter a configuration he had once in the past, and hence will follow a cyclic evolution from there. So the halting problem IS decidable: you just have to run the game till it cycles, and this only requires finite time.

l4m2

1. Is "generations in Conway's Game of Life that it will take for it to stabilize." the first time an existed universe appear or the first universe that will appear again? 2. What test data?

Riker

@l4m2 both of those issues should be fixed now.

Baaing Cow

@DigitalTrauma A Turing machine won't fit in an 8x8 grid; plus, I said if it doesn't stabilize in 2^20 generations, it never will.

Anders Kaseorg

18:47

Your reference answers are wrong. The R-pentomino, for example, evolves to a stable configuration plus six gliders at generation 1103. You then need to wait for those gliders to crash into the boundary of the grid before the result is truly stable by your definition. (And you still haven’t told us exactly where the boundary of the grid is?)

Baaing Cow

@AndersKaseorg I edited my question. The boundary of the grid isn't an exact place; I'm just saying the pattern can evolve until it is a 1024x1024 pattern, then, it stays that size. I'm thinking of removing the 1024x1024 part.

Anders Kaseorg

Your edits say to exclude escaping gliders and spaceships, but now you need to define exactly what gliders and spaceships are and what it means for one to be escaping. That isn’t just nit picking, I’m legitimately not sure how one would define that precisely (much less compute it), especially when taking into account that the potential interaction radius of a glider is larger than the glider itself.

If you wait until everything hits the 1024×1024 boundary, at least you have a chance at defining an objective result. But you do still need to finish defining that boundary. If it’s dynamically placed when the pattern gets big enough, what happens when a width 1023 pattern grows in both directions simultaneously to width 1025? I’d really recommend keeping everything as simple as possible: fix the boundary in place at the start with the initial pattern centered. (And add the guarantee that the initial pattern is 8×8 or at least even×even.) Dealing with the boundary shouldn’t be the hard part.

Jo King

I'm not sure how you can enforce the 512 mB limit, nor why it's necessary.

Balzola

It is not like it's been studied over and over again :) A good starting point read is twimgs.com/ddj/abrashblackbook/gpbb17.pdf and twimgs.com/ddj/abrashblackbook/gpbb18.pdf from Michael Abrash's "Black book".

next day → last day (18 days later) »

all rooms