29-year-old Conway conjecture settled(cp4space.hatsya.com)
cp4space.hatsya.com
29-year-old Conway conjecture settled
https://cp4space.hatsya.com/2022/01/14/conway-conjecture-settled/
61 comments
NOTE: The central patch which settled the conjecture is a chunk of an infinite repetitive configuration composed of 2x2 "blocks" and S-looking shapes "snakes". Given that the block-square pattern is somewhat well known in CGOL, it's likely that multiple people have created still configurations with the conjectured property without realizing it at the time.
Is there anything in IRL physics with this property?
"If it exists, it is "primordial" because it's absolutely impossible to create this configuration from a previous, different configuration".
edit: Like maybe a topological kink. I think it's been suggested that Alcubierre drives are physically possible, except there is no physically-legal way to create them starting from flat spacetime. I.e. it'd be alright if one existed because it "always existed".
"If it exists, it is "primordial" because it's absolutely impossible to create this configuration from a previous, different configuration".
edit: Like maybe a topological kink. I think it's been suggested that Alcubierre drives are physically possible, except there is no physically-legal way to create them starting from flat spacetime. I.e. it'd be alright if one existed because it "always existed".
Spacetime, energy, the laws? All the particles seem to come and go.
Here is the configuration of live and
dead cells, surrounded by an infinite
background of grey “don’t care” cells:
[deleted]
The grey cells marked "don't care" can be on or off, and the resulting pattern will still have the property that it must exist from the start. Some of those said "don't care" cells can also be turned on to form a stable configuration, which is additionally nice.
Related or coincidence?
This is just defining the edge of the pattern they are discussion. They are saying 'if you see this pattern with any surrounding cells at any point T, then the given cells must also match at time T-1'.
If you look at the pattern, you'll see that some of the cells on the edge do not have 2 or 3 neighbours, so if you place this pattern in isolation in a field of empty cells, it won't survive, but there will be multiple possible ways to make this pattern survive (so a choice of cells to make the edge cells add to 2 or 3)
If you look at the pattern, you'll see that some of the cells on the edge do not have 2 or 3 neighbours, so if you place this pattern in isolation in a field of empty cells, it won't survive, but there will be multiple possible ways to make this pattern survive (so a choice of cells to make the edge cells add to 2 or 3)
Oh! So if you ever walk around in the wonderful world of Conway and encounter this pattern, then it will have existed since the beginning of time. But most probably it will disappear right now because your presence will disturb the stabilizing patterns around it.
"Don't care" cells is a designation saying the state of those cells doesn't impact the prior state requirement that they wanted to prove.
For those on a command-line, the Game of Life configuration looks like a series of rows of squares. 3 on the first row, 5 on the second row, 5 on the third row, then 3 on the last row. There are a total of 3 + 5 + 5 + 3 = 16 squares.
The fact that this is a base 2^n number seems intriguing to me. There's a hypothesis that everything in the universe is easier in base 2, which I'm still looking into.
Here's another speculative hypothesis, which some expert here can most likely prove.
Can this "Godlike still-life" create every other configuration, using an off-by-one error in 1 bit?
Specifically, taking the 306-cell Törmä-Salo result, can all the Still Lifes, Oscillators, and Spaceships be achieved simply by flipping 1 bit (obviously a different bit for each configuration) in the original?
There's a (non-exhaustive, I think) collection of patterns on Wikipedia:
https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life#Exampl...
The fact that this is a base 2^n number seems intriguing to me. There's a hypothesis that everything in the universe is easier in base 2, which I'm still looking into.
Here's another speculative hypothesis, which some expert here can most likely prove.
Can this "Godlike still-life" create every other configuration, using an off-by-one error in 1 bit?
Specifically, taking the 306-cell Törmä-Salo result, can all the Still Lifes, Oscillators, and Spaceships be achieved simply by flipping 1 bit (obviously a different bit for each configuration) in the original?
There's a (non-exhaustive, I think) collection of patterns on Wikipedia:
https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life#Exampl...
Maybe it works out in base-2 because it's on 2 dimensions? ...and maybe the universe has some weird base-primes system because it actually have infinite dimensions.
Is the universe infinite?
"Two things are infinite: the universe and human stupidity; and I’m not sure about th’universe!"
-- Maybe Einstein. https://quoteinvestigator.com/2010/05/04/universe-einstein/
Prime numbers look a lot like stars (e.g. Converse, Heineken use 5-pointed stars). I'm particularly interested in Mersenne Primes, which are of the form 2^n - 1.
https://en.wikipedia.org/wiki/Mersenne_prime#:~:text=In%20ma....
Some of these prime numbers are even illegal when translated to other forms (e.g. DeCSS).
https://en.wikipedia.org/wiki/Illegal_number#Illegal_primes
"Two things are infinite: the universe and human stupidity; and I’m not sure about th’universe!"
-- Maybe Einstein. https://quoteinvestigator.com/2010/05/04/universe-einstein/
Prime numbers look a lot like stars (e.g. Converse, Heineken use 5-pointed stars). I'm particularly interested in Mersenne Primes, which are of the form 2^n - 1.
https://en.wikipedia.org/wiki/Mersenne_prime#:~:text=In%20ma....
Some of these prime numbers are even illegal when translated to other forms (e.g. DeCSS).
https://en.wikipedia.org/wiki/Illegal_number#Illegal_primes
Has this result appeared in any publications yet? It should be pretty easy to check, as the post says, but I'm curious to know if it will be written up. I'd be interested to see how they found the particular chunk of agar and whether there was evidence suggesting they look there.
I suspect this will get written up in a paper relatively soon, but it's too new for the journal wheels to have turned far enough yet. The original ... publicization, if not publication ... was in a post on the conwaylife.com forums, and there's some more detail there on the general method:
https://conwaylife.com/forums/viewtopic.php?p=140258#p140258
The previous "Grand^N Orphan" result involved a complete enumeration of the relevant 6x3 agars, but this "Unique Father" result was a partial enumeration of 6x6 agars, I think, just until a working example was found.
At least one independent verification has been done:
https://conwaylife.com/forums/viewtopic.php?p=140277#p140277
https://conwaylife.com/forums/viewtopic.php?p=140258#p140258
The previous "Grand^N Orphan" result involved a complete enumeration of the relevant 6x3 agars, but this "Unique Father" result was a partial enumeration of 6x6 agars, I think, just until a working example was found.
At least one independent verification has been done:
https://conwaylife.com/forums/viewtopic.php?p=140277#p140277
There was also some early discussion of the result by the authors on the ConwayLife Lounge on Discord:
https://discord.com/channels/357922255553953794/370571014654...
https://discord.com/channels/357922255553953794/370571014654...
Their post has a link to a self-published book about Game of Life looks really interesting. Any other recommendations? The only other cellular automata book I've seen is Wolfram's "New Kind Of Science", which I really dislike. Wolfram is so arrogant and long winded.
Toffoli[0] & Margolus’[1] Cellular Automata Machines (1987) is the CA bible, I guess. Andrew Adamatsky edited the encyclopedic Cellular Automata (2018). Ed Fredkin's[2] stuff on reversible CA is fascinating. Gerard Vichniac[3] wrote some great papers in the 80s, e.g. Simulating Physics with Cellular Automata (1984). Kenichi Morita[4] papers. Rudy Rucker[5] has written a lot of stuff on 1 and 2D CA, and worked as a CA programmer. Etc. There are a lot of papers. The very common finite element method of solving differential equations and PDEs is basically the same thing as CA - see e.g. Anderson's Computational Fluid Dynamics.
Attractors and approximations for lattice dynamical systems by Shengfan Zhou, 2002.
1954's Studies of Nonlinear Problems by Fermi, Ulam, Pasta, featuring a 1D CA. https://www.cs.princeton.edu/courses/archive/fall02/cs323/li...
Noether's theorem comes up frequently - that every symmetry of the system corresponds to a conservation law.[6]
Smooth Life is Stephan Rafler's very cool version of CGOL with every discrete aspect turned into a continuous one.[7]
[0] https://en.wikipedia.org/wiki/Tommaso_Toffoli
[1] https://people.csail.mit.edu/nhm/ https://en.wikipedia.org/wiki/Norman_Margolus
[2] https://en.wikipedia.org/wiki/Edward_Fredkin
[3] https://scholar.google.com.au/scholar?as_vis=1&hl=en&q=gerar...
[4] https://scholar.google.com/citations?user=kujUxFYAAAAJ&hl=en
[5] https://en.wikipedia.org/wiki/Rudy_Rucker
[6] https://en.wikipedia.org/wiki/Noether%27s_theorem
[7] best video of SmoothLife https://www.youtube.com/watch?v=KJe9H6qS82I
https://sourceforge.net/projects/smoothlife/files/
This slideshow by Rafler contains the best, most complete explanation of it I've found: https://www.youtube.com/watch?v=iyTIXRhjXII
Shadertoy version https://www.shadertoy.com/view/XtdSDn
Attractors and approximations for lattice dynamical systems by Shengfan Zhou, 2002.
1954's Studies of Nonlinear Problems by Fermi, Ulam, Pasta, featuring a 1D CA. https://www.cs.princeton.edu/courses/archive/fall02/cs323/li...
Noether's theorem comes up frequently - that every symmetry of the system corresponds to a conservation law.[6]
Smooth Life is Stephan Rafler's very cool version of CGOL with every discrete aspect turned into a continuous one.[7]
[0] https://en.wikipedia.org/wiki/Tommaso_Toffoli
[1] https://people.csail.mit.edu/nhm/ https://en.wikipedia.org/wiki/Norman_Margolus
[2] https://en.wikipedia.org/wiki/Edward_Fredkin
[3] https://scholar.google.com.au/scholar?as_vis=1&hl=en&q=gerar...
[4] https://scholar.google.com/citations?user=kujUxFYAAAAJ&hl=en
[5] https://en.wikipedia.org/wiki/Rudy_Rucker
[6] https://en.wikipedia.org/wiki/Noether%27s_theorem
[7] best video of SmoothLife https://www.youtube.com/watch?v=KJe9H6qS82I
https://sourceforge.net/projects/smoothlife/files/
This slideshow by Rafler contains the best, most complete explanation of it I've found: https://www.youtube.com/watch?v=iyTIXRhjXII
Shadertoy version https://www.shadertoy.com/view/XtdSDn
Cellular automata are not a common topic. The new book is definitely the best in terms of Game of Life in particular. Another recommendation might be Jarkko Kari's lecture notes, which cover the subject from a more academic perspective. Not coincidentally, he was the advisor of the two discoverers here.
https://users.utu.fi/jkari/ca2022/
https://users.utu.fi/jkari/ca2022/
These lecture notes look GREAT, thank you! I suppose that they are not a common topic due to their limited (or non-existent?) applicability. But, they are so fun.
> Experience is a bad guide to large configurations...
At least subjectively, one is given to:
- getting the test case working and
- assuming a linearity to the functionality when scaled to a production load.
Which becomes an important iteration when crawling out of the smoldering wreckage.
At least subjectively, one is given to:
- getting the test case working and
- assuming a linearity to the functionality when scaled to a production load.
Which becomes an important iteration when crawling out of the smoldering wreckage.
That's not what "large configurations" refers to.
would like to see a live animation of this
Maybe I'm getting this wrong, but in my understanding is that since with this configuration it must be the same for T amd T-1 one and so must already exist from the beginning. There is no state other than itself that leads to it.
So the still image is already the animation of it ;)
So the still image is already the animation of it ;)
I made an animation [0] by taking the given pattern and finding a 3 step predecessor of it. In accordance with the theorem the pattern is still present in the predecessor. So you can watch the other cells churn around it without changing the central region.
[0] https://media.discordapp.net/attachments/370571014654001154/...
[0] https://media.discordapp.net/attachments/370571014654001154/...
Just off-hand, this looks like a great way to build long-period oscillators.
Lots of people will miss the joke.
It is interesting to see what's happening around this pattern, so I won't be too sure that it was indeed a joke.
I don’t think it is for this discussion. You could put any pattern around it that doesn’t soon destroy this pattern (I would pick one that eventually destroys it. That takes away any possible misunderstanding about this pattern being indestructible)
Also, I think there’s no animation that shows the special property of this pattern.
Yes, you could show a grid with all other possible 30 × 24 cell grids, iterate over one iteration, and then show none of them evolves to the given pattern, but that grid would be way, way, way, too large (and that’s an under-, under-, understatement) for that to pop out (that’s a scientific term. See https://en.wikipedia.org/wiki/Visual_search#Feature_search) to our visual system.
Also, I think there’s no animation that shows the special property of this pattern.
Yes, you could show a grid with all other possible 30 × 24 cell grids, iterate over one iteration, and then show none of them evolves to the given pattern, but that grid would be way, way, way, too large (and that’s an under-, under-, understatement) for that to pop out (that’s a scientific term. See https://en.wikipedia.org/wiki/Visual_search#Feature_search) to our visual system.
[deleted]
It's missing an "/s" at the end to make it passable
Who is Danielle Conway? Google links me to some lawyer.
Hi! At the time of the article's publishing, I had my nickname set to "danielle conway" in the CGoL Discord server, and I guess apgoucher thought that was my full alias. I usually just contribute pseudonymously as either "danielle" or "dani".
[deleted]
I have to say I don’t understand this, because a 2x2 square is already stable
A 2x2 square's predecessor is not necessarily a 2x2 square - many patterns will evolve to a 2x2 square.
This conjecture is anout patterns whose predecessor must be the same pattern, which means they cannot be constructed by colliding gliders.
This conjecture is anout patterns whose predecessor must be the same pattern, which means they cannot be constructed by colliding gliders.
I was confused at first until I read how Conway first described it. His words are quoted at the end. It makes more sense when he describes it - something he had a wonderful knack for.
> I expect that there is a still life of such delicacy that in some essential sense it is its only ancestor – though obviously that sense must allow for fading configurations outside it, and probably allow for more.
Yes, that's was clearer to me too
Yes, that's was clearer to me too
Plenty of patterns are stable (in fact, infinitely many), but what we didn't have before today is a stable pattern which cannot be constructed from scratch. This is such a pattern, because the patch in the middle must have existed since Generation 0 and therefore is unable to be formed just from emptiness - "if it isn't there it won't be".
[deleted]
That is like God
So the most compact solution is a 2 x 2 surrounded 2s? Weird!
[deleted]
[deleted]
The theorem is whether there exists an "isolated" state, one that is unreachable from every other state.
No, that's what a Garden Of Eden state is and they are extremely different from the configuration for this theorem. A Garden of Eden state at time t has no possible states before time t - there is nothing that could have produced it. It can only be reached by starting with GoL set to it, it has no past - only a future.
https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_autom...
Conway's theorem asks whether there is a self-replicating pattern whose only ancestor is itself. By induction, this also means its only predecessor is also itself. The states that satisfy this theorem have infinite past and future states that all contain the same specific pattern.
https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_autom...
Conway's theorem asks whether there is a self-replicating pattern whose only ancestor is itself. By induction, this also means its only predecessor is also itself. The states that satisfy this theorem have infinite past and future states that all contain the same specific pattern.
> future states that all contain the same specific pattern.
Past yes, but probably not future surely? I see no reason such a pattern couldn't be broken by outside influence somewhere in the future.
Past yes, but probably not future surely? I see no reason such a pattern couldn't be broken by outside influence somewhere in the future.
If I am understanding correctly that is not the case. The point of the "don't care" squares in the diagram is that the pattern will continue no matter what they are so any outside interference is irrelevant. It won't be sufficient to change the pattern.
But if you leave those squares all empty it won't keep the original pattern, so I'm not sure how that can be right.
Right -- this discovery is about identical states extending into the past, not into the future.
A Conway's Life pattern that has to stay the same into the indefinite future would be an impenetrable wall, and we don't know of any such thing in the Life rule. It hasn't exactly been proved impossible, but nobody seriously thinks that such a thing exists.
I think it _can_ easily be proven that a finite stable (period 1) impenetrable wall can't exist. It's trivial to find a way to attack the corners, and almost equally trivial to find something that makes a change at any edge.
A Conway's Life pattern that has to stay the same into the indefinite future would be an impenetrable wall, and we don't know of any such thing in the Life rule. It hasn't exactly been proved impossible, but nobody seriously thinks that such a thing exists.
I think it _can_ easily be proven that a finite stable (period 1) impenetrable wall can't exist. It's trivial to find a way to attack the corners, and almost equally trivial to find something that makes a change at any edge.
Right you can break it, but can you prevent its reincarnation?
Well yeah, in fact it would be impossible to rebuild.
The configuration in the article is a Garden of Eden, but it is also a still life. Also, while the past is fixed, the future might look different from interference from outside.
It's technically not a Garden of Eden, because it has a predecessor, namely itself. But it is nearly a GoE, in the sense that it only has one predecessor.
Is that only with the stabilizers shown in yellow, or do they have some other purpose?
The purpose of the cells in yellow is to turn the patch relevant to this discussion into a still life: it's already got the property of "must exist in gen N-1 if it is in gen N" without those yellows, but this serves to keep it from destabilizing instantly.