8 ms·
29-year-old Conway conjecture settled
- deleted 5y ago[deleted]
- smitty1e 5y 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 5y agoThat's not what "large configurations" refers to.
- alisonkisk 5y agoThe theorem is whether there exists an "isolated" state, one that is unreachable from every other state.
- goldenkey 5y agoNo, 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_automaton) 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 5y agoThe 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.
- OscarCunningham 5y agoIt'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.
- cma 5y agoIs that only with the stabilizers shown in yellow, or do they have some other purpose?
- andrewthehacker 5y agoThe 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.
- contravariant 5y 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.
- kevincox 5y agoIf 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.
- 5y ago
- dskloet 5y agoWho is Danielle Conway? Google links me to some lawyer.
- deleted 5y ago[deleted]
- danielleconway 5y agoHi! 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".
- dskloet 5y agoCool. I was mostly curious if you're related to John?
- danielleconway 5y agoI am not
- charlieyu1 5y agoI have to say I don’t understand this, because a 2x2 square is already stable
- Diggsey 5y agoA 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 5y agoI 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 5y 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
- andrewthehacker 5y agoPlenty 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 5y ago[deleted]
- galaxyLogic 5y agoThat is like God
- fnord77 5y agowould like to see a live animation of this
- rnestler 5y agoMaybe 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 5y agoI 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/931582816137916416/931582811872309289.gif https://media.discordapp.net/attachments/370571014654001154/...
- ted_dunning 5y agoJust off-hand, this looks like a great way to build long-period oscillators.
- jacquesm 5y agoLots of people will miss the joke.
- prideout 5y agoTheir 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 5y agoCellular 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/
- prideout 5y agoThese 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 5y agoToffoli[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/links/fpu/fpu.pdf 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 https://en.wikipedia.org/wiki/Tommaso_Toffoli [1] https://people.csail.mit.edu/nhm/ https://people.csail.mit.edu/nhm/ https://en.wikipedia.org/wiki/Norman_Margolus https://en.wikipedia.org/wiki/Norman_Margolus [2] https://en.wikipedia.org/wiki/Edward_Fredkin https://en.wikipedia.org/wiki/Edward_Fredkin [3] https://scholar.google.com.au/scholar?as_vis=1&hl=en&q=gerard%20vichniac https://scholar.google.com.au/scholar?as_vis=1&hl=en&q=gerar... [4] https://scholar.google.com/citations?user=kujUxFYAAAAJ&hl=en https://scholar.google.com/citations?user=kujUxFYAAAAJ&hl=en [5] https://en.wikipedia.org/wiki/Rudy_Rucker https://en.wikipedia.org/wiki/Rudy_Rucker [6] https://en.wikipedia.org/wiki/Noether%27s_theorem https://en.wikipedia.org/wiki/Noether%27s_theorem [7] best video of SmoothLife https://www.youtube.com/watch?v=KJe9H6qS82I https://www.youtube.com/watch?v=KJe9H6qS82I https://sourceforge.net/projects/smoothlife/files/ 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 https://www.youtube.com/watch?v=iyTIXRhjXII Shadertoy version https://www.shadertoy.com/view/XtdSDn https://www.shadertoy.com/view/XtdSDn
- mg 5y agoHere 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?
- danielleconway 5y agoThe 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 5y agoRelated or coincidence?
- deleted 5y ago[deleted]
- cesaref 5y agoThis 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 5y agoOh! 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 5y ago
- xayfs 5y ago[flagged]
- peterburkimsher 5y agoFor 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#Examples_of_patterns https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life#Exampl...
- q1w2 5y agoMaybe 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 5y agoIs 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/ 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%20mathematics%2C%20a%20Mersenne%20prime,so%20is%202n%20%E2%88%92%201 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 https://en.wikipedia.org/wiki/Illegal_number#Illegal_primes
- andrewthehacker 5y agoNOTE: 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.
- deleted 5y ago[deleted]
- irthomasthomas 5y agoSo the most compact solution is a 2 x 2 surrounded 2s? Weird!
- perihelions 5y agoIs 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 5y agoSpacetime, energy, the laws? All the particles seem to come and go.
- rspencer 5y agoHas 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.
- dvgrn 5y agoI 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 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=140277#p140277
- dvgrn 5y agoThere was also some early discussion of the result by the authors on the ConwayLife Lounge on Discord: https://discord.com/channels/357922255553953794/370571014654001154/931615448653496330 https://discord.com/channels/357922255553953794/370571014654...