7 ms·

Conway's Game of Life is omniperiodic

272 points by sohkamyung 3y ago

pohl 3y ago
Of all the natural numbers in N, how did it turn out that the last two were so small: 41 and 19? I’d have guessed that maybe some huge number would have been the most difficult.
- DemocracyFTW2 3y ago
  After years of watching numberphile on Youtube, my guess would be that there's a cutoff number n0 for which can be inductively shown that if n0 is a period then n0+1 is also a period; that would then eliminate almost all natural numbers from the search. Such a proof might perhaps use combining periodic patterns to obtain longer periods. It seems to be difficult to construct a periodic GoL pattern with a given period, so that then would explain why of all numbers two very small ones held out over the decades; this is truly astounding, especially given how incredibly inventive and industrious people have gotten with the Game of Life, simulating entire computers on the canvas.
  - AeiumNE 3y ago
    As a fellow numberphile viewer, I accept your authority on the topic, and will probably repeat this guess as fact later.
  - mhink 3y ago
    Actually, progress looks like it's been very steady. You're right regarding inductive-style proofs, but the ones for _all_ natural numbers greater than a certain value came surprisingly late. There appear to have been many more oscillators with periods of x + yn (for constant x and y, any natural number n). In 1996 there was a paper showing that it was possible to use a particular family of patterns called "Herschel loops" to create oscillators of any period >= 61. From there, the only missing oscillators were 17, 19, 22, 23, 27, 31, 33, 34, 37, 38, 39, and 41, 49, 51, 53, 57, and 59. There were gradual discoveries of new oscillators over the next several years, then in 2013 there was another pattern discovered which lowered that upper bound to >= 43. At this point, there were only five oscillators missing: 23, 34, 38, 19, and 41. There appear to have been a few years where progress stalled; 23 was found in 2019, and then the last four were found over the course of these past couple years.
- Grimblewald 3y ago
  would have been great if the last one was 42.
  - Dove 3y ago
    42 is special, though, as the longest cycle that requires a its own solution. 43+ can be made as a Snark Loop. https://conwaylife.com/wiki/P43_Snark_loop https://conwaylife.com/wiki/P43_Snark_loop
    - codeflo 3y ago
      That doesn't make any sense to me. A 6-cycle oscillator next to a 7-cycle oscillator should form a 42-cycle oscillator, or am I missing something?
      - LegionMammal978 3y ago
        This paper is primarily considering nontrivial oscillators, i.e., oscillators in which at least one cell oscillates at the full period, not just some divisor. Still, there are many nontrivial "LCM" oscillators that can be constructed with two lower-period oscillators that just slightly interact. Such an LCM oscillator for p42 ("unix on 44P7.2") could have been constructed for decades; the actual last nontrivial periods to be discovered were p34, p38, p19, and p41.
  - readyplayernull 3y ago
    Off by one
  - bee_rider 3y ago
    Or if 42 was the only impossible period.
  - passion__desire 3y ago
    If you care for 42 to be special, here's video that might be of interest to you. The Answer to the Ultimate Question of Life, the Universe and Everything : https://www.youtube.com/watch?v=ZFxT0sObrYQ https://www.youtube.com/watch?v=ZFxT0sObrYQ
- z2trillion 3y ago
  From page two of the paper: "Low-period oscillators in Life, roughly p ≤ 15, can be found by playing with patterns by hand or using brute force computer searches. In 1996, David Buckingham demonstrated [6] using his “Herschel conduits” that one can construct oscillators with p ≥ 61 by sending signals around a closed track; the cutoff for systematically constructing oscillators was later improved to p ≥ 43, by Mike Playle’s discovery of the Snark [43]."
  - davidgrenier 3y ago
    I was speculating two oscillators with periods p and q could be composed (as long as there was no way for them to interact) to create an oscillator of period p*q/gcd(p,q) but wondering why large primes wouldn't be a problem. I guess this is my answer.
