A Conway 'Game of Life' Conjecture Settled After 29 years (hatsya.com) 54
In 1992 John Conway raised a question about the patterns in his famous mathematical Game of Life: "Is there a Godlike still-life, one that can only have existed for all time (apart from things that don't interfere with it)?"
Conway closed his note by adding "Well, I'm going out to get a hot dog now..." And then, nearly 30 years later, a mathematical blog reports: Ilkka Törmä and Ville Salo, a pair of researchers at the University of Turku in Finland, have found a finite configuration in Conway's Game of Life such that, if it occurs within a universe at time T, it must have existed in that same position at time T-1 (and therefore, by induction, at time 0)...
The configuration was discovered by experimenting with finite patches of repeating 'agar' and using a SAT solver to check whether any of them possess this property.
The blogger also shares some other Game of Life-related news:
Conway closed his note by adding "Well, I'm going out to get a hot dog now..." And then, nearly 30 years later, a mathematical blog reports: Ilkka Törmä and Ville Salo, a pair of researchers at the University of Turku in Finland, have found a finite configuration in Conway's Game of Life such that, if it occurs within a universe at time T, it must have existed in that same position at time T-1 (and therefore, by induction, at time 0)...
The configuration was discovered by experimenting with finite patches of repeating 'agar' and using a SAT solver to check whether any of them possess this property.
The blogger also shares some other Game of Life-related news:
- David Raucci discovered the first oscillator of period 38. The remaining unsolved periods are 19, 34, and 41.
- Darren Li has connected Charity Engine to Catagolue, providing approximately 2000 CPU cores of continuous effort and searching slightly more than 10^12 random initial configurations per day.
- Nathaniel Johnston and Dave Greene have published a book on Conway's Game of Life, featuring both the theoretical aspects and engineering that's been accomplished in the half-century since its conception. Unfortunately it was released slightly too early to include the Törmä-Salo result or Raucci's period-38 oscillator.
Thanks to Slashdot reader joshuark for sharing the story.
Re: (Score:1)
Re: (Score:2)
You just posted this screed, again. That isn't "nothing".
I beg to differ.
Re: (Score:2)
Re: (Score:1)
your biggest problems are caused by massively centralized companies and social media
stop using them
Re: (Score:2)
His biggest problem is he just spams the same garbage over and over again.
Re: (Score:2, Funny)
So your complaint is that the online world doesn't work precisely the way that YOU think it should?
Well, pucker up, buttercup, because I've got an unpleasant insight for you. Once you turn off your computer and go outside, you'll find that the entire world is made up of systems that don't work precisely the way that you (or I) think they should.
And to bring it back to the topic at hand, That, my friend, is the fundamental rule of the (real) Game of Life.
Re: (Score:2)
No. His complaint is that he was dropped on his head as a baby and he hasn't been in the head right since then.
10^12 configurations per day (Score:2)
Its only 500 million per day per core? what the f...?
Re: (Score:2)
Re: (Score:3)
If I understand the problem correctly, it's a complex problem to solve. For each initial configuration they need to see what the configuration converges too. So you may need to run many time steps before that happens.
Contradiction? (Score:2)
There must be more to this than the summary states.
If the pattern is required to exist at time T-1 if it exists at T, then it must exist at time -1 (0-1), before the game starts. So either there is no such pattern or they must have some special casing required for 0.
I guess I'll have to read the paper!
Re:Contradiction? (Score:5, Informative)
There is no time -1. What the paper and the summary are saying is that that configuration can *only* occur if the world is directly set up to contain it. There's no way to set up the simulation with gliders and whatnot to eventually *produce* it.
Re: (Score:1)
Re:Contradiction? (Score:4, Informative)
Right. I just realised that a couple of minutes ago.
The real point is that there is no initial configuration that does not include the specific pattern which will cause it to appear.
[/brainfart]
Re: (Score:3)
There must be more to this than the summary states.
If the pattern is required to exist at time T-1 if it exists at T, then it must exist at time -1 (0-1), before the game starts. So either there is no such pattern or they must have some special casing required for 0.
I guess I'll have to read the paper!
Read the paper? I'm still trying to understand the question:
"Is there a Godlike still-life, one that can only have existed for all time (apart from things that don't interfere with it)?"
Re:Contradiction? (Score:4, Informative)
Read the paper? I'm still trying to understand the question:
You can setup the initial configuration anyway you wish, and as the world plays out, things are changed. Some structures are created, others destroyed, others yet become changed, and some change into structures that end up static and unchanging.
The question is: is there a static unchanging structure that can only exist by putting it there at the initial setup, and can never be created by the world playing out and making that structure come into existence.
Re: (Score:2)
So it's the same as the statement "are there structures that can never be created by others, no matter how clever?"
Re: (Score:1)
Well, and that are immutable in the sense that they stay there forever, I think is the important qualifier. It can neither be created nor destroyed while the game is running, and simply can only exist if it was put there before the game started. Basically what I'm gathering is they solved the equation so they know there's 3 of them and they did the math to actually calculate one of them.
Re: (Score:1)
Oh, no my bad, misread. There's 4 of them, of which they've calculated the starting positions of 1.
Re: (Score:1)
I understood this part:
"Well, I'm going out to get a hot dog now..."
Re: (Score:3)
I'm still trying to figure out what "going out" is supposed to mean.
Re: (Score:2)
It means going to the surface, and exiting the building.
Re: (Score:2)
No way! That's where the cold lives!
Sent from Canada.
Re: (Score:2)
"Can only have existed for all time" could be phrased much better, like "Cannot have descended from any other configuration".
Re: (Score:2)
The key is to understand what he meant by "still-life". Once you get that, the makes sense.
Re: (Score:2)
The standard term is "garden of Eden", so the summary is unhelpful even for people who are moderately familiar with the field. I only understood it because I've already seen a reference to the work elsewhere.
Re: (Score:2)
Re: (Score:3)
>I guess I'll have to read the paper!
???
You realize, of course, that that is about the *only* way to get banned from slashdot?
hawk
Re:Fixed point theorem? (Score:5, Informative)
You've missed some important points. Fixed points in GoL, or "still-lifes", have been known from the beginning, the simplest being a square block of four living cells.
Patterns without predecessors, known as "Garden of Eden" patterns, have also been known for many years.
The new pattern is a still-life Garden of Eden.
Fascinating (Score:3)
This is why I still read /. despite 25 years of semi-autistic bs in the comments. Mine included.
Re: Fascinating (Score:2, Offtopic)
Good Lord, has it really been that long?
Checks calendar⦠Yepâ¦
Get off my lawn, and stop dumping hot grits on Natalie Portman!
Re: (Score:3)
I would, but could you imagine a beowulf cluster of naked and petrified Natalie Portmans?
Yes, totally agree... (Score:1)
This is why I still read /. despite 25 years of semi-autistic bs in the comments.
This is a pretty cool thing to just find now, so many years later...
One little bit of sub-knowledge I did not know about life was in the article also:
Every strict still-life with â 20 cells can be synthesised by gliders.
A pretty cool little factlet I hadn't heard before.
Re: (Score:2)
Damn I've gotten old!
Worth pointing out that the book is free (Score:3, Informative)
Worth pointing out, don't expect the "editors" to bother doing it.
https://conwaylife.com/book/ [conwaylife.com]
Unanswered questions (Score:2)
Did he ever get the hot dog?
Did Conway like Life cereal?
Had he considered giving up and just playing the board game instead?
Re: (Score:2)
Had he considered giving up and just playing the board game instead?
He gave up on Global Thermonuclear War, that's for sure. That game has an unsatisfying resolution.
What? (Score:2)
Can anyone explain what this is about?
Re: (Score:2)
https://www.conwaylife.com/wik... [conwaylife.com]
Re: (Score:2)
You must not have had a computer back in the 70's or 80's :)
This was probably the first thing I really programmed in Assembly.
TFA Missed a Bit (Score:5, Funny)
They skipped the part where Stephen Wolfram then claimed that he knew that all along and just assumed the rest of us were as smart as he thinks he is. Oh, and that he invented "Conway's Game of Life" when he was 11 and has regretted calling that ever since.
I guess Conway would have been happy (Score:3)
He would have been happy to see this. Too bad he died of COVID in 2020. We will miss him. He was still active at past 80.
and now it needs you to send it (Score:1)
What's the conjecture? (Score:2)
The link in question presents a life pattern that seems to destruct instantly. Tested on LiveViewer [lazyslug.com] and copying that pattern (manually by the way) - I don't see how that pattern is a parent of itself, nor how it could be formed by anything, and thus I don't know what's being talked about.
Re: (Score:2)
nor how it could be formed by anything
That's the point.
Re: (Score:2)
That would be half the point, not the point. Even if it was the point, it doesn't mean much if there's an issue with the description or presentation.
Also, it's not even the point. If you read the rest of my comment, you'd notice that it's the unique father problem where it's formed by exactly one parent rather than being a garden of eden with no parent.
Pretty sweet deal - FREE (Score:2)
34 period oscillator stupid question (Score:2)
Re: (Score:2)
Source [conwaylife.com]
still-lifes (Score:2)
A still-life, from another poster, I don't know if there is a real name, like a square will eventually break up if something hits it.
Is there a position that make break up but will after a finite number of moves return to its first position again?
Throw a glider at it and it will warp to an apparently random design but go back to the start, as though the glider never hit.