Any idea of the surface...

For general discussion about Conway's Game of Life.
Post Reply
User avatar
Pilou
Posts: 63
Joined: January 20th, 2012, 5:08 am
Contact:

Any idea of the surface...

Post by Pilou »

...x * y, yet entierely explored as start figures ?

5 * 5, 10 * 10, 20 * 20,...?
Is beautiful that please without concept :)
p46beth
Posts: 345
Joined: June 18th, 2010, 8:18 pm

Re: Any idea of the surface...

Post by p46beth »

???
What are we talking about?
User avatar
Pilou
Posts: 63
Joined: January 20th, 2012, 5:08 am
Contact:

Re: Any idea of the surface...

Post by Pilou »

All start's combinaisons possible for a surface x,y (a bounding box)
example (symmetry or rotation are not inspected)
for a surface 1 * 1 there are 2 possibilities
for a surface 1 * 2 there are 4 possibilities
for a surface 1 * 3 there are 5 possibilities
for a surface 2 * 2 there are 14 possibilities
for a surface 2 * 3 there are 1 248
for a surface 3 * 3 there are 643 531
etc...
Is beautiful that please without concept :)
User avatar
Wojowu
Posts: 210
Joined: October 1st, 2011, 1:24 pm

Re: Any idea of the surface...

Post by Wojowu »

I think he means number of possible patterns in x*y bounding box, excluding rotations/reflections. There is function to compute this, but I don't know it exactly
First question ever. Often referred to as The Question. When this question is asked in right place in right time, no one can lie. No one can abstain. But when The Question is asked, silence will fall. Silence must fall. The Question is: Doctor Who?
User avatar
Pilou
Posts: 63
Joined: January 20th, 2012, 5:08 am
Contact:

Re: Any idea of the surface...

Post by Pilou »

number of possible patterns in x*y bounding box, excluding rotations/reflections.
Yes that is exactly that :)

If the surface 5*5 is fully explored, no need to search inside for find something new! :)

So at this date any idea of the biggest size of the bounding box fully explored ?
Is beautiful that please without concept :)
User avatar
apg
Moderator
Posts: 3007
Joined: June 1st, 2009, 4:32 pm

Re: Any idea of the surface...

Post by apg »

I think he means number of possible patterns in x*y bounding box, excluding rotations/reflections. There is function to compute this, but I don't know it exactly
It's possible using Burnside's Lemma, although we have to consider five separate cases:

Rectangular:
2m by 2n: (2^(4mn) + 2^(2mn) + 2^(2mn) + 2^(2mn))/4
2m+1 by 2n: (2^(4mn + 2n) + 2^(2mn + n) + 2^(2mn + 2n) + 2^(2mn + n))/4
2m+1 by 2n+1: (2^(4mn + 2n + 2m + 1) + 2^(2mn + n + 2m + 1) + 2^(2mn + 2n + m + 1) + 2^(2mn + n + m + 1))/4

Square:
2k by 2k: (2^(4k²) + 2^(2k²) + 2^(2k²) + 2^(2k²) + 2^(k²) + 2^(k²) + 2^(2k² + k) + 2^(2k² + k))/8
2k+1 by 2k+1: (2^(4k² + 4k + 1) + 2^(2k² + 3k + 1) + 2^(2k² + 3k + 1) + 2^(2k² + 2k + 1) + 2^(k² + 2k + 1) + 2^(k² + 2k + 1) + 2^(2k² + 3k + 1) + 2^(2k² + 3k + 1))/8

Also, you can replace any '2^' with 'n^' for the equivalent formula for n-state cellular automata.
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
Tropylium
Posts: 421
Joined: May 31st, 2011, 7:12 pm
Location: Finland

Re: Any idea of the surface...

Post by Tropylium »

calcyman wrote:
I think he means number of possible patterns in x*y bounding box, excluding rotations/reflections. There is function to compute this, but I don't know it exactly
It's possible using Burnside's Lemma, although we have to consider five separate cases:
(…)
Doesn't suffice for excluding translations, tho. This still counts a pattern such as "O.." distinct from a pattern such as ".O." (An extra constraint needed seems to be having cells on all edges of the bounding box in consideration.)

Infinite growth studies cover at least the entirety of the 5x5, 2x12 and 1x39 areas (possibly a little higher?), but I don't think that necessarily counts as having "entirely explored" the start figures in question. Eg. there might be a 5x5 pattern that evolves into some (larger) novel oscillator, but this result wasn't recorded?

All oscillators up to at least 6x7 are apparently known (according to the LifeWiki article on Mold). I'm not sure where the limit is on spaceships.

—For exhausting "small" patterns, I'm tempted to agree that the bounding box is a better constraint than the amount of live cells; the combinatorics of glider/still life/methuselah collisions start piling up ridiculously fast.
Post Reply