- SAI_Peregrinus 3y ago
  You can build a Turing Machine in the GoL. Then program a loop. The period needed to execute the loop is rather long (TMs in life aren't very fast), but every period beyond that is trivially just a different TM program. Finding oscillators shorter than the shortest looping TM takes is harder.
  - klyrs 3y ago
    This would only get you multiples of your "clock rate."
  - kuhewa 3y ago
    You don't want a clunky TM, in GOL terms just a 'signal conduit' with a reasonably short delay on the reflectors so the periodicity can be reduced.
- GolDDranks 3y ago
  I don't think that's surprising, because surely there are a lot more possible ways to get larger periods than small periods? The amount of possible interactions / mechanisms in play is more limited with small periods. I think that groups of periods over some theshold numbers would also yield more readily to "constructive" approaches where you can "build up" the period using oscillators of a smaller period as components.
  - Someone 3y ago
    for example, search for constellations that send gliders back and forth through empty space. If you have one of period p, you can make one of period p + 8n for every n in Ν by moving the guns further away from each other. Find a few guns that take longer to ‘reload’ upon getting ‘hit’. Search on, and hopefully, you can find the 7 other modulos. And it need not be glider guns. It could also be constellations that send a ‘ripple’ through occupied space back and forth. I guess such ones can be made with smaller periods, but may require larger constants than 8 because you typically can’t move them further apart by a single cell. Edit: another comment mentions https://conwaylife.com/wiki/P43_Snark_loop https://conwaylife.com/wiki/P43_Snark_loop, a single construct that can be tweaked to have any period ≥ 43.
Dove 3y ago
Our family celebrated the event with a custom t-shirt:https://www.teepublic.com/t-shirt/49108604-life-is-omniperiodic?store_id=2810567 https://www.teepublic.com/t-shirt/49108604-life-is-omniperio...
- ksaj 3y ago
  I just bought one. I bet a lot of people reading this thread did.
- xpe 3y ago
  Backstory please.
  - Dove 3y ago
    My son (13) is extremely mathematically adept, and current research on cellular automata generally and Life specifically is one of his passions. When the final pattern was discovered earlier this year, he was extremely excited about it, and we all wanted to celebrate. So he put together on graph paper what he felt were the smallest/most iconic/best designs for each period, and I transferred those designs into a Teepublic appropriate digital format (using my obvious "Engineer Faking Things" designer skills. LOL.) We then went wild buying shirts for the family, a sticker (stuck currently on the water filter in the living room), a mug which was supposed to be mine but which my son guards as a precious possession, and a giant wall tapestry to hang in my son's room. I actually wasn't sure all of those were going to come out, but even on the sticker, you can make out the individual cells in the more complex designs. Anyway - we enjoy these things on a daily basis. We're kinda a bunch of math geeks. My husband and I both have masters degrees in the field, and our son, I guess, is a demonstration of what you can accomplish with selective breeding. ;) We have a lot of mathematical curiosities around the house, most of them homemade - penrose and hat tile fridge magnets, klein bottles, constant width solids, representations of projective tuning space. You know, the usual. Other enthusiasts in the (very niche) space enjoy seeing the graphic. Since the time of creation, math has advanced, with these no longer being the smallest or best examples of some of these loops. This is exciting for all of us - the advance of mathematics is usually not this accessible. :)
xpe 3y ago
Total aside. I just looked at https://conwaylife.com/wiki/Ocellus https://conwaylife.com/wiki/Ocellus -- there is one main glider. I noticed the two biggish curvy Golgi apparatus-looking-things on the sides and wondered if they play a necessary role in preserving the cyclical pattern. I guessed they might be important to prevent the three squares on each end from breaking down when the glider collides with them. I couldn't tell for sure as the animation was too fast. Well, turns out there is a very nice LifeViewer that allowed me to play with the sequence! By stepping the simulation I could see that the curvy structures play a role.
- cultureswitch 3y ago
  People be watching this and still argue "math is invented" smh
  - trenchgun 3y ago
    Math is an empirical science.
    - kuhewa 3y ago
      If it is a science, it can't have theorems. Empiricism is often involves in mathematical discoveries but the key difference is math isn't reliant on empiricism and at least in theory the current body of mathematical knowledge can reasoned entirely from simple axioms.
    - xpe 3y ago
      Why do you say this? What do you mean? You recognize that "empirical science" has a clear meaning to most scientists, right? This idea is quite different than formal reasoning (e.g. deduction over theorems).
  - nairboon 3y ago
    Some math is actually invented, like transfinite numbers. But feel free to empirically construct one of those...
  - 3y ago
eikenberry 3y ago
Can anyone speak to the significance of this?
- lotharbot 3y ago
  "Conway's Game Of Life" is a game of cells on a 2d grid that live/die/reproduce based on how many neighbors they have. As a result of the game rules, you can get simple behaviors like "everything dies" or "everything is stable". But you can also get more complex behaviors, like things growing for thousands of turns before eventually collapsing and then stabilizing into a few fragments here and there. And you can get behaviors that don't stabilize -- like shapes that evolve in a way that after a certain number of turns the whole shape has moved along the grid ("gliders" or "spaceships") or oscillators of various periods. Quite a while back there was a loop discovered that allowed for a period 43 oscillator, which could be adjusted by just moving things farther apart and therefore allowed every period of 43 or more. And oscillators of most smaller periods had been discovered -- but 19 and 41 were still unknown, up until both were discovered in rapid succession by 2 different people. So now we know how to make an oscillator for any given period within Conway's Game of Life.
  - omginternets 3y ago
    And why does that matter? What do we now know as a result? Or what interesting properties follow?
    - beacon294 3y ago
      It's quite interesting in its own context, otherwise, you may not be interested.
      - omginternets 3y ago
        Yes, yes. I need help appreciating it :)
