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
Once a year or so I find myself on those forums and I'm always astounded how many people there are that dedicate massive amounts of time and brain power to this.
That's because it's not "game of life jargon", it's "cellular automata" jargon. Which is a field of math and comes along with a bunch of math jargon from related fields.
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.
One exception: You are actually enthused about the topic you don't understand.
Your SO is likely only enthused to the degree that it affects your mood. "So this RISC architecture isn't compliant with ADA-1056 after all? And you were right all along? Wow, that's great, honey!"
Philosophically and depending on what schools of thought you follow, reality is just a really complex GoL simulation. I'm sure I read about it once, but if we were living in a simulation, would we be able to know?
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?
Your first question is discussed in the book The Recursive Universe by William Poundstone (1984).
One of the chapters asks "what is life?". It considers (and rejects) various options, and finally settles upon a definition based on Von Neumann-style self-replicating machines using blueprints and universal constructors, and explains why this is the most (only?) meaningful definition of life.
Later, it talks about how one would go about creating such a machine in Conway's Game of Life. When the book was written in 1984, no one had actually created one (they need to be very large, and computers weren't really powerful enough then). But in 2010 Andrew J. Wade created Gemini, the first successful self-replicating machine in GoL, which I believe meets the criteria - and hence is "alive" according to that definition (but only in the sense that, say, a simple bacteria is alive). And I think it works somewhat like how it was sketched out in the book.
Another chapter estimated how big (and how densely populated) a randomly-initialized hypothetical GoL universe would need to be in order for "life" (as defined earlier) to appear by chance. I don't recall the details - but the answer was mind-boggling big, and also very sparsely populated.
All that only gives you life though, not intelligence. But life (by this definition) has the potential to evolve through a process of natural selection to achieve higher levels of complexity and eventually intelligence, at least in theory.
One problem is that, even though it is turing-complete, many practical operations are very difficult. Patterns tend towards chaos and they tend towards fading out, which are not good properties for useful computation. Simply moving information from one part of the grid to another requires complex structures like spaceships.
You might have better luck with other variants. Reversible cellular automata have a sort of 'conservation of mass' where cells act more like particles. Continuous cellular automata (like Lenia) have less chaotic behavior. Neural cellular automata can be trained with gradient descent.
‘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.
> the Game of Life supports self-replication and is Turing-complete, and therefore can support arbitrarily intelligent programs.
I think people will disagree about whether “Turing-complete” is powerful enough for supporting intelligence but let’s assume it does.
> So, will a random initial position (tend to) be filled with super-intelligent life forms, or will the chaos reign?
Even if it doesn’t, it might take only one intelligent life form for the space to (eventually) get filled with it (the game of life doesn’t heave energy constraints that make it hard to travel over long distances, so I don’t see a reason why it wouldn’t. On the other hand, maybe my assumption that all intelligent life would want to expand is wrong), and in an infinite plane, it’s likely (¿certain?) one will exist.
On the other hand it’s likely more than one exists, and they might be able to exterminate each other.
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.
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?
This is a linear sequence of bits, which when interpreted as a Game of Life board, "prints" an exact copy of itself 2 pixels to the right (leaving no trace of the original).
I suppose its job would be easier if it only had to construct a copy of itself rather than "moving" itself, but I enjoy the interpretation that it's a linear "tape" of bits which prints its own code transposed by 2 pixels, and takes an unfathomable amount of time and space to do so. Beautiful.
yeah, spaceships are pretty common (fun fact: 2 spaceships were found on the same day including this one in GOL), also in CA it's called a "spaceship". However until now there was no 1D one (1D is also called 1-cell-thick or linear).
Also, you are actually wrong, it is actually much easier to move than to self-synthesize and then remain alive like a replicator. There has been no true replicator found yet in Life as far as I know (arguably, linear propagator may be a replicator) but like millions of spaceships have been found.
Tangential, but to people who find this topic interesting I highly recommend the book What is Intelligence [0] by Blaise Agüera y Arcas that views life through the lens of mutating self replicating Turing machines.
In the book he also talks about GoF, but one of the fascinating experiments he did is that a "computronium" of initially random Brainfuck programs (that obviously don't do anything interesting in the beginning) that mutate (by flipping random bits) and merge (by taking two random programs and sticking them together) eventually, after a sudden phase transition, start to self replicate by producing gradually better copies of themselves!
He also argues that symbiogenesis (merging replicators into a whole that does more than its parts) is the main driving force of evolution instead of just random mutations, because the random Brainfuck computronium eventually produces replicators even without the random bit flips.
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.
My understanding (which could be wildly wrong, I only skimmed the thread) is that it's running in a standard 2-dimensional Game of Life grid, it just happens to start out as a 1x3.7B cell line.
Someone figured out how to create a glider that starts and ends as a long string of cells on a single line. Gliders are figures in the game of life that move themselves in a direction by repeated patterns that result in movement. For more game of life/glider context you can read the pretty decent Wikipedia articles:
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.
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?
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.
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.
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.
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.
That shares the impressive inefficiencies of the Quest for Tetris project, though. For something that's much more practical to run, and can be programmed to do things like print out the digits of pi in-universe, see
It's already being done. Has been done for decades now. Definitely wouldn't be a good use of an LLM-type model if that's what you're proposing
If you look at the placement of Journal of Cellular Automata in SciMago's Shape of Science visualization[0] you'll see that it's completely surrounded by machine learning/AI journals
The Game of Life is Turing complete. And therefore a complete analysis of how to write programs in it would imply a solution to the Halting problem. Which is impossible.
“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.
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.
2) there are algorithms that calculate digits of Pi or e.
so... yes?
but if I just took any old Pi-digits algorithm and encoded it on GoL, its appearance would not be meaningful or "elegant" to our senses. You're probably asking "what does the shortest/most elegant program to calculate Pi in GoL look like, and does it maybe have some unexpected relation to other mathematical terms like, I dunno, Euler's identity or... Mandelbrot set?" And then you would probably need to answer the question "Well, how would you like the digits encoded and represented?".
All of a sudden your question becomes a bit ambiguous. Or did I misunderstand what you meant?
I mean.... I think I feel what you're asking, like... is there some primal version of Pi that can be encoded in GoL initial condition with as few bits as possible but I'm afraid that the answer is something like "well, that depends on what you mean by [...]"
Life is isotropic, so it remains symmetric vertically. It travels horizontally but I don't know which direction because it's so unfathomably large you would need a supercomputer to run at least a cycle of it.
Unidimensional spaceship can be interpreted as a demonstration of the progress of recent years in slow salvo technology and the various arms that use it.
The project uses 4 construction arms, with the last three sharing principles with the arms used in the RCT15 project. The first arm is newly invented just for this case. I was not part of the community at the time the principles of the first two arms were studied, but let me describe them anyway.
The one line restriction limit us to using blinkers as the basis of the first arm. Interestingly, a small perturbation at the end of some blinker configuration makes the pattern unstable, and several blinker patterns allow the perturbation "fuse" to move in a controlled manner. Various configurations have been discovered that leave no debris but move at different speeds. Some configurations have been found that produce backward-firing mwss (and leave debris), head-on collisions of mwss that transform them into gliders for both glider colors. By combining these configurations, we can trigger a fusion in the middle of a carefully chosen arrangement of blinkers that would synchronize the mwss collisions at the desired time parity at a prescribed x-coordinate and generate a glider with a prescribed phase and trajectory, so that such an arm could create any p2 recipe.
The second arm used is a binary arm, where a pair of synchronized gliders on the same trajectories are used, with one glider always present and the presence of the other gliders allowing modification of the resulting configuration. Careful study of the results of various words using letters "1" and "2" (indicating the presence of the second glider) led to the discovery of specific modifications of the target "anchor" configuration.
Some of them allow you to move the "head" of the anchor stack to move closer/farther from the base of the arm. Some sequences will generate a perpendicular glider. Not all mod 8 phases and colors are known, but with careful "head positioning" any p8 recipe could be built with such an arm. The program used for the translation only used single blinker anchor technology, which produces a glider for a cost of around 100 bits ("letters").
The agnosticisation salvas of the p8 recipe to use only the p1/p2 constraints on the glider phases (when possible) greatly reduces the number of bits required. Alternative glider paths also help, leading to the same stable configurations during a slow salvas. Currently, there is an alternative method with around 80 bits per glider using 4 different anchors deep in the "arm target stack".
The code could be improved by some form of dynamic programming by compiling the salvo from the parts emitting gliders closest to the arm to the gliders further away from the arm, but there was no need to complete the project.
The third and fourth arms are extreme compression construction arms "ecca", where a programming language interpreter is created and individual incoming letters are interpreted as instructions specifying which phase (mod 2) and line of glider to emit.
We have achieved an optimal encoding that requires about 7-8 bits to emit a typical slow p2 salvo of gliders.
The instruction set includes a move direction change option, move4 (repeated), move2, move1, color option, phase option.
Stopping the move4 loop results in a glider being fired "near" the current arm position after a defined number of letters.
The third arm uses exactly this set of options, while the fourth arm executes move1 after a change of direction, further increasing its efficiency. The fourth arm uses "yellow lane" filtering technology, which allows its components to be recycled, resulting in a more compact and less expensive design.
On the contrary ecca1 is built as p1 pattern what allows selecting less expensive options during the build by the binary arm (at few places where p8 restriction would be required in ecca2 build).
The arms are capable of firing gliders with 4 combinations of phase mode 8 and color (all four combinations of phase mode 2 and color). This is perfectly fine for slow salvos with a p2 restriction, but building p8 salvos requires limiting the salvos to use only a limited set of "signature" color combinations of glider phases.
This led to a modification of the psamake program (transforming "neo" Spartan configurations for slow salvos that are built from a single block). When a bespoke subsalvo builds a p8 pattern (initial call by a single glider), a 0 degree one time turner prefix is optionally allowed for a phase/color correction. Similarly, p2 salvos are transformed to the required p8 phases corresponding to the signature.
There are several other prerequisites for building a ship. We should implement a storage where the bits to be fed into the binary arm and later into the ecca1 and ecca2 arms are encoded. Fortunately, a slow salvo of 8 gliders fired symmetrically into the central "spine" of the track from both sides (the ship cannot lose symmetry) will create 4 blocks near the spine if there was nothing there, or move the blinker from its given position by 2 pixels (east) emitting glider back.
There are a few more requirements to build the ship. We should implement a storege of bits that will be fed into the binary arm and later into the ECCA1 and ECCA2 arms. Fortunately, a slow salvo of 8 gliders fired symmetrically into the central “spine” track from both sides (the ship cannot lose symmetry) will create 4 blocks near the spine if there is nothing there, or move the blinker from its current position by 2 pixels (east) emitting glider backward.
The fuse arm fires 8 90 degree glider producing switch engines “GPSE90” that fire the slow salvo and convert the blinkers on the spine into a traveling signal.
The signal is then fed into the binary arm by a pair of gliders firing the gliders back. One of the gliders is reflected so that they annihilate on impact. The glider signal from the tape annihilates the glider from one stream (negative signal), so the reflected glider from the other stream is not annihilated at the start of the arm. The ever-present glider of the binary arm is created by a gun of the corresponding period (repeated in the third and fourth arms).
The fuse arm creates a reflector (p8bouncer) and a seed for a pair of corderships so that the first bit read triggers the corderships in synchronized phase to allow annihilation (and reflection).
To trigger the fuse arm, we need a target for the arm gliders to be modified. This is what the pre-fuse does. It releases a glider, travels some distance, and releases a perpendicular lwss on collision course with the glider. The collision leaves behind debris (the target of the fuse arm) and launches two gliders into the spine. One of them hits its mirror image and creates a biblock, while the other triggers the fuse arm in the middle.
We already know what the fuse arm does, the binary arm creates ecca1 and triggers a meteor shower creating a reflector on the input signal path. When the arm's anchor stack is removed, ecca1 starts interpreting the input bits. The goal of the ecca1 arm is to clean up the west. It destroys the remnants of the dirty mwss creations and reconstructs the initial bliner configurations shifted 2 pixels to the east (we can't build anything on the spine due to symmetry, but we can modify the already presented content of the spine).
It also creates ecca2, the hive needed to transition to the one-dimensional state and the ship needed at the end of the tape cleaning.
Ecca1 finishes its work by destroying its reflector on the input signal path.
Ecca2 is responsible for cleaning up the east. It is built with a destruction seed (computation supported by the gSoD program), which means that one incoming glider on the correct path will cause the pattern to disappear. The destruction seed generates two gliders.
One of the goals of ecca2 is to create seeds of destruction of the reflectors on the input path - one destruction seed for the reflectors of ecca1 and one for the reflector, thus triggering the binary arm. The ship created by ecca1 near the spine converts a pair of cleaning mwss into a single glider, which triggers the destruction seed of ecca2. The exit gliders of ecca2 seed of destruction, are navigated by one time reflectors to the destruction seeds of the reflectors of ecca1 and the binary arm.
Ecca2 converts ecca1 into a ship (a disposable turner), which would play its role at the very end of the ship's period
(a slow destructive salvo combined with the trivial task of pslmake).
(the rest of the blinker of the binary arm stack is also destroyed by ecca2).
ECCA2 should also clean up the remains of the gun used by the binary arm (in the current version we stopped it with ecca1, but it would probably be equally or more efficient to stop it with ecca2)
(slow 2 salvo is used there and half honey farm to honey farm slow salvo move collection helps a lot in such design).
The most important task of ecca2 is to stop the tape reading mechanism and clean it up.
The salvo of synchronized gliders stops the GPSE90 and the corderabsorbers are assembled in time to stop the cordership pair
(as a tool a program was used that automatically combines a pre-calculated splitters and reflectors (consisting of at most two small objects) to create a given pair of synchronized parallel gliders).
The glider streams fired from the corderships do not stop at the same time, so the 3 escaping gliders are also stopped by the seed created by ecca2.
In order for ecca2 to create a seed to stop the GPSE90, it must clean up the irregularities of the GPSE90's trajectory debris. (destructive salvo calculated into a periodic pattern...). Similarly, the far-end cleanup converts the debris of the stalled GPSE90 into a periodic pattern.
Ecca2 must send corderfleets cleaning a periodic pattern (of arbitrary length). Therefore, it must create corderabsorbers on the other side (we chose corderabsorbers close, ships travelling from far).
(used a program to search for corderfleets cleaning compatible periodic patterns) ... the corderships were created using modern 11 cluster seeds (except for the one closest to the arm, where 12 cluster seeds were used to fit close to the arm)).
The corderfleet was also used to destroy the remnants of a pair of corderships.
The last task of ecca2 was to fire a salvo to create two mwss that would clean the blocks created during the tape reading (this would trigger a seed of ecca2 destroyal at the end).
The corderabsorber for the last cordership is modified and instead of annihilating with the cordership it emits a perpendicular glider that hits the boat from the ECCA1 conversion to bounce to the behive and converts it into a one-dimensional pattern, starting a new generation.
The ECCA2 compiler used agnosticised lane phase recipes and chose the optimal route from the options (shortening the tape as much as possible). This optimization was not done in ECCA1, binary or fuse arm.
Pretty please with a cherry on top use standard SI multipliers for numbers like this. I can't be sure without reading the article whether you mean 3.7G cells or 3.7T cells. Billion is ambiguous having different meanings to different people and should not be used as a word any longer.
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.
flufluflufluffy|2 months ago
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
falcor84|2 months ago
IncreasePosts|2 months ago
culi|2 months ago
pkilgore|2 months ago
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!
layer8|2 months ago
It’s also a relatively sparse line, as the number of live cells is less than a hundredth of the line’s extent: https://conwaylife.com/wiki/Unidimensional_spaceship_1
scotty79|2 months ago
Romario77|2 months ago
[deleted]
wrs|2 months ago
ekjhgkejhgk|2 months ago
https://www.youtube.com/watch?v=eMJk4y9NGvE
IAmBroom|2 months ago
Your SO is likely only enthused to the degree that it affects your mood. "So this RISC architecture isn't compliant with ADA-1056 after all? And you were right all along? Wow, that's great, honey!"
pavel_lishin|2 months ago
tomcam|2 months ago
MasterScrat|2 months ago
I picture entities playing with our universe, "it starts slow but check it out at the 13.8B mark"
Cthulhu_|2 months ago
7373737373|2 months ago
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...
jmsgwd|2 months ago
One of the chapters asks "what is life?". It considers (and rejects) various options, and finally settles upon a definition based on Von Neumann-style self-replicating machines using blueprints and universal constructors, and explains why this is the most (only?) meaningful definition of life.
Later, it talks about how one would go about creating such a machine in Conway's Game of Life. When the book was written in 1984, no one had actually created one (they need to be very large, and computers weren't really powerful enough then). But in 2010 Andrew J. Wade created Gemini, the first successful self-replicating machine in GoL, which I believe meets the criteria - and hence is "alive" according to that definition (but only in the sense that, say, a simple bacteria is alive). And I think it works somewhat like how it was sketched out in the book.
Another chapter estimated how big (and how densely populated) a randomly-initialized hypothetical GoL universe would need to be in order for "life" (as defined earlier) to appear by chance. I don't recall the details - but the answer was mind-boggling big, and also very sparsely populated.
All that only gives you life though, not intelligence. But life (by this definition) has the potential to evolve through a process of natural selection to achieve higher levels of complexity and eventually intelligence, at least in theory.
Legend2440|2 months ago
You might have better luck with other variants. Reversible cellular automata have a sort of 'conservation of mass' where cells act more like particles. Continuous cellular automata (like Lenia) have less chaotic behavior. Neural cellular automata can be trained with gradient descent.
jameshart|2 months ago
Someone|2 months ago
I think people will disagree about whether “Turing-complete” is powerful enough for supporting intelligence but let’s assume it does.
> So, will a random initial position (tend to) be filled with super-intelligent life forms, or will the chaos reign?
Even if it doesn’t, it might take only one intelligent life form for the space to (eventually) get filled with it (the game of life doesn’t heave energy constraints that make it hard to travel over long distances, so I don’t see a reason why it wouldn’t. On the other hand, maybe my assumption that all intelligent life would want to expand is wrong), and in an infinite plane, it’s likely (¿certain?) one will exist.
On the other hand it’s likely more than one exists, and they might be able to exterminate each other.
qnleigh|2 months ago
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
iamgopal|2 months ago
pontifier|2 months ago
Does that you exist any less fully because its not currently in the memory of a computer being evaluated?
triggercut|2 months ago
sethaurus|2 months ago
This is a linear sequence of bits, which when interpreted as a Game of Life board, "prints" an exact copy of itself 2 pixels to the right (leaving no trace of the original).
I suppose its job would be easier if it only had to construct a copy of itself rather than "moving" itself, but I enjoy the interpretation that it's a linear "tape" of bits which prints its own code transposed by 2 pixels, and takes an unfathomable amount of time and space to do so. Beautiful.
HTHThreee|2 months ago
pka|2 months ago
In the book he also talks about GoF, but one of the fascinating experiments he did is that a "computronium" of initially random Brainfuck programs (that obviously don't do anything interesting in the beginning) that mutate (by flipping random bits) and merge (by taking two random programs and sticking them together) eventually, after a sudden phase transition, start to self replicate by producing gradually better copies of themselves!
He also argues that symbiogenesis (merging replicators into a whole that does more than its parts) is the main driving force of evolution instead of just random mutations, because the random Brainfuck computronium eventually produces replicators even without the random bit flips.
[0] https://whatisintelligence.antikythera.org
zkmon|2 months ago
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.
eig|2 months ago
pavel_lishin|2 months ago
creatonez|2 months ago
sebzim4500|2 months ago
adzm|2 months ago
syncsynchalt|2 months ago
I'm really charmed by the linked thread and all the passion and work it belies. Congrats to those involved!
bntr|2 months ago
blackle|2 months ago
ekjhgkejhgk|2 months ago
NooneAtAll3|2 months ago
glider is a specific spaceship, but name for "moving pattern" is spaceship
rtkwe|2 months ago
https://conwaylife.com/wiki/Spaceship
herodoturtle|2 months ago
cpfohl|2 months ago
Conway's game of life: https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
Gliders: https://en.wikipedia.org/wiki/Glider_(Conway%27s_Game_of_Lif...
nerevarthelame|2 months ago
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.
cool_dude85|2 months ago
DexesTTP|2 months ago
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.
Isamu|2 months ago
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.
OscarCunningham|2 months ago
wffurr|2 months ago
metalliqaz|2 months ago
pavel_lishin|2 months ago
> Seems there is a bug in the forum, when more people write a post at the same time the post sometimes vanishes.
HackerThemAll|2 months ago
dcel|2 months ago
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.
bezko|2 months ago
Looking forward to the impending AI and crypto crash and have people run GoL simulations on expensive computer systems like it's 1972 again.
munchler|2 months ago
https://quoteinvestigator.com/2014/01/12/history-rhymes/
kbelder|2 months ago
dvgrn|2 months ago
https://conwaylife.com/wiki/Lisp_in_Life
That shares the impressive inefficiencies of the Quest for Tetris project, though. For something that's much more practical to run, and can be programmed to do things like print out the digits of pi in-universe, see
https://conwaylife.com/wiki/APGsembly
gdevillers|2 months ago
pavel_lishin|2 months ago
marifjeren|2 months ago
marcandre|2 months ago
londons_explore|2 months ago
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.
culi|2 months ago
If you look at the placement of Journal of Cellular Automata in SciMago's Shape of Science visualization[0] you'll see that it's completely surrounded by machine learning/AI journals
[0] https://www.scimagojr.com/shapeofscience/
btilly|2 months ago
The Game of Life is Turing complete. And therefore a complete analysis of how to write programs in it would imply a solution to the Halting problem. Which is impossible.
Jaxan|2 months ago
vrighter|2 months ago
thih9|2 months ago
I'm on a smartphone, I'd like to look at the end result.
HTHThreee|2 months ago
DesiLurker|2 months ago
terlisimo|2 months ago
1) GoL is turing complete
2) there are algorithms that calculate digits of Pi or e.
so... yes?
but if I just took any old Pi-digits algorithm and encoded it on GoL, its appearance would not be meaningful or "elegant" to our senses. You're probably asking "what does the shortest/most elegant program to calculate Pi in GoL look like, and does it maybe have some unexpected relation to other mathematical terms like, I dunno, Euler's identity or... Mandelbrot set?" And then you would probably need to answer the question "Well, how would you like the digits encoded and represented?".
All of a sudden your question becomes a bit ambiguous. Or did I misunderstand what you meant?
I mean.... I think I feel what you're asking, like... is there some primal version of Pi that can be encoded in GoL initial condition with as few bits as possible but I'm afraid that the answer is something like "well, that depends on what you mean by [...]"
mNovak|2 months ago
Traubenfuchs|2 months ago
In which direction does it glide?
HTHThreee|2 months ago
Dwedit|2 months ago
martianlantern|2 months ago
adzm|2 months ago
>>>
Unidimensional spaceship can be interpreted as a demonstration of the progress of recent years in slow salvo technology and the various arms that use it.
The project uses 4 construction arms, with the last three sharing principles with the arms used in the RCT15 project. The first arm is newly invented just for this case. I was not part of the community at the time the principles of the first two arms were studied, but let me describe them anyway.
The one line restriction limit us to using blinkers as the basis of the first arm. Interestingly, a small perturbation at the end of some blinker configuration makes the pattern unstable, and several blinker patterns allow the perturbation "fuse" to move in a controlled manner. Various configurations have been discovered that leave no debris but move at different speeds. Some configurations have been found that produce backward-firing mwss (and leave debris), head-on collisions of mwss that transform them into gliders for both glider colors. By combining these configurations, we can trigger a fusion in the middle of a carefully chosen arrangement of blinkers that would synchronize the mwss collisions at the desired time parity at a prescribed x-coordinate and generate a glider with a prescribed phase and trajectory, so that such an arm could create any p2 recipe.
The second arm used is a binary arm, where a pair of synchronized gliders on the same trajectories are used, with one glider always present and the presence of the other gliders allowing modification of the resulting configuration. Careful study of the results of various words using letters "1" and "2" (indicating the presence of the second glider) led to the discovery of specific modifications of the target "anchor" configuration.
Some of them allow you to move the "head" of the anchor stack to move closer/farther from the base of the arm. Some sequences will generate a perpendicular glider. Not all mod 8 phases and colors are known, but with careful "head positioning" any p8 recipe could be built with such an arm. The program used for the translation only used single blinker anchor technology, which produces a glider for a cost of around 100 bits ("letters"). The agnosticisation salvas of the p8 recipe to use only the p1/p2 constraints on the glider phases (when possible) greatly reduces the number of bits required. Alternative glider paths also help, leading to the same stable configurations during a slow salvas. Currently, there is an alternative method with around 80 bits per glider using 4 different anchors deep in the "arm target stack". The code could be improved by some form of dynamic programming by compiling the salvo from the parts emitting gliders closest to the arm to the gliders further away from the arm, but there was no need to complete the project.
The third and fourth arms are extreme compression construction arms "ecca", where a programming language interpreter is created and individual incoming letters are interpreted as instructions specifying which phase (mod 2) and line of glider to emit.
We have achieved an optimal encoding that requires about 7-8 bits to emit a typical slow p2 salvo of gliders.
The instruction set includes a move direction change option, move4 (repeated), move2, move1, color option, phase option. Stopping the move4 loop results in a glider being fired "near" the current arm position after a defined number of letters. The third arm uses exactly this set of options, while the fourth arm executes move1 after a change of direction, further increasing its efficiency. The fourth arm uses "yellow lane" filtering technology, which allows its components to be recycled, resulting in a more compact and less expensive design. On the contrary ecca1 is built as p1 pattern what allows selecting less expensive options during the build by the binary arm (at few places where p8 restriction would be required in ecca2 build). The arms are capable of firing gliders with 4 combinations of phase mode 8 and color (all four combinations of phase mode 2 and color). This is perfectly fine for slow salvos with a p2 restriction, but building p8 salvos requires limiting the salvos to use only a limited set of "signature" color combinations of glider phases.
This led to a modification of the psamake program (transforming "neo" Spartan configurations for slow salvos that are built from a single block). When a bespoke subsalvo builds a p8 pattern (initial call by a single glider), a 0 degree one time turner prefix is optionally allowed for a phase/color correction. Similarly, p2 salvos are transformed to the required p8 phases corresponding to the signature.
There are several other prerequisites for building a ship. We should implement a storage where the bits to be fed into the binary arm and later into the ecca1 and ecca2 arms are encoded. Fortunately, a slow salvo of 8 gliders fired symmetrically into the central "spine" of the track from both sides (the ship cannot lose symmetry) will create 4 blocks near the spine if there was nothing there, or move the blinker from its given position by 2 pixels (east) emitting glider back.
There are a few more requirements to build the ship. We should implement a storege of bits that will be fed into the binary arm and later into the ECCA1 and ECCA2 arms. Fortunately, a slow salvo of 8 gliders fired symmetrically into the central “spine” track from both sides (the ship cannot lose symmetry) will create 4 blocks near the spine if there is nothing there, or move the blinker from its current position by 2 pixels (east) emitting glider backward.
The fuse arm fires 8 90 degree glider producing switch engines “GPSE90” that fire the slow salvo and convert the blinkers on the spine into a traveling signal.
The signal is then fed into the binary arm by a pair of gliders firing the gliders back. One of the gliders is reflected so that they annihilate on impact. The glider signal from the tape annihilates the glider from one stream (negative signal), so the reflected glider from the other stream is not annihilated at the start of the arm. The ever-present glider of the binary arm is created by a gun of the corresponding period (repeated in the third and fourth arms).
The fuse arm creates a reflector (p8bouncer) and a seed for a pair of corderships so that the first bit read triggers the corderships in synchronized phase to allow annihilation (and reflection).
To trigger the fuse arm, we need a target for the arm gliders to be modified. This is what the pre-fuse does. It releases a glider, travels some distance, and releases a perpendicular lwss on collision course with the glider. The collision leaves behind debris (the target of the fuse arm) and launches two gliders into the spine. One of them hits its mirror image and creates a biblock, while the other triggers the fuse arm in the middle.
We already know what the fuse arm does, the binary arm creates ecca1 and triggers a meteor shower creating a reflector on the input signal path. When the arm's anchor stack is removed, ecca1 starts interpreting the input bits. The goal of the ecca1 arm is to clean up the west. It destroys the remnants of the dirty mwss creations and reconstructs the initial bliner configurations shifted 2 pixels to the east (we can't build anything on the spine due to symmetry, but we can modify the already presented content of the spine). It also creates ecca2, the hive needed to transition to the one-dimensional state and the ship needed at the end of the tape cleaning.
Ecca1 finishes its work by destroying its reflector on the input signal path.
Ecca2 is responsible for cleaning up the east. It is built with a destruction seed (computation supported by the gSoD program), which means that one incoming glider on the correct path will cause the pattern to disappear. The destruction seed generates two gliders. One of the goals of ecca2 is to create seeds of destruction of the reflectors on the input path - one destruction seed for the reflectors of ecca1 and one for the reflector, thus triggering the binary arm. The ship created by ecca1 near the spine converts a pair of cleaning mwss into a single glider, which triggers the destruction seed of ecca2. The exit gliders of ecca2 seed of destruction, are navigated by one time reflectors to the destruction seeds of the reflectors of ecca1 and the binary arm.
Ecca2 converts ecca1 into a ship (a disposable turner), which would play its role at the very end of the ship's period (a slow destructive salvo combined with the trivial task of pslmake). (the rest of the blinker of the binary arm stack is also destroyed by ecca2).
ECCA2 should also clean up the remains of the gun used by the binary arm (in the current version we stopped it with ecca1, but it would probably be equally or more efficient to stop it with ecca2) (slow 2 salvo is used there and half honey farm to honey farm slow salvo move collection helps a lot in such design).
The most important task of ecca2 is to stop the tape reading mechanism and clean it up. The salvo of synchronized gliders stops the GPSE90 and the corderabsorbers are assembled in time to stop the cordership pair (as a tool a program was used that automatically combines a pre-calculated splitters and reflectors (consisting of at most two small objects) to create a given pair of synchronized parallel gliders). The glider streams fired from the corderships do not stop at the same time, so the 3 escaping gliders are also stopped by the seed created by ecca2. In order for ecca2 to create a seed to stop the GPSE90, it must clean up the irregularities of the GPSE90's trajectory debris. (destructive salvo calculated into a periodic pattern...). Similarly, the far-end cleanup converts the debris of the stalled GPSE90 into a periodic pattern. Ecca2 must send corderfleets cleaning a periodic pattern (of arbitrary length). Therefore, it must create corderabsorbers on the other side (we chose corderabsorbers close, ships travelling from far). (used a program to search for corderfleets cleaning compatible periodic patterns) ... the corderships were created using modern 11 cluster seeds (except for the one closest to the arm, where 12 cluster seeds were used to fit close to the arm)).
The corderfleet was also used to destroy the remnants of a pair of corderships. The last task of ecca2 was to fire a salvo to create two mwss that would clean the blocks created during the tape reading (this would trigger a seed of ecca2 destroyal at the end).
The corderabsorber for the last cordership is modified and instead of annihilating with the cordership it emits a perpendicular glider that hits the boat from the ECCA1 conversion to bounce to the behive and converts it into a one-dimensional pattern, starting a new generation.
The ECCA2 compiler used agnosticised lane phase recipes and chose the optimal route from the options (shortening the tape as much as possible). This optimization was not done in ECCA1, binary or fuse arm.
nilslindemann|2 months ago
avhon1|2 months ago
IAmBroom|2 months ago
theendisney|2 months ago
mnw21cam|2 months ago
pugworthy|2 months ago
Jaxan|2 months ago
jacquesm|2 months ago
HTHThreee|2 months ago