29-year-old Conway conjecture settled

https://cp4space.hatsya.com/2022/01/14/conway-conjecture-settled/

230 54 5 years ago

cp4space.hatsya.com

alisonkisk• 5 years ago

The theorem is whether there exists an "isolated" state, one that is unreachable from every other state.

goldenkey• 5 years ago

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.

sp332• 5 years ago

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.

contravariant3• 5 years ago

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.

dskloet2• 5 years ago

Who is Danielle Conway? Google links me to some lawyer.

danielleconway3• 5 years ago

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".

dskloet2• 5 years ago

Cool. I was mostly curious if you're related to John?

charlieyu1• 5 years ago

I have to say I don’t understand this, because a 2x2 square is already stable

Diggsey• 5 years ago

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.

tasha0663• 5 years ago

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.

afterburner• 5 years ago

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

andrewthehacker3• 5 years ago

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".

galaxyLogic2• 5 years ago

That is like God

fnord77• 5 years ago

would like to see a live animation of this

rnestler• 5 years ago

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 ;)

OscarCunningham3• 5 years ago

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/...

jacquesm2• 5 years ago

Lots of people will miss the joke.

inimino• 5 years ago

With this audience, that joke just fell flat and stayed there for all time.

ridaj• 5 years ago

It's missing an "/s" at the end to make it passable

eps• 5 years ago

It is interesting to see what's happening around this pattern, so I won't be too sure that it was indeed a joke.

prideout2• 5 years ago

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.

OscarCunningham3• 5 years ago

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/

prideout2• 5 years ago

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.

yesenadam• 5 years ago

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

mg2• 5 years ago

    Here is the configuration of live and
    dead cells, surrounded by an infinite
    background of grey “don’t care” cells:

What are "don't care cells"? I thought cells in Conway's Game of Life are either alive or dead?

danielleconway3• 5 years ago

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.

jacquesm2• 5 years ago

Related or coincidence?

cesaref• 5 years ago

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)

mg2• 5 years ago

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.

NAHWheatCracker• 5 years ago

"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.

peterburkimsher2• 5 years ago

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...

q1w2• 5 years ago

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.

peterburkimsher2• 5 years ago

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

andrewthehacker3• 5 years ago

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.

smitty1e• 5 years ago

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.

nieve• 5 years ago

That's not what "large configurations" refers to.

irthomasthomas• 5 years ago

So the most compact solution is a 2 x 2 surrounded 2s? Weird!

perihelions• 5 years ago

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".

tim333• 5 years ago

Spacetime, energy, the laws? All the particles seem to come and go.

rspencer• 5 years ago

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.

dvgrn3• 5 years ago

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

dvgrn3• 5 years ago

There was also some early discussion of the result by the authors on the ConwayLife Lounge on Discord:

https://discord.com/channels/357922255553953794/370571014654...

29-year-old Conway conjecture settled

Related Stories