deleted 3y ago
[deleted]
mbfg 3y ago
shame john wasn't here to see it.
- Syzygies 3y ago
  The last time I saw John, he was talking at a Mathematical Sciences Research Institute donor dinner. I was audience filler, after consulting on "A Beautiful Mind". He was describing games from his book with Berlekamp, and needed some fresh meat to play him in front of everyone. No one budged. The director gave me a certain look, and I volunteered. One of those "sticks on paper" games that never interested me, I was slaughtered. It all went very fast, some in the audience thought I had actually won a game counted against me. I got the biggest laugh when trying to outrun a certian loss, I enlarged the game board.
- tobinfricke 3y ago
  >> Life ultimately became way too popular for Dr. Conway’s liking. Whenever the subject came up, he would bellow, “I hate Life!” But in his final years he learned to love Life again. He narrated a documentary, with the working title “Thoughts on Life,” by the Brooklyn-based mathematician and filmmaker Will Cavendish, exploring the deterministic Game of Life versus the Free Will Theorem, a result Dr. Conway proved with his Princeton colleague Simon Kochen. “I used to go around saying, ‘I hate Life,’” Dr. Conway says in the film. “But then I was giving a lecture somewhere, and I was introduced as ‘John Conway, Creator of Life.’ And I thought, ‘Oh, that’s quite a nice way to be known.’ So I stopped saying ‘I hate Life’ after that.” << https://www.nytimes.com/2020/12/28/science/math-conway-game-of-life.html https://www.nytimes.com/2020/12/28/science/math-conway-game-...
tbm57 3y ago
I might be misunderstanding what they accomplished here - doesn't this mean that oscillators needed to be found for all prime number periods? for me, random coincidence that this popped up today, I just published a little holiday-themed GoL variant last week here: https://52games52weeks.com/gameofchristmas https://52games52weeks.com/gameofchristmas
- cultureswitch 3y ago
  I think that beyond a certain period you have so much logic at your disposal that you can construct two organisms sending messages to each other and vary the distance in increments of one to get any period you want.
  - lotharbot 3y ago
    You're basically correct, though it's usually done with 4 mechanisms making an adjustable glider loop, which can have any period of 43 or more just by increasing the spacing: https://conwaylife.com/wiki/P43_Snark_loop https://conwaylife.com/wiki/P43_Snark_loop
- Paul-Craft 3y ago
  Right. If you want to have an oscillator with period $pq$ where $p$ and $q$ are primes, then you can just use independent oscillators with period $p$ to one with period $q$. They'd already discovered a construction for $p \geq 61,$ and most of the values below that, so only 19 and 41 were left.
