[HN Gopher] 29-year-old Conway conjecture settled
___________________________________________________________________
29-year-old Conway conjecture settled
Author : OscarCunningham
Score : 164 points
Date : 2022-01-16 13:21 UTC (9 hours ago)
(HTM) web link (cp4space.hatsya.com)
(TXT) w3m dump (cp4space.hatsya.com)
| fnord77 wrote:
| would like to see a live animation of this
| rnestler wrote:
| 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 ;)
| OscarCunningham wrote:
| 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/3705710146540011
| 54/...
| ted_dunning wrote:
| Just off-hand, this looks like a great way to build long-
| period oscillators.
| jacquesm wrote:
| Lots of people will miss the joke.
| ridaj wrote:
| It's missing an "/s" at the end to make it passable
| inimino wrote:
| With this audience, that joke just fell flat and stayed there
| for all time.
| plutonorm wrote:
| The joke was so bad that it never even stood up, it just is
| and always has been dead.
| eps wrote:
| It _is_ interesting to see what 's happening _around_ this
| pattern, so I won 't be too sure that it was indeed a joke.
| Someone wrote:
| 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 x 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.
| peterburkimsher wrote:
| 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 Torma-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 wrote:
| 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.
| peterburkimsher wrote:
| 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
| mg wrote:
| 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?
| [deleted]
| danielleconway wrote:
| 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.
| jacquesm wrote:
| Related or coincidence?
| cesaref wrote:
| 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)
| mg wrote:
| 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 wrote:
| "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.
| xayfs wrote:
| andrewthehacker wrote:
| 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.
| dskloet wrote:
| Who is Danielle Conway? Google links me to some lawyer.
| [deleted]
| danielleconway wrote:
| 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".
| charlieyu1 wrote:
| I have to say I don't understand this, because a 2x2 square is
| already stable
| andrewthehacker wrote:
| 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]
| tasha0663 wrote:
| 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 wrote:
| > 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
| Diggsey wrote:
| 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.
| [deleted]
| [deleted]
| prideout wrote:
| 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.
| OscarCunningham wrote:
| 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/
| prideout wrote:
| 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.
| smitty1e wrote:
| > 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.
| alisonkisk wrote:
| The theorem is whether there exists an "isolated" state, one that
| is unreachable from every other state.
| goldenkey wrote:
| 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 wrote:
| 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.
| cma wrote:
| Is that only with the stabilizers shown in yellow, or do
| they have some other purpose?
| andrewthehacker wrote:
| 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.
| OscarCunningham wrote:
| 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.
| contravariant wrote:
| > 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.
| kevincox wrote:
| 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.
| contravariant wrote:
| 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.
| dvgrn wrote:
| 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.
___________________________________________________________________
(page generated 2022-01-16 23:00 UTC)