The level of engineering necessary to do this in 1 dimension is still beyond me, as is the "simple" explanation posted on the Conway forums. But I feel like I appreciate the achievement a little bit more now.
Me: oh cool, this is interesting, I don’t quite understand what exactly that means, let me read the thread to learn more…
The thread:
> Replacing ECCA1 by version with step after the direction change could save something like 1% of the ecca1 bits size. Compiling agnosticized program instead of fixed lane program by ecca1 could save something like 1% as well (just guesses). Build of smaller ECCA1 would shorten binary portion, but it would be hardly seen in the ship size.
> Using agnosticized recipe in the fuse portion would definitely reduce its size. Better cordership seed and better salvo for gpse90 would help…
Dear lord I had no idea there’s this much jargon in the game of life community. Gonna be reading the wiki for hours
Reading a long explanation on a GoL forum is a great way to experience what it’s like for my spouse to listen to my work conversations on Zoom. This jargon is fantastic.
Sometimes I feel a deep sense of loss of the old web that grew up with -full of niche interests, unashamedly earnest and rich in subcultures- has been lost in a sea of corporate slop and clickbait social media.
Then occasionally I come across something like this and it feels like all is not lost. Conway's GoL was one of the first C programmes I ever wrote and I've long been distantly fascinated by cellular automata but I had no idea that there was such a depth of research (work, experimentation, collaboration? how do you even describe this kind of collective endeavour?) into GoL lurking out there all these years.
“Easily verifiable”… Not really, you have to simulate 133_076_755_768 steps. Sure it’s doable. But if the AI suggests a thousands patterns, then it will be useless.
Two of the most fascinating open questions about the Game of Life are in my opinion:
1. What is the behavior of Conway's Game of Life when the initial position is random? Paraphrasing Boris Bukh's comment on the post linked below, the Game of Life supports self-replication and is Turing-complete, and therefore can support arbitrarily intelligent programs. So, will a random initial position (tend to) be filled with super-intelligent life forms, or will the chaos reign?
There exist uncountably infinitely many particular initial configurations out of which a random one may be drawn, which makes this more difficult (a particular infinite grid configuration can be represented as the binary digits (fractional part) of a real number, spiraling outwards from a given center coordinate cell: 0.0000... represents an empty infinite grid, 0.1111... a fully alive infinite grid).
2. Relatedly, does a superstable configuration exist? One that continues to exist despite any possible external interference pattern on its border? Perhaps even an expanding one?
‘Random’ configurations are going to be dominated by fixed scale noise of a general 50% density, which is going to have very common global evolutionary patterns - it’s almost homogenous so there’s little opportunity for interesting things to occur. You need to start with more scale free noise patterns, so there are more opportunities for global structures to emerge.
in an infinite plane, if we keep adding random points ( similar to sun continuously giving earth low entropy energy ) , eventually, it will reach to intelligent life form, which are very efficient at converting low entropy energy to high entropy energy.
The thing that blows my mind is: say you start filling the plane with pi. Pi has been proven to contain every finite sequence. That means that somewhere in the plane is a full physics simulation of YOU in the room you are in right now.
Does that you exist any less fully because its not currently in the memory of a computer being evaluated?
An interesting thing related to these questions in the context of physics: there was an interesting discussion on Scott Aaronson's blog a few years ago about why the universe should be quantum mechanical. One idea that was brought up is quite related to the open questions you name here.
Here's an excerpt from a comment of Daniel Harlow (a prof at MIT):
> In order for us to be having this discussion at all, the laws of physics need to have the ability to generate interesting complex structures in a reasonable amount of time starting from a simple initial state. Now I know that as a computer scientist you are trained to think that is a trivial problem because of Turing completeness, universality, blah blah blah, but really I don’t think it is so simple. Why should the laws of physics allow a Turing machine to be built? And even if a Turing machine is possible, why should one exist? I think the CS intuition that “most things are universal” comes with baked-in assumptions about the stability of matter and the existence of low-entropy objects, and I think it is not so easy to achieve these with arbitrary laws of physics.
Scott replies:
> Multiple people made the case to me that it’s far from obvious how well
(1) stable matter,
(2) complex chemistry,
(3) Lorentzian and other continuous symmetries,
(4) robustness against small perturbations,
(5) complex structures
being not just possible but likely from “generic” initial data,…can actually be achieved in simple Turing-universal classical cellular automaton models.
How in the world do people even discover these things? Certainly not by clicking cells to set up an initial population then hit "Go". Brute force approach works I suppose.
In 1995, I received an email from someone named Conway asking me for more details about some silly thing I wrote in sci.math usenet group. Later I came to know more abut him as John Conway. Sadly I lost access to those emails.
Now, I'm unaware of this strange GoL world with amazing work people are doing. Sometimes I wonder which frontiers of progress, should we as human race be utilizing this amazing creative potential of the current generations.
makes me wonder if its possible to get natural numbers like pi/e using a geometric structure in GoL. it would be interesting to derive them from an emerging order based on fixed set of automata rules. If possible it might lead credence to simulated universe hypothesis.
Sure! Here you go. Open paint. Set the canvas to FHD resolution. Draw a one pixel thick, gray (#777777) line from one side to the other. You now have a perfect render, with antialiasing.
Can someone who knows a bit more about this help me understand how structures like this are produced? Is there some kind of computer search, perhaps guided? Is this a clever combination of sub-structures, timing mechanisms, etc. that are then fit together like Legos?
Right. Interesting small patterns can be found using clever search algorithms. There's also the approach of running trillions of random 'soups' and scanning the results for interesting patterns. These small patterns are then pieced together to build the larger structures.
I believe this one is a deliberate construction, they knew the evolution of the pieces and gradually put it together.
There’s search programs too, for smaller patterns. This construction is just too big and with such a long period. The search space would be enormous.
I got involved in this stuff years ago when I modified a search program for Life to search any CA rule. That’s how we found the HighLife rule and others like Day and Night.
Basically, for this specific structure, they had to develop their own "sub structures" on the 1d line. These sub structures are known to create one little thing going diagonally (and then leave a bunch of debris behind, but that doesn't matter too much for that first step, they called this custom part "the fuse"). Then, there is a known technique where taking "diagonal moving objects" created on the same y-coordinate and placing them at the "right x position" makes the collide in a way where you can "program" where to create diagonal moving objects but at arbitrary positions on the screen (this is called a "binary construction arm"). And then, once you can create these anywhere on the screen, then you've basically won ; there's another technique to turn arbitrary positions into arbitrary shapes ("extreme compression construction arm", or ECCA), and it's "just" a matter of making the ECCA clean up all of the debris and build a new fuse but moved over.
Of course, the "just" here does the heavy lifting and represents over two years of exploration, writing algorithms for how to clean up everything, and so on.
54 comments
[ 5.1 ms ] story [ 98.5 ms ] thread> Seems there is a bug in the forum, when more people write a post at the same time the post sometimes vanishes.
That's kind of amazing. I wish someone unpacked the units of abstraction/compilation that must surely exist here.
Surely they aren't developing this with 1 or 0 as the abstraction level!
The level of engineering necessary to do this in 1 dimension is still beyond me, as is the "simple" explanation posted on the Conway forums. But I feel like I appreciate the achievement a little bit more now.
Looking forward to the impending AI and crypto crash and have people run GoL simulations on expensive computer systems like it's 1972 again.
The thread: > Replacing ECCA1 by version with step after the direction change could save something like 1% of the ecca1 bits size. Compiling agnosticized program instead of fixed lane program by ecca1 could save something like 1% as well (just guesses). Build of smaller ECCA1 would shorten binary portion, but it would be hardly seen in the ship size.
> Using agnosticized recipe in the fuse portion would definitely reduce its size. Better cordership seed and better salvo for gpse90 would help…
Dear lord I had no idea there’s this much jargon in the game of life community. Gonna be reading the wiki for hours
Then occasionally I come across something like this and it feels like all is not lost. Conway's GoL was one of the first C programmes I ever wrote and I've long been distantly fascinated by cellular automata but I had no idea that there was such a depth of research (work, experimentation, collaboration? how do you even describe this kind of collective endeavour?) into GoL lurking out there all these years.
The result is easily verify-able, yet the techniques to design such a glider are very complex and some might not have been discovered yet.
glider is a specific spaceship, but name for "moving pattern" is spaceship
1. What is the behavior of Conway's Game of Life when the initial position is random? Paraphrasing Boris Bukh's comment on the post linked below, the Game of Life supports self-replication and is Turing-complete, and therefore can support arbitrarily intelligent programs. So, will a random initial position (tend to) be filled with super-intelligent life forms, or will the chaos reign?
There exist uncountably infinitely many particular initial configurations out of which a random one may be drawn, which makes this more difficult (a particular infinite grid configuration can be represented as the binary digits (fractional part) of a real number, spiraling outwards from a given center coordinate cell: 0.0000... represents an empty infinite grid, 0.1111... a fully alive infinite grid).
https://mathoverflow.net/questions/132402/conways-game-of-li...
2. Relatedly, does a superstable configuration exist? One that continues to exist despite any possible external interference pattern on its border? Perhaps even an expanding one?
https://mathoverflow.net/questions/132687/is-there-any-super...
Does that you exist any less fully because its not currently in the memory of a computer being evaluated?
Here's an excerpt from a comment of Daniel Harlow (a prof at MIT):
> In order for us to be having this discussion at all, the laws of physics need to have the ability to generate interesting complex structures in a reasonable amount of time starting from a simple initial state. Now I know that as a computer scientist you are trained to think that is a trivial problem because of Turing completeness, universality, blah blah blah, but really I don’t think it is so simple. Why should the laws of physics allow a Turing machine to be built? And even if a Turing machine is possible, why should one exist? I think the CS intuition that “most things are universal” comes with baked-in assumptions about the stability of matter and the existence of low-entropy objects, and I think it is not so easy to achieve these with arbitrary laws of physics.
Scott replies:
> Multiple people made the case to me that it’s far from obvious how well
(1) stable matter,
(2) complex chemistry,
(3) Lorentzian and other continuous symmetries,
(4) robustness against small perturbations,
(5) complex structures
being not just possible but likely from “generic” initial data,…can actually be achieved in simple Turing-universal classical cellular automaton models.
See comments 225 and 261
https://scottaaronson.blog/?p=6244
Now, I'm unaware of this strange GoL world with amazing work people are doing. Sometimes I wonder which frontiers of progress, should we as human race be utilizing this amazing creative potential of the current generations.
There’s search programs too, for smaller patterns. This construction is just too big and with such a long period. The search space would be enormous.
I got involved in this stuff years ago when I modified a search program for Life to search any CA rule. That’s how we found the HighLife rule and others like Day and Night.
Of course, the "just" here does the heavy lifting and represents over two years of exploration, writing algorithms for how to clean up everything, and so on.