- abetusk 3y ago
  From the abstract: """ ... At the turn of the millennium, only twelve oscillator periods remained ... . The search has finally ended, with ... the final two periods, 19 and 41, ... """ Note that 19 and 41 are prime. I'm not familiar with this line of research in the GoL (nor most others) but I assume that it was proved all prime periods (above 41, say) have been known since the turn of the century, or thereabouts. I suspect what happened is that there were "easy" constructions for large periods that could be done. I would think that once you have the freedom of large periods, you can construct large gadgets and thus prove with "relative ease" that you can get any large prime number period. My bet is that smaller periods are harder because of the smallness restriction.
Paul-Craft 3y ago
I'm wondering why this is a surprise, given GoL has been known to be Turing complete for some time, and why one couldn't just bootstrap oscillators of all periods off of some kind of Turing machine construction. https://hackaday.com/2020/11/21/a-computer-in-the-game-of-life/ https://hackaday.com/2020/11/21/a-computer-in-the-game-of-li... Incidentally, the computer in the previous link reminds me a lot of something I've seen implemented in my favorite CA, Wireworld: https://en.wikipedia.org/wiki/Wireworld https://en.wikipedia.org/wiki/Wireworld
- armchairhacker 3y ago
  I believe Turing completeness means you can simulate all periods divisible by some number(s) n, but the individual steps in the Turing machine construction would take multiple real steps.
- GolDDranks 3y ago
  Note that each single "step" of the Turing Machine may take n steps of advancing the GoL cellular automaton itself. This means that only periods of n*i where i is an integer corresponding to the number of steps made by the TM, are guaranteed to exist. Worse even, I don't think that a proof of Turing completeness requires there to be any time bounds on the machine, so n might not even be a constant... If that's the case, then Turing completeness only proves that there exists an infinite number of periods of various lengths, but nothing about how comprehensively they "cover" all possible periods.
  - kuhewa 3y ago
    In other words, Turing completeness is enough to simulate GoL within GoL, but says nothing about the existence of the p41 oscillator
- mmis1000 3y ago
  Turning complete does not mean it can finish all operations in specific limited time/step. It only means it can finish the computable calculations "eventually".
cultureswitch 3y ago
I'm surprised it took this long. Intuitively, it should be possible to show that the smallest setup that has a period of 19 cannot be larger than some area related to 19, and therefore ought to be long but not intractable to enumerate. Maybe I'm off and it's really too big already.
- kuhewa 3y ago
  The p19 in the paper is 31x21, but let it be 19x19. That's 361 cells, so 4.7x10^108 'soups' to search. The paper details the evolution of search methods. Brute force-ish methods were responsible for discovery of some lower period oscillators.
dclowd9901 3y ago
Glad we figured that out. So how’s the search for unified field theory going?
- offices 3y ago
  Not so great, all our greatest thinkers are working on advertising.
mckn1ght 3y ago
To help me get a grasp on the meaning and significance of this finding, could anyone provide examples of things outside the domain of cellular automata that are omniperiodic?
- kuhewa 3y ago
  I'm not sure the concept is very meaningful outside of CA. There aren't really infinites in the real world, and most domains they'd be possible they are probably trivial. Perhaps outstanding combinatory or graph theory problems are analogous
  - mckn1ght 3y ago
    Thanks, that’s helpful to know!
taylorbuley 3y ago
for whomever needs to hear it, on linux, xscreensaver has a great variant on conway's game of life built in as an optional package
ultimoo 3y ago
> ...in the decades since the creation of Life. Beautifully put.
kuhewa 3y ago
I loved reading this. One bug -the pattern that p11 links to is missing two live cells on the bottom still life, thus doesn't oscillate. The image of it in the pdf appears to be he correct pattern though. https://conwaylife.com/?rle=10b2o$10b2o$5bo10bo$4bobo8bobo$3bobo10bobo$2bobo3b6o3bobo$3bo14bo2$5bo10bo$5bo10bo$2o3bo10bo3b2o$2o3bo10bo3b2o$5bo10bo$5bo10bo2$3bo14bo$2bobo3b6o3bobo$3bobo10bobo$4bobo8bobo$5bo10bo$10b2o$10b2!&name=Achim%27s%20p11 https://conwaylife.com/?rle=10b2o$10b2o$5bo10bo$4bobo8bobo$3...

272 points by sohkamyung 3y ago

pohl 3y ago

Of all the natural numbers in N, how did it turn out that the last two were so small: 41 and 19? I’d have guessed that maybe some huge number would have been the most difficult.

DemocracyFTW2 3y ago
After years of watching numberphile on Youtube, my guess would be that there's a cutoff number n0 for which can be inductively shown that if n0 is a period then n0+1 is also a period; that would then eliminate almost all natural numbers from the search. Such a proof might perhaps use combining periodic patterns to obtain longer periods. It seems to be difficult to construct a periodic GoL pattern with a given period, so that then would explain why of all numbers two very small ones held out over the decades; this is truly astounding, especially given how incredibly inventive and industrious people have gotten with the Game of Life, simulating entire computers on the canvas.
- AeiumNE 3y ago
  As a fellow numberphile viewer, I accept your authority on the topic, and will probably repeat this guess as fact later.
- mhink 3y ago
  Actually, progress looks like it's been very steady. You're right regarding inductive-style proofs, but the ones for _all_ natural numbers greater than a certain value came surprisingly late. There appear to have been many more oscillators with periods of x + yn (for constant x and y, any natural number n). In 1996 there was a paper showing that it was possible to use a particular family of patterns called "Herschel loops" to create oscillators of any period >= 61. From there, the only missing oscillators were 17, 19, 22, 23, 27, 31, 33, 34, 37, 38, 39, and 41, 49, 51, 53, 57, and 59. There were gradual discoveries of new oscillators over the next several years, then in 2013 there was another pattern discovered which lowered that upper bound to >= 43. At this point, there were only five oscillators missing: 23, 34, 38, 19, and 41. There appear to have been a few years where progress stalled; 23 was found in 2019, and then the last four were found over the course of these past couple years.
Grimblewald 3y ago
would have been great if the last one was 42.
- Dove 3y ago
  42 is special, though, as the longest cycle that requires a its own solution. 43+ can be made as a Snark Loop. https://conwaylife.com/wiki/P43_Snark_loop https://conwaylife.com/wiki/P43_Snark_loop
  - codeflo 3y ago
    That doesn't make any sense to me. A 6-cycle oscillator next to a 7-cycle oscillator should form a 42-cycle oscillator, or am I missing something?
    - LegionMammal978 3y ago
      This paper is primarily considering nontrivial oscillators, i.e., oscillators in which at least one cell oscillates at the full period, not just some divisor. Still, there are many nontrivial "LCM" oscillators that can be constructed with two lower-period oscillators that just slightly interact. Such an LCM oscillator for p42 ("unix on 44P7.2") could have been constructed for decades; the actual last nontrivial periods to be discovered were p34, p38, p19, and p41.
- readyplayernull 3y ago
  Off by one
- bee_rider 3y ago
  Or if 42 was the only impossible period.
- passion__desire 3y ago
  If you care for 42 to be special, here's video that might be of interest to you. The Answer to the Ultimate Question of Life, the Universe and Everything : https://www.youtube.com/watch?v=ZFxT0sObrYQ https://www.youtube.com/watch?v=ZFxT0sObrYQ
z2trillion 3y ago
From page two of the paper: "Low-period oscillators in Life, roughly p ≤ 15, can be found by playing with patterns by hand or using brute force computer searches. In 1996, David Buckingham demonstrated [6] using his “Herschel conduits” that one can construct oscillators with p ≥ 61 by sending signals around a closed track; the cutoff for systematically constructing oscillators was later improved to p ≥ 43, by Mike Playle’s discovery of the Snark [43]."
- davidgrenier 3y ago
  I was speculating two oscillators with periods p and q could be composed (as long as there was no way for them to interact) to create an oscillator of period p*q/gcd(p,q) but wondering why large primes wouldn't be a problem. I guess this is my answer.
SAI_Peregrinus 3y ago
You can build a Turing Machine in the GoL. Then program a loop. The period needed to execute the loop is rather long (TMs in life aren't very fast), but every period beyond that is trivially just a different TM program. Finding oscillators shorter than the shortest looping TM takes is harder.
- klyrs 3y ago
  This would only get you multiples of your "clock rate."
- kuhewa 3y ago
  You don't want a clunky TM, in GOL terms just a 'signal conduit' with a reasonably short delay on the reflectors so the periodicity can be reduced.
GolDDranks 3y ago
I don't think that's surprising, because surely there are a lot more possible ways to get larger periods than small periods? The amount of possible interactions / mechanisms in play is more limited with small periods. I think that groups of periods over some theshold numbers would also yield more readily to "constructive" approaches where you can "build up" the period using oscillators of a smaller period as components.
- Someone 3y ago
  for example, search for constellations that send gliders back and forth through empty space. If you have one of period p, you can make one of period p + 8n for every n in Ν by moving the guns further away from each other. Find a few guns that take longer to ‘reload’ upon getting ‘hit’. Search on, and hopefully, you can find the 7 other modulos. And it need not be glider guns. It could also be constellations that send a ‘ripple’ through occupied space back and forth. I guess such ones can be made with smaller periods, but may require larger constants than 8 because you typically can’t move them further apart by a single cell. Edit: another comment mentions https://conwaylife.com/wiki/P43_Snark_loop https://conwaylife.com/wiki/P43_Snark_loop, a single construct that can be tweaked to have any period ≥ 43.

Dove 3y ago

Our family celebrated the event with a custom t-shirt:https://www.teepublic.com/t-shirt/49108604-life-is-omniperiodic?store_id=2810567 https://www.teepublic.com/t-shirt/49108604-life-is-omniperio...

ksaj 3y ago
I just bought one. I bet a lot of people reading this thread did.
xpe 3y ago
Backstory please.
- Dove 3y ago
  My son (13) is extremely mathematically adept, and current research on cellular automata generally and Life specifically is one of his passions. When the final pattern was discovered earlier this year, he was extremely excited about it, and we all wanted to celebrate. So he put together on graph paper what he felt were the smallest/most iconic/best designs for each period, and I transferred those designs into a Teepublic appropriate digital format (using my obvious "Engineer Faking Things" designer skills. LOL.) We then went wild buying shirts for the family, a sticker (stuck currently on the water filter in the living room), a mug which was supposed to be mine but which my son guards as a precious possession, and a giant wall tapestry to hang in my son's room. I actually wasn't sure all of those were going to come out, but even on the sticker, you can make out the individual cells in the more complex designs. Anyway - we enjoy these things on a daily basis. We're kinda a bunch of math geeks. My husband and I both have masters degrees in the field, and our son, I guess, is a demonstration of what you can accomplish with selective breeding. ;) We have a lot of mathematical curiosities around the house, most of them homemade - penrose and hat tile fridge magnets, klein bottles, constant width solids, representations of projective tuning space. You know, the usual. Other enthusiasts in the (very niche) space enjoy seeing the graphic. Since the time of creation, math has advanced, with these no longer being the smallest or best examples of some of these loops. This is exciting for all of us - the advance of mathematics is usually not this accessible. :)

xpe 3y ago

Total aside. I just looked at https://conwaylife.com/wiki/Ocellus https://conwaylife.com/wiki/Ocellus -- there is one main glider. I noticed the two biggish curvy Golgi apparatus-looking-things on the sides and wondered if they play a necessary role in preserving the cyclical pattern. I guessed they might be important to prevent the three squares on each end from breaking down when the glider collides with them. I couldn't tell for sure as the animation was too fast. Well, turns out there is a very nice LifeViewer that allowed me to play with the sequence! By stepping the simulation I could see that the curvy structures play a role.

cultureswitch 3y ago
People be watching this and still argue "math is invented" smh
- trenchgun 3y ago
  Math is an empirical science.
  - kuhewa 3y ago
    If it is a science, it can't have theorems. Empiricism is often involves in mathematical discoveries but the key difference is math isn't reliant on empiricism and at least in theory the current body of mathematical knowledge can reasoned entirely from simple axioms.
  - xpe 3y ago
    Why do you say this? What do you mean? You recognize that "empirical science" has a clear meaning to most scientists, right? This idea is quite different than formal reasoning (e.g. deduction over theorems).
- nairboon 3y ago
  Some math is actually invented, like transfinite numbers. But feel free to empirically construct one of those...
- 3y ago

eikenberry 3y ago

Can anyone speak to the significance of this?

lotharbot 3y ago
"Conway's Game Of Life" is a game of cells on a 2d grid that live/die/reproduce based on how many neighbors they have. As a result of the game rules, you can get simple behaviors like "everything dies" or "everything is stable". But you can also get more complex behaviors, like things growing for thousands of turns before eventually collapsing and then stabilizing into a few fragments here and there. And you can get behaviors that don't stabilize -- like shapes that evolve in a way that after a certain number of turns the whole shape has moved along the grid ("gliders" or "spaceships") or oscillators of various periods. Quite a while back there was a loop discovered that allowed for a period 43 oscillator, which could be adjusted by just moving things farther apart and therefore allowed every period of 43 or more. And oscillators of most smaller periods had been discovered -- but 19 and 41 were still unknown, up until both were discovered in rapid succession by 2 different people. So now we know how to make an oscillator for any given period within Conway's Game of Life.
- omginternets 3y ago
  And why does that matter? What do we now know as a result? Or what interesting properties follow?
  - beacon294 3y ago
    It's quite interesting in its own context, otherwise, you may not be interested.
    - omginternets 3y ago
      Yes, yes. I need help appreciating it :)

deleted 3y ago

[deleted]

mbfg 3y ago

shame john wasn't here to see it.

Syzygies 3y ago
The last time I saw John, he was talking at a Mathematical Sciences Research Institute donor dinner. I was audience filler, after consulting on "A Beautiful Mind". He was describing games from his book with Berlekamp, and needed some fresh meat to play him in front of everyone. No one budged. The director gave me a certain look, and I volunteered. One of those "sticks on paper" games that never interested me, I was slaughtered. It all went very fast, some in the audience thought I had actually won a game counted against me. I got the biggest laugh when trying to outrun a certian loss, I enlarged the game board.
tobinfricke 3y ago
>> Life ultimately became way too popular for Dr. Conway’s liking. Whenever the subject came up, he would bellow, “I hate Life!” But in his final years he learned to love Life again. He narrated a documentary, with the working title “Thoughts on Life,” by the Brooklyn-based mathematician and filmmaker Will Cavendish, exploring the deterministic Game of Life versus the Free Will Theorem, a result Dr. Conway proved with his Princeton colleague Simon Kochen. “I used to go around saying, ‘I hate Life,’” Dr. Conway says in the film. “But then I was giving a lecture somewhere, and I was introduced as ‘John Conway, Creator of Life.’ And I thought, ‘Oh, that’s quite a nice way to be known.’ So I stopped saying ‘I hate Life’ after that.” << https://www.nytimes.com/2020/12/28/science/math-conway-game-of-life.html https://www.nytimes.com/2020/12/28/science/math-conway-game-...

tbm57 3y ago

I might be misunderstanding what they accomplished here - doesn't this mean that oscillators needed to be found for all prime number periods? for me, random coincidence that this popped up today, I just published a little holiday-themed GoL variant last week here: https://52games52weeks.com/gameofchristmas https://52games52weeks.com/gameofchristmas

cultureswitch 3y ago
I think that beyond a certain period you have so much logic at your disposal that you can construct two organisms sending messages to each other and vary the distance in increments of one to get any period you want.
- lotharbot 3y ago
  You're basically correct, though it's usually done with 4 mechanisms making an adjustable glider loop, which can have any period of 43 or more just by increasing the spacing: https://conwaylife.com/wiki/P43_Snark_loop https://conwaylife.com/wiki/P43_Snark_loop
Paul-Craft 3y ago
Right. If you want to have an oscillator with period $pq$ where $p$ and $q$ are primes, then you can just use independent oscillators with period $p$ to one with period $q$. They'd already discovered a construction for $p \geq 61,$ and most of the values below that, so only 19 and 41 were left.
abetusk 3y ago
From the abstract: """ ... At the turn of the millennium, only twelve oscillator periods remained ... . The search has finally ended, with ... the final two periods, 19 and 41, ... """ Note that 19 and 41 are prime. I'm not familiar with this line of research in the GoL (nor most others) but I assume that it was proved all prime periods (above 41, say) have been known since the turn of the century, or thereabouts. I suspect what happened is that there were "easy" constructions for large periods that could be done. I would think that once you have the freedom of large periods, you can construct large gadgets and thus prove with "relative ease" that you can get any large prime number period. My bet is that smaller periods are harder because of the smallness restriction.

Paul-Craft 3y ago

I'm wondering why this is a surprise, given GoL has been known to be Turing complete for some time, and why one couldn't just bootstrap oscillators of all periods off of some kind of Turing machine construction. https://hackaday.com/2020/11/21/a-computer-in-the-game-of-life/ https://hackaday.com/2020/11/21/a-computer-in-the-game-of-li... Incidentally, the computer in the previous link reminds me a lot of something I've seen implemented in my favorite CA, Wireworld: https://en.wikipedia.org/wiki/Wireworld https://en.wikipedia.org/wiki/Wireworld

armchairhacker 3y ago
I believe Turing completeness means you can simulate all periods divisible by some number(s) n, but the individual steps in the Turing machine construction would take multiple real steps.
GolDDranks 3y ago
Note that each single "step" of the Turing Machine may take n steps of advancing the GoL cellular automaton itself. This means that only periods of n*i where i is an integer corresponding to the number of steps made by the TM, are guaranteed to exist. Worse even, I don't think that a proof of Turing completeness requires there to be any time bounds on the machine, so n might not even be a constant... If that's the case, then Turing completeness only proves that there exists an infinite number of periods of various lengths, but nothing about how comprehensively they "cover" all possible periods.
- kuhewa 3y ago
  In other words, Turing completeness is enough to simulate GoL within GoL, but says nothing about the existence of the p41 oscillator
mmis1000 3y ago
Turning complete does not mean it can finish all operations in specific limited time/step. It only means it can finish the computable calculations "eventually".

cultureswitch 3y ago

I'm surprised it took this long. Intuitively, it should be possible to show that the smallest setup that has a period of 19 cannot be larger than some area related to 19, and therefore ought to be long but not intractable to enumerate. Maybe I'm off and it's really too big already.

kuhewa 3y ago
The p19 in the paper is 31x21, but let it be 19x19. That's 361 cells, so 4.7x10^108 'soups' to search. The paper details the evolution of search methods. Brute force-ish methods were responsible for discovery of some lower period oscillators.

dclowd9901 3y ago

Glad we figured that out. So how’s the search for unified field theory going?

offices 3y ago
Not so great, all our greatest thinkers are working on advertising.

mckn1ght 3y ago

To help me get a grasp on the meaning and significance of this finding, could anyone provide examples of things outside the domain of cellular automata that are omniperiodic?

kuhewa 3y ago
I'm not sure the concept is very meaningful outside of CA. There aren't really infinites in the real world, and most domains they'd be possible they are probably trivial. Perhaps outstanding combinatory or graph theory problems are analogous
- mckn1ght 3y ago
  Thanks, that’s helpful to know!

taylorbuley 3y ago

for whomever needs to hear it, on linux, xscreensaver has a great variant on conway's game of life built in as an optional package

ultimoo 3y ago

> ...in the decades since the creation of Life. Beautifully put.

kuhewa 3y ago

I loved reading this. One bug -the pattern that p11 links to is missing two live cells on the bottom still life, thus doesn't oscillate. The image of it in the pdf appears to be he correct pattern though. https://conwaylife.com/?rle=10b2o$10b2o$5bo10bo$4bobo8bobo$3bobo10bobo$2bobo3b6o3bobo$3bo14bo2$5bo10bo$5bo10bo$2o3bo10bo3b2o$2o3bo10bo3b2o$5bo10bo$5bo10bo2$3bo14bo$2bobo3b6o3bobo$3bobo10bobo$4bobo8bobo$5bo10bo$10b2o$10b2!&name=Achim%27s%20p11 https://conwaylife.com/?rle=10b2o$10b2o$5bo10bo$4bobo8bobo$3...