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
And for a related rabbit hole where people actually went all the to the bottom, there's of course the full implementation of Tetris in GoL which was nerd-sniped by a CodeGolf challenge
Sometimes you see something that makes you wonder how it is that you get to exist in the same world as people with the drive and intelligence to do truly awesome ( in the original sense) thing like this. I am proud of myself when the compiler works on the first try.
I think it's awesome that they can do this amazing fun esoteric stuff, but at the same time a small part of me thinks maybe they need to be doing something more meaningful in the real world.
I wonder, what would that be, that thing that is more meaningful?
I would make the case that, zoomed out far enough, nothing at all is meaningful, so you might as well make beautiful things, and this is a delightfully beautiful thing.
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.
I think it appeals to the same itch that languages like Brainfuck scratch.
There's something exceedingly interesting about how you can model complexity with something extremely simple. Brainfuck is fun because it forces you to think extremely low level, because ultimately it is basically just a raw implementation of a Turing machine. I wouldn't want to write a big program in it, but it is fun to think about how you might express a complicated algorithm with it.
Similarly with CGOL, it is really interesting to see how far you can stretch really simple rules into something really complex.
I've written CGOL dozens of times, it's a common project that I do to "break in" a language I've learned, since it's not completely trivial but it's simple enough to not be frustrating, and I completely understand why math/computability-theory folks find it something to dedicate brain power to.
I have a weird love for Brainfuck. It's a tiny, incredibly simple language that you can write an interpreter for in an hour, it's effectively a super-simple byte code that can easily be extended and used as a compilation target for simple languages.
Honestly, as an educational tool, the only thing wrong with it is the name!
I have no idea how I'd be able to pitch this to a university (or even who I could pitch it to), but I would absolutely love to teach a computability course using Brainfuck as the language, just to really show students how low-level logic can be.
I would probably need to find a similar language with a different name though.
You might find mlatu-6[0] interesting- it’s convertible to SKI calculus but concatenative (like Forth) rather than applicative. It’s actually a subset of Mlatu, a language I created for similar reasons to explore “how low can you go.”
When I was an undergrad at Georgia Tech, one of my intro computer science classes had us implement something in brainfuck. Turns out college kids are quite comfortable with swear words.
Assembly is higher level logic than brainfuck, especially on modern chips. You have built in instructions for arithmetic and conditionals/branches and you can allocate memory and point to it.
You don’t really get any of that with brainfuck. You have a theoretical tape and counters and that’s basically it.
SKI calculus is pretty neat, too. You get no tape, no counters. (But it's not quite as bad to program in as brainfuck, because you can built more ergonomic contraptions to help you along.)
SKI can, of course, be de-optimised a bit further by replacing I with SKK. You are right though that it is relatively simply to go from something that looks like a normal program languages to a pile of S and K combinators. Not the most efficient way to compute though!
One of my favorite calculations of pi is to pick random coordinates in a unit square and count how many of them are in a circle. it's so stupid and so clever at the same time.
This was recreated from memory. I think it is close but I may have a bounding bug.
import random
def pi(count):
inside = 0
for i in range(count):
test_x = random.random()
test_y = random.random()
if test_x ** 2 + test_y ** 2 < 1:
inside += 1
return inside / count * 4 #above is a quarter circle
print(pi(2 ** 30) )
With the metatopic of this thread being obscure languages, I had some fun squeezing this into some list comprehensions (maybe someone's got an idea of how to keep track of the state within the list):
```
$ cat << EOF > pi.py
state = [0, 0, 2*8, 2*12]; _ = [print(f'\rRun {state.__setitem__(0, state[0] + 1) or state[0]}/{state[3]} | Last \u03c0: {current_pi:.6f} | *Average \u03c0: {(state.__setitem__(1, state[1] + current_pi) or state[1]) / state[0]:.6f}*', end='', flush=True) for current_pi in [(4 * sum([1 for _ in range(state[2]) if __import__("random").random()*2 + __import__("random").random()*2 < 1]) / state[2]) for _ in range(state[3])]]; print()
EOF
$ time python3 pi.py
Run 4096/4096 | Last π: 3.140625 | *Average π: 3.143051*
python3 pi.py 0.41s user 0.01s system 99% cpu 0.429 total
```
Play around with the `2*8` and `2*10` values in the state, they control the amount of rounds and the range in which the random values get generated respectively.
> I've written CGOL dozens of times, it's a common project that I do to "break in" a language I've learned, since it's not completely trivial but it's simple enough to not be frustrating, and I completely understand why math/computability-theory folks find it something to dedicate brain power to.
Writing a naive CGOL is fun and quick. But writing a _fast_ one can get arbitrarily complicated.
Yeah, a million years ago I did that one as a convolutions so I could run it on the GPU when I was learning OpenCL. That was my first exposure to “optimizing” CGOL.
"So did Achilles lose his friend in war, and Homer did no injustice to his grief by writing about it in dactylic hexameters" - Tobias Wolff, Old School
if you find that fascinating then you'll be blown away by something called 'Wolfarm physics project'. it basically is trying to recreate entire physics using such baseline 'graph update' rules like 'Game of Life'. So far no predictions yet but very interesting.
Wolfram is kind of obsessed with cellular automata, even went and wrote a whole book about them titled "A New Kind of Science". The reception to it was a bit mixed. CA are Turing-complete, so yeah, you can compute anything with them, I'm just not sure that in itself leads to any greater Revealed Truths. Does make for some fun visualizations though.
A new kind of science is one of my favorite books, I read the entirety of the book during a dreadful vacation when I was 19 or 20 on an iPod touch.
It goes much beyond just cellular automata, the thousand pages or so all seem to drive down the same few points:
- "I, Stephen Wolfram, am an unprecedented genius" (not my favorite part of the book)
- Simple rules lead to complexity when iterated upon
- The invention of field of computation is as big and important of an invention as the field of mathematics
The last one is less explicit, but it's what I took away from it. Computation is of course part of mathematics, but it is a kind of "live" mathematics. Executable mathematics.
Super cool book and absolutely worth reading if you're into this kind of thing.
I would give the same review, without seeing any of this as a positive. NKS was bloviating, grandiose, repetitive, and shallow. The fact that Wolfram himself didn’t show that CA were Turing complete when most theoretical computer scientists would say “it’s obvious, and not that interesting” kinda disproves his whole point about him being an under appreciated genius. Shrug.
That CA in general were Turing complete is 'obvious'. What was novel is that Wolfram's employee proved something like Turing completeness for a 1d CA with two states and only three cells total in the neighbourhood.
I say something-like-Turing completeness, because it requires a very specially prepared tape to work that makes it a bit borderline. (But please look it up properly, this is all from memory.)
Having said all that, the result is a nice optimisation / upper bound on how little you need in terms of CA to get Turing completeness, but I agree that philosophically nothing much changes compared to having to use a slightly more complicated CA to get to Turing completeness.
The question really ultimately resolves to whether the universe can be quantized at all levels or whether it is analog. If it is quantized I demand my 5 minutes with god, because I would see that as proof of all of this being a simulation. My lack of belief in such a being makes me hope that it is analog.
Computation does not necessarily need to be quantized and discrete; there are fully continuous models of computation, like ODEs or continuous cellular automata.
That's true, but we already know that a bunch of stuff about the universe is quantized. The question is whether or not that holds true for everything or rather not. And all 'fully continuous models of computation' in the end rely on a representation that is a quantized approximation of an ideal. In other words: any practical implementation of such a model that does not end up being a noise generator or an oscillator and that can be used for reliable computation is - as far as I know - based on some quantized model, and then there are still the cells themselves (arguably quanta) and their location (usually on a grid, but you could use a continuous representation for that as well). Now, 23 or 52 bits (depending on the size of the float representation you use for the 'continuous' values) is a lot, but it is not actually continuous. That's an analog concept and you can't really implement that concept with a fidelity high enough on a digital computer.
You could do it on an analog computer but then you'd be into the noise very quickly.
In theory you can, but in practice this is super hard to do.
If your underlying system is linear and stable, you can pick any arbitrary precision you are interested in and compute all future behaviour to that precision on a digital computer.
Btw, quantum mechanics is both linear and stable--and even deterministic. Admittedly it's a bit of a mystery how the observed chaotic nature of eg Newtonian billard balls emerges from quantum mechanics.
'Stable' in this case means that small perturbations in the input only lead to small perturbations in the output. You can insert your favourite epsilon-delta formalisation of that concept, if you wish.
To get back to the meat of your comment:
You can simulate such a stable system 'lazily'. Ie you simulate it with any given fixed precision at first, and (only) when someone zooms in to have a closer look at a specific part, you increase the precision of the numbers in your simulation. (Thanks to the finite speed of light, you might even get away with only re-simulating that part of your system with higher fidelity. But I'm not quite sure.)
Remember those fractal explorers like Fractint that used to be all the rage: they were digital at heart---obviously---but you could zoom in arbitrarily as if they had infinite continuous precision.
Sure, but that 'If' isn't true for all but the simplest analog systems. Non-linearities are present in the most unexpected places and just about every system can be made to oscillate.
That's the whole reason digital won out: not because we can't make analog computers but because it is impossible to make analog computers beyond a certain level of complexity if you want deterministic behavior. Of course with LLMs we're throwing all of that gain overboard again but the basic premise still holds: if you don't quantize you drown in an accumulation of noise.
> Sure, but that 'If' isn't true for all but the simplest analog systems.
Quantum mechanics is linear and stable. Quantum mechanics is behind all systems (analog or otherwise), unless they become big enough that gravity becomes important.
> That's the whole reason digital won out: not because we can't make analog computers but because it is impossible to make analog computers beyond a certain level of complexity if you want deterministic behavior.
It's more to do with precision: analog computers have tolerances. It's easier and cheaper to get to high precision with digital computers. Digital computers are also much easier to make programmable. And in the case of analog vs digital electronic computers: digital uses less energy than analog.
For all we know, it could be distinct layers all the way down to infinity. Each time you peel one, something completely different comes up. Never truly knowable. The universe has thrown more than a few hints that our obsession with precision and certainty could be seen cosmically as "silly".
In our current algorithmic-obsessed era, this is reminiscent of procedural generation (but down/up the scale of complexity, not "one man's sky" style of PG).
However, we also have a long track record of seeing the world as nails for our latest hammer. The idea of an algorithm, or even computation in general, could be in reality conceptually closer to "pointy stone tool" than "ultimate substrate".
> For all we know, it could be distinct layers all the way down to infinity. Each time you peel one, something completely different comes up. Never truly knowable. The universe has thrown more than a few hints that our obsession with precision and certainty could be seen cosmically as "silly".
That's a tempting thing to say, but quantum mechanics suggests that we don't have infinite layers at the bottom. Most thermodynamic arguments combined with quantum mechanics. See eg also https://en.wikipedia.org/wiki/Bekenstein_bound about the amount of information that can even in theory be contained in a specific volume of space time.
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.
I searched several of these terms and they are all specifically jargon of game of life enthusiasts, (i.e. search reaults are all on fansites related to game of life) not general cellular automata jargon.
conwaylife.com isn't just for GOL, although it is the main subject, there is an Other Cellular Automata forum.
also it's not really a fansite, it's a bit more academic than what would be considered a "fansite".
> 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.
As the wiki page states, the period is 133076755768, and it moves by two cells in that time. Spaceships in GoL by definition don’t leave anything behind, they produce the exact same configuration, just shifted across the grid.
Given that it starts as a single line, it is symmetric in the axis implied by that line, and hence can’t possibly move diagonally or orthogonal to the line. Hence it moves in the direction of the line.
Yeah, “orthogonal” here just means “not diagonal”. Since GoL configurations don’t have a distinguished orientation (you can rotate and/or mirror them however you like), it wouldn’t make sense to specify up/down/left/right, at least not without first fixing an (arbitrary) orientation.
I’m not sure where our guidelines/norms are on this kind of thing, but I get the sense that most of us feel very capable of pasting articles into LLMs ourselves.
What we’re less capable of—and the reason we look to each other here instead—is distinguishing where the LLM’s errors or misinterpretations lie. The gross mistakes are often easy enough to spot, but the subtle misstatements get masked by its overconfidence.
Luckily for us, a lot of the same people actually doing the work on the stuff we care about tend to hang out around here. And often, they’re kind enough to duck in and share.
Thank you in any case for being upfront about it. It’s just that it’d be a shame and a real loss if the slop noise came to drown out the signal here.
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?
I enjoy the [GoL -> our “reality” -> outside-the-simulation] comparison. It really drives home how unlikely we would be to understand the outside-the-simulation world.
Of course, there are other variants (see qntm's https://qntm.org/responsibility) where the simulation _is_ a simulation of the world outside. And we have GoL in GoL :-)
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.
can be programmed to self-replicate in any number of ways, but it's so big that it's very hard to simulate it through a full cycle. By contrast, Pavel Grankovskiy's "DOGun SaGaQR"
OK, I didn't know if it was a "true" replicator (what even does "true" mean) so I excluded it. And, running a true replicator from other rule in 0E0P takes millenia, so that leaves DOGun SaGaQR (specifically the QR configuration). Sorry.
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.
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.
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.
‘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.
> it might take only one intelligent life form for the space to (eventually) get filled with it
It wouldn't need to be intelligent to do this; it could be a self-replicating machine with no intelligence at all - which is orders of magnitude simpler and therefore more likely.
Chaotic initial state -> self-replicating machine -> intelligence is much more likely than chaotic initial state -> intelligence.
(See my other reply to the GP comment about The Recursive Universe, where all this is discussed.)
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?
Depending on the infinite grid filling scheme even these properties may not be sufficient to guarantee that every two dimensional pattern is initially generated because the grid is two-dimensional, but the number property is "one-dimensional". A spiral pattern for example may always make it line up in a way such that certain 2d patterns are never generated.
Since it's not provable with pi, then we'd have to do a more circuitous proof of every finite pattern occurring. Inspired by Champernowne's constant, I propose a Pontifier Pattern that is simple, inefficient, but provably contains every finite pattern.
Starting at the origin, mark off rows of squares. the Nth row would contain NxN^2 squares of size n x n. Each square would be filled in left to right reading order with successive binary numbers with the most significant digit at the top left.
Somewhere in that pattern is the physics simulation of you reading this comment :)
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.
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.
It's possible. It'd just be a 3D visualization and more importantly, stupendously huge. If each cell was a cubic millimeter, the shape would be 3700km wide, and stretch 1/3rd of the way to the moon.
And if each cell was a cubic micrometer (which is a side length 200-300 times smaller than a pixel on a typical screen and 50-100 times thinner than a human hair), it'd still stretch 3.7 kilometers, which is about the length of a commercial airport runway.
I see what you're saying, but I think it's a misunderstanding. 1D here only means that there's some state where the active cells are confined to one row — but one row within the ordinary 2D GoL plane. I'm sure the next iteration leaps off the line immediately. Search for "Blinker" here to imagine how it could start spreading off the line.
This is one of those tricky things, highly dependent on context.
If you're talking about Conway's Game of Life patterns, then "gliders" are the 5-cell spaceships that travel diagonally, and all other moving things are "spaceships" but not "gliders". If you call a Conway's Life non-glider spaceship a "glider" you'll mostly just confuse people.
But if you're talking about other CA rules -- especially rules where there isn't any 5-cell diagonal spaceship -- then "glider" is very commonly used to refer to other moving patterns.
For example, David Eppstein's "Gliders in Life-Like Cellular Automata" database was active for decades -- recording spaceships across a large rulespace, not just Conway's Life. It's an accepted generalization of the term, somewhat like saying "Xerox machine" for any old copying machine whether or not it was built by Xerox.
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.
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:
As noted by others, the title is mistaken; this is a spaceship, not a glider. (As explained in the Wikipedia article, "glider" refers to a specific 5-cell pattern discovered very early on.)
> So finally 2/133076755768 ship of starting bounding box 3707300605x1 is here
My understanding is that 2/133076755768 is the speed, in (number of cells translated) / (number of generations to repeat).
what is significant about making such a peculiar shape?
I find it difficult to believe that making a recurrent structure that translates in the grid (my lay language of doing what a glider does) requires a preposterously long structure like this,
so my guess was, is the excitement that someone made something extremely long, and there is some kind of race to make bigger and bigger structures with this behavior, akin crudely to the race to compute digits of Pi?
Or is it rather that no one has described a structure which "glides," with this preposterous number of cycles... which I would guess is coupled to the size?
Or is it rather that no one has described a 1D structure which "glides," at all...?
I would think that if what's desired is to find novel larger-scale structures, the best approach today would be to just fuzz noise of all kinds in large windows, let them iterate, and put the energy into the ML which evaluates the evolution of the world to categorize the results...
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.
Golly with hashlife algorithm is quite amazing. You can simulate and visualize quite a bit of it.
Summary:
In the end I was able to go through full period with the memory limit set to 35GB of memory. Most of the time all the action happens in 1+3x2 straight lines with different angles no more than 100 cells wide each. There were multiple distinct phases. Some one could definitely make an interesting visualization zooming in one the distinct regions at different stages of progression. General shape is horizontal line, <- shaped arrow, arrow with kite head, arrow with 2 nested kites, 2 giant nested kites, kite, arrow, horizontal line.
At first I was able to simulate first 15*10^9 generations quite quickly. And you could see some of initial stages. During first 2e9 generations it was using only 500MB of memory, somewhere between 2e9-4e9 it started to slow down. After bumping the memory it limit to 16G it was able to spedup again until ~15e9.
Initially it looks like 3 strings xxx. First one the shortest, second slightly longer and third even longer. Pattern xxx oscilates between horizontal and vertical giving stable form to store information.
Shortest string starts to get consumed from right to left.At some point it emits 2 gliders diagonally to the up/left and down left. After a while there are 2 vertical spaceships which collide with 2 diagonal gliders. After a bit more it starts to emit stream of gliders to the up right direction with overall shape being like arrow. At the back of arrows the gliders start to build a structure for next stage. The constructed structure starts creating bigger stream in the up right direction which in turn starts emiting stream down right back to the horizontal line. Once it meets original line it creates a new line towards first diagonal at more gradual angle. Thus an arrow like shape with tip consisting of 2 nested kites keeps expanding and consuming the line of oscilating xxx. By the generation 2e9 it has processed first 2 smallest of 3 sequences. At ~30e9 it reaches end of third line and inner kite starts to disappear outer kite keeps expanding. 37e9 Inner kite has fully disappeared.
At this point I further bumped RAM so that I can inspect zoomed in look at 1x speed. Now and probably previously what looked like sharp tip of arrow actually is more complicated machinery receiving in stream of gliders processing them and then emitting towards front in a way that reconstructs line of xxx. I am guessing at this point it is reconstructing initial line of xxx.
At ~44e9 first segment of line was reconstructed and machinery started to get torn down? It started to rebuild something near the outer edge of arrow front. And shortly creates new stream of spaceships along the outside of arrow. Most of the time structure consisted of 7+2 similar parallel streams. Some slowdown at ~66e9 probably transition to new phase. Front of kite detaches from central line, outer corner of kite also starts to tear separate and tear down. 88e9 back of kite has fully disappeared leaving only arrow. 95e9 central line start to shrink shorter. 105e9 central line has returned to sequence of xxx. The sides of arrow are still there. 117e9 sides arrow break in half and erase from middle. 133e9 back to single line and start from beginning.
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
Specifically, after 133_076_755_768 steps, the 1-dimensional pattern reoccurs translated by two pixels. On skimming the thread I haven't determined if that shift is parallel or perpendicular to the line.
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
“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.
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.
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 [...]"
yes you are right the question was ambiguous. WHat I was really looking for is if there is a way to physically derive PI out of some basic cellular automata operations. that does not necessarily have to involve circles etc. much less so about representing digits of PI itself. just that an pattern that evolves into ever more accurate values of pi (or a quantity derived from pi). this definitly must not be encoded or somehow preprogrammed into the GoL's initial condition. In fact I dont even care if the evolution rules of standard GoL are followed. just that SOME set of rules automatically produce PI-derivative.
the reason it would be cool is because then we've taken a most fundamental geometric constant and derived it from purely graph update type of mechanics. if you could do that then likely you can do a whole set of other things like physical laws.
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.
If the first Star Trek episodes were written today, they could have very well used GoL terminology as technobabble. The depth of the GoL community lingo always amazes me, as an outsider
If it's garbage, it's reposting garbage. A huge percentage of posts are garbage anyway, whether because they are mere opinions, or because they are overconfident guesses from Internet Experts(TM).
If it's not garbage, it shines a light into the workings without each of us having to understand what's going on.
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.
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.
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.
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.
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
Their free book "Conway’s Game of Life: Mathematics and Construction" is a great starting point - https://conwaylife.com/book/conway_life_book.pdf
You sent me down a rabbit hole: https://esolangs.org/wiki/APGsembly is mentioned in the book
And for a related rabbit hole where people actually went all the to the bottom, there's of course the full implementation of Tetris in GoL which was nerd-sniped by a CodeGolf challenge
https://codegolf.stackexchange.com/questions/11880/build-a-w...
Sometimes you see something that makes you wonder how it is that you get to exist in the same world as people with the drive and intelligence to do truly awesome ( in the original sense) thing like this. I am proud of myself when the compiler works on the first try.
I think it's awesome that they can do this amazing fun esoteric stuff, but at the same time a small part of me thinks maybe they need to be doing something more meaningful in the real world.
This small part is what makes broken people. Whoever reads this, go have fun! :)
You know what? I think I will.
I wonder, what would that be, that thing that is more meaningful?
I would make the case that, zoomed out far enough, nothing at all is meaningful, so you might as well make beautiful things, and this is a delightfully beautiful thing.
the only thing that's meaningful is having fun, everything else is a waste of time
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.
I think it appeals to the same itch that languages like Brainfuck scratch.
There's something exceedingly interesting about how you can model complexity with something extremely simple. Brainfuck is fun because it forces you to think extremely low level, because ultimately it is basically just a raw implementation of a Turing machine. I wouldn't want to write a big program in it, but it is fun to think about how you might express a complicated algorithm with it.
Similarly with CGOL, it is really interesting to see how far you can stretch really simple rules into something really complex.
I've written CGOL dozens of times, it's a common project that I do to "break in" a language I've learned, since it's not completely trivial but it's simple enough to not be frustrating, and I completely understand why math/computability-theory folks find it something to dedicate brain power to.
I have a weird love for Brainfuck. It's a tiny, incredibly simple language that you can write an interpreter for in an hour, it's effectively a super-simple byte code that can easily be extended and used as a compilation target for simple languages.
Honestly, as an educational tool, the only thing wrong with it is the name!
for those who think brainfuck is too pedestrian, have a browse through the esolang wiki:
https://esolangs.org/wiki/Language_list
I have no idea how I'd be able to pitch this to a university (or even who I could pitch it to), but I would absolutely love to teach a computability course using Brainfuck as the language, just to really show students how low-level logic can be.
I would probably need to find a similar language with a different name though.
You might find mlatu-6[0] interesting- it’s convertible to SKI calculus but concatenative (like Forth) rather than applicative. It’s actually a subset of Mlatu, a language I created for similar reasons to explore “how low can you go.”
[0]: https://esolangs.org/wiki/Mlatu-6
When I was an undergrad at Georgia Tech, one of my intro computer science classes had us implement something in brainfuck. Turns out college kids are quite comfortable with swear words.
Of course they are ... It's college administration that are uncomfortable
How about Assembly?
Assembly is higher level logic than brainfuck, especially on modern chips. You have built in instructions for arithmetic and conditionals/branches and you can allocate memory and point to it.
You don’t really get any of that with brainfuck. You have a theoretical tape and counters and that’s basically it.
SKI calculus is pretty neat, too. You get no tape, no counters. (But it's not quite as bad to program in as brainfuck, because you can built more ergonomic contraptions to help you along.)
SKI can, of course, be de-optimised a bit further by replacing I with SKK. You are right though that it is relatively simply to go from something that looks like a normal program languages to a pile of S and K combinators. Not the most efficient way to compute though!
Unlambda solves that problem.
"What if we had the lambda calculus without the lambda forms?" asked no one.
http://www.madore.org/~david/programs/unlambda/
StupidStackLanguage is by far my favorite:
https://esolangs.org/wiki/StupidStackLanguage
Piet is mine - the programs are 2D images: https://esolangs.org/wiki/Piet
Primarily because of the note on the "calculating pi" example program:
> Richard Mitton supplies this amazing program which calculates an approximation of pi... literally by dividing a circular area by the radius twice.
> Naturally, a more accurate value can be obtained by using a bigger program.
https://www.dangermouse.net/esoteric/piet/samples.html
One of my favorite calculations of pi is to pick random coordinates in a unit square and count how many of them are in a circle. it's so stupid and so clever at the same time.
This was recreated from memory. I think it is close but I may have a bounding bug.
With the metatopic of this thread being obscure languages, I had some fun squeezing this into some list comprehensions (maybe someone's got an idea of how to keep track of the state within the list):
```
$ cat << EOF > pi.py
state = [0, 0, 2*8, 2*12]; _ = [print(f'\rRun {state.__setitem__(0, state[0] + 1) or state[0]}/{state[3]} | Last \u03c0: {current_pi:.6f} | *Average \u03c0: {(state.__setitem__(1, state[1] + current_pi) or state[1]) / state[0]:.6f}*', end='', flush=True) for current_pi in [(4 * sum([1 for _ in range(state[2]) if __import__("random").random()*2 + __import__("random").random()*2 < 1]) / state[2]) for _ in range(state[3])]]; print()
EOF
$ time python3 pi.py
Run 4096/4096 | Last π: 3.140625 | *Average π: 3.143051*
python3 pi.py 0.41s user 0.01s system 99% cpu 0.429 total
```
Play around with the `2*8` and `2*10` values in the state, they control the amount of rounds and the range in which the random values get generated respectively.
I'm not sure about a bounding bug, but there's definitely an indent error on the return line (good old Python!)
Oh my god, that list lacks DATAFlex!
Dear Lord.
I remain utterly baffled how they made a lisp compiler with malbolge
> I've written CGOL dozens of times, it's a common project that I do to "break in" a language I've learned, since it's not completely trivial but it's simple enough to not be frustrating, and I completely understand why math/computability-theory folks find it something to dedicate brain power to.
Writing a naive CGOL is fun and quick. But writing a _fast_ one can get arbitrarily complicated.
https://en.wikipedia.org/wiki/Hashlife is one particular example of where you can go for a faster-than-naive CGOL.
Yeah, a million years ago I did that one as a convolutions so I could run it on the GPU when I was learning OpenCL. That was my first exposure to “optimizing” CGOL.
In the music world there are people who will build whole symphonies out of one sample, one filter, and one delay patch.
"So did Achilles lose his friend in war, and Homer did no injustice to his grief by writing about it in dactylic hexameters" - Tobias Wolff, Old School
Same with Your World of Text [0], still going strong.
[0] https://www.yourworldoftext.com/
if you find that fascinating then you'll be blown away by something called 'Wolfarm physics project'. it basically is trying to recreate entire physics using such baseline 'graph update' rules like 'Game of Life'. So far no predictions yet but very interesting.
Wolfram is kind of obsessed with cellular automata, even went and wrote a whole book about them titled "A New Kind of Science". The reception to it was a bit mixed. CA are Turing-complete, so yeah, you can compute anything with them, I'm just not sure that in itself leads to any greater Revealed Truths. Does make for some fun visualizations though.
A new kind of science is one of my favorite books, I read the entirety of the book during a dreadful vacation when I was 19 or 20 on an iPod touch.
It goes much beyond just cellular automata, the thousand pages or so all seem to drive down the same few points:
- "I, Stephen Wolfram, am an unprecedented genius" (not my favorite part of the book) - Simple rules lead to complexity when iterated upon - The invention of field of computation is as big and important of an invention as the field of mathematics
The last one is less explicit, but it's what I took away from it. Computation is of course part of mathematics, but it is a kind of "live" mathematics. Executable mathematics.
Super cool book and absolutely worth reading if you're into this kind of thing.
I would give the same review, without seeing any of this as a positive. NKS was bloviating, grandiose, repetitive, and shallow. The fact that Wolfram himself didn’t show that CA were Turing complete when most theoretical computer scientists would say “it’s obvious, and not that interesting” kinda disproves his whole point about him being an under appreciated genius. Shrug.
That CA in general were Turing complete is 'obvious'. What was novel is that Wolfram's employee proved something like Turing completeness for a 1d CA with two states and only three cells total in the neighbourhood.
I say something-like-Turing completeness, because it requires a very specially prepared tape to work that makes it a bit borderline. (But please look it up properly, this is all from memory.)
Having said all that, the result is a nice optimisation / upper bound on how little you need in terms of CA to get Turing completeness, but I agree that philosophically nothing much changes compared to having to use a slightly more complicated CA to get to Turing completeness.
The question really ultimately resolves to whether the universe can be quantized at all levels or whether it is analog. If it is quantized I demand my 5 minutes with god, because I would see that as proof of all of this being a simulation. My lack of belief in such a being makes me hope that it is analog.
Computation does not necessarily need to be quantized and discrete; there are fully continuous models of computation, like ODEs or continuous cellular automata.
That's true, but we already know that a bunch of stuff about the universe is quantized. The question is whether or not that holds true for everything or rather not. And all 'fully continuous models of computation' in the end rely on a representation that is a quantized approximation of an ideal. In other words: any practical implementation of such a model that does not end up being a noise generator or an oscillator and that can be used for reliable computation is - as far as I know - based on some quantized model, and then there are still the cells themselves (arguably quanta) and their location (usually on a grid, but you could use a continuous representation for that as well). Now, 23 or 52 bits (depending on the size of the float representation you use for the 'continuous' values) is a lot, but it is not actually continuous. That's an analog concept and you can't really implement that concept with a fidelity high enough on a digital computer.
You could do it on an analog computer but then you'd be into the noise very quickly.
In theory you can, but in practice this is super hard to do.
If your underlying system is linear and stable, you can pick any arbitrary precision you are interested in and compute all future behaviour to that precision on a digital computer.
Btw, quantum mechanics is both linear and stable--and even deterministic. Admittedly it's a bit of a mystery how the observed chaotic nature of eg Newtonian billard balls emerges from quantum mechanics.
'Stable' in this case means that small perturbations in the input only lead to small perturbations in the output. You can insert your favourite epsilon-delta formalisation of that concept, if you wish.
To get back to the meat of your comment:
You can simulate such a stable system 'lazily'. Ie you simulate it with any given fixed precision at first, and (only) when someone zooms in to have a closer look at a specific part, you increase the precision of the numbers in your simulation. (Thanks to the finite speed of light, you might even get away with only re-simulating that part of your system with higher fidelity. But I'm not quite sure.)
Remember those fractal explorers like Fractint that used to be all the rage: they were digital at heart---obviously---but you could zoom in arbitrarily as if they had infinite continuous precision.
> If your underlying system is linear and stable
Sure, but that 'If' isn't true for all but the simplest analog systems. Non-linearities are present in the most unexpected places and just about every system can be made to oscillate.
That's the whole reason digital won out: not because we can't make analog computers but because it is impossible to make analog computers beyond a certain level of complexity if you want deterministic behavior. Of course with LLMs we're throwing all of that gain overboard again but the basic premise still holds: if you don't quantize you drown in an accumulation of noise.
> Sure, but that 'If' isn't true for all but the simplest analog systems.
Quantum mechanics is linear and stable. Quantum mechanics is behind all systems (analog or otherwise), unless they become big enough that gravity becomes important.
> That's the whole reason digital won out: not because we can't make analog computers but because it is impossible to make analog computers beyond a certain level of complexity if you want deterministic behavior.
It's more to do with precision: analog computers have tolerances. It's easier and cheaper to get to high precision with digital computers. Digital computers are also much easier to make programmable. And in the case of analog vs digital electronic computers: digital uses less energy than analog.
Just be careful with how aligned to reality your simulation is. When you get it exactly right, it's no longer just a simulation.
"It looks designed" means nothing. It could be our ignorance at play (we have a long proven track record of being ignorant about how things work).
Yes. Or it could be an optimisation algorithm like evolution.
Or even just lots and lots of variation and some process selecting which one we focus our attention one. Compare the anthropic principle.
For all we know, it could be distinct layers all the way down to infinity. Each time you peel one, something completely different comes up. Never truly knowable. The universe has thrown more than a few hints that our obsession with precision and certainty could be seen cosmically as "silly".
In our current algorithmic-obsessed era, this is reminiscent of procedural generation (but down/up the scale of complexity, not "one man's sky" style of PG).
However, we also have a long track record of seeing the world as nails for our latest hammer. The idea of an algorithm, or even computation in general, could be in reality conceptually closer to "pointy stone tool" than "ultimate substrate".
> For all we know, it could be distinct layers all the way down to infinity. Each time you peel one, something completely different comes up. Never truly knowable. The universe has thrown more than a few hints that our obsession with precision and certainty could be seen cosmically as "silly".
That's a tempting thing to say, but quantum mechanics suggests that we don't have infinite layers at the bottom. Most thermodynamic arguments combined with quantum mechanics. See eg also https://en.wikipedia.org/wiki/Bekenstein_bound about the amount of information that can even in theory be contained in a specific volume of space time.
From the link you shared:
> the maximum amount of information that is required to perfectly describe a given physical system _down to the quantum level_
(emphasis added by me)
It looks like it makes predictions for the quantum layer and above.
--
Historically, we humans have a long proven track record of missing layers at the bottom that were unknown but now are known.
If you're interested in science fiction based on this concept, Greg Egan has a book called Permutation City which is pretty interesting.
I think I've read it or maybe a portion of it, was not very captivating. will try again.
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.
I searched several of these terms and they are all specifically jargon of game of life enthusiasts, (i.e. search reaults are all on fansites related to game of life) not general cellular automata jargon.
I assume there's fanfic shipping of automata...
(If you don't recognize that use of "shipping", don't google it at work.)
https://tvtropes.org/pmwiki/pmwiki.php/Main/Shipping should be reasonably safe for work. As long as you can avoid getting sucked in to an all-day wiki bender.
short for relationship
conwaylife.com isn't just for GOL, although it is the main subject, there is an Other Cellular Automata forum. also it's not really a fansite, it's a bit more academic than what would be considered a "fansite".
mmmh I don't think so. I've read several papers on cellular automata and I don't recognize the terms
So it starts as a line, explodes into a huge 2D complex mess, and eventually, after many generation, returns to form the same 3.7B cells long line?
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!
See here: https://conwaylife.com/forums/viewtopic.php?f=2&t=2040&start...
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
I'm barely able to follow, but this part was fun:
> 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.
> Work started in 2016 and was completed on December 1, 2025.
Almost 10 years of development.
Development, idle hacking when someone got bored at work; potato, potahto...
This kind of thing is many times more complicated and involved than my day job, I wouldn't call it "idle" if I were to do it.
Only about 1.5% of the human genome is protein coding. The human genome is about 3 billion base pairs long.
Game of life indeed!
Also share about 60 percent with bananas.
How many steps is the period? How far does it travel in that period? What direction does it go? Does it clean up after itself?
As the wiki page states, the period is 133076755768, and it moves by two cells in that time. Spaceships in GoL by definition don’t leave anything behind, they produce the exact same configuration, just shifted across the grid.
Given that it starts as a single line, it is symmetric in the axis implied by that line, and hence can’t possibly move diagonally or orthogonal to the line. Hence it moves in the direction of the line.
Thanks!
I was a bit confused by that wiki page because it says "Direction Orthogonal" but like you said that can't be.
Yeah, “orthogonal” here just means “not diagonal”. Since GoL configurations don’t have a distinguished orientation (you can rotate and/or mirror them however you like), it wouldn’t make sense to specify up/down/left/right, at least not without first fixing an (arbitrary) orientation.
Thank you for this description. I thought it's a glider for some 1 dimensional cellular automata system.
Yes, that was my first reading as well. I thought "((1D Conway's Life) glider) found" but it is "(1D (Conway's Life glider)) found".
[flagged]
> I asked AI to explain it to me,
We all know how to do that, but that's not why were here.
I’m not sure where our guidelines/norms are on this kind of thing, but I get the sense that most of us feel very capable of pasting articles into LLMs ourselves.
What we’re less capable of—and the reason we look to each other here instead—is distinguishing where the LLM’s errors or misinterpretations lie. The gross mistakes are often easy enough to spot, but the subtle misstatements get masked by its overconfidence.
Luckily for us, a lot of the same people actually doing the work on the stuff we care about tend to hang out around here. And often, they’re kind enough to duck in and share.
Thank you in any case for being upfront about it. It’s just that it’d be a shame and a real loss if the slop noise came to drown out the signal here.
dang (the head moderator of Hacker News) has said multiple times that HN prefers human-only comments.
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.
More or less like this?
https://www.youtube.com/watch?v=eMJk4y9NGvE
It’s technobabble https://youtu.be/RXJKdh1KZ0w
One of the nice things about having my spouse also working in a tech field is that we can bitch about our jobs to each other on a higher level :P
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!"
However much karma this comment scored, it's underrated
> The start is slow as well, skipping to generation 42168M is recomended.
I picture entities playing with our universe, "it starts slow but check it out at the 13.8B mark"
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?
I enjoy the [GoL -> our “reality” -> outside-the-simulation] comparison. It really drives home how unlikely we would be to understand the outside-the-simulation world.
Of course, there are other variants (see qntm's https://qntm.org/responsibility) where the simulation _is_ a simulation of the world outside. And we have GoL in GoL :-)
Always a fun read :) they turned it into a futurama episode
I think of reality as of GOL but 3D, with more states other than 0 and 1, and conservative (follows conservation laws, no relation with any politics).
Universe could be probability based GoL simulation; basic Turing machine cannot handle that
Oh my god, it's a Quine!
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.
> There has been no true replicator found yet in Life as far as I know...
Actually more than one true replicator has been constructed. The 0E0P metacell
https://conwaylife.com/wiki/0E0P_metacell
can be programmed to self-replicate in any number of ways, but it's so big that it's very hard to simulate it through a full cycle. By contrast, Pavel Grankovskiy's "DOGun SaGaQR"
https://conwaylife.com/forums/viewtopic.php?&p=138191#p13819...
only has one pattern of replication, but it's much simpler than the 0E0P metacell and can easily be run through many cycles in Golly.
OK, I didn't know if it was a "true" replicator (what even does "true" mean) so I excluded it. And, running a true replicator from other rule in 0E0P takes millenia, so that leaves DOGun SaGaQR (specifically the QR configuration). Sorry.
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.
[0] https://whatisintelligence.antikythera.org
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).
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...
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.
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.
See comments 225 and 261
https://scottaaronson.blog/?p=6244
‘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.
> it might take only one intelligent life form for the space to (eventually) get filled with it
It wouldn't need to be intelligent to do this; it could be a self-replicating machine with no intelligence at all - which is orders of magnitude simpler and therefore more likely.
Chaotic initial state -> self-replicating machine -> intelligence is much more likely than chaotic initial state -> intelligence.
(See my other reply to the GP comment about The Recursive Universe, where all this is discussed.)
What’s up with the upside down question mark?
It's an interrogative in Spanish https://en.wikipedia.org/wiki/Upside-down_question_and_excla...
Typical for Spanish speakers
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?
> Pi has been proven to contain every finite sequence
This has not been proven yet: https://math.stackexchange.com/a/216348/575868
(or more generally: https://en.wikipedia.org/wiki/Disjunctive_sequence)
Depending on the infinite grid filling scheme even these properties may not be sufficient to guarantee that every two dimensional pattern is initially generated because the grid is two-dimensional, but the number property is "one-dimensional". A spiral pattern for example may always make it line up in a way such that certain 2d patterns are never generated.
Since it's not provable with pi, then we'd have to do a more circuitous proof of every finite pattern occurring. Inspired by Champernowne's constant, I propose a Pontifier Pattern that is simple, inefficient, but provably contains every finite pattern.
Starting at the origin, mark off rows of squares. the Nth row would contain NxN^2 squares of size n x n. Each square would be filled in left to right reading order with successive binary numbers with the most significant digit at the top left.
Somewhere in that pattern is the physics simulation of you reading this comment :)
minor correction: 2^(NxN) squares per row, right?
https://news.ycombinator.com/item?id=36357466
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.
This would require patterns to emerge that are "radiation-hardened", like https://en.wikipedia.org/wiki/Quine_(computing)#Radiation-ha...
3. Could it generate it's own GoL forum asking these very questions?
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.
Is there a visualization of the glider in the thread? Would love to see how it evolves with one dimension being time.
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.
Pretty sure the GOL grid has more than one of those lines...
The best way to run it is in the software Golly. It has the HashLife algorithm needed to make it run fast enough to see it finish.
After the first step it isn't 1D any more, so I don't think that visualization is possible
It's possible. It'd just be a 3D visualization and more importantly, stupendously huge. If each cell was a cubic millimeter, the shape would be 3700km wide, and stretch 1/3rd of the way to the moon.
And if each cell was a cubic micrometer (which is a side length 200-300 times smaller than a pixel on a typical screen and 50-100 times thinner than a human hair), it'd still stretch 3.7 kilometers, which is about the length of a commercial airport runway.
I'm having trouble finding a common image file format that has > 32bit resolution fields, fit it in.
Notably it only fits within a 1 cell high bounding box during at least one of its phases, not all.
I'm not a GoLtician myself but I don't think that would be possible under the "standard" rules anyway, except the trivial case of stasis/death.
I'm really charmed by the linked thread and all the passion and work it belies. Congrats to those involved!
I found this line in the first line of the first page of this thread:
>It's still an open problem as to whether there exists a spaceship in B3/S23 which fits within a 1-by-N bounding box in one of its phases.
So they use the "typical" rule here.
Why do you think it would not be possible?
To make a new cell "live" it must be neighbored by three live cells. And in 2d, a cell only has two neighbors.
A 1d row of cells also affects nearby cells above and below the line. Consider a row of three cells:
https://parkscomputing.com/page/conways-game-of-life?boardSi...
That produces a spinner, because the empty cells above and below the 1d row have three live cells nearby.
Yes, which is not what adzm asked for.
[dead]
s/2d/1d/ right?
Oh, right.
I see what you're saying, but I think it's a misunderstanding. 1D here only means that there's some state where the active cells are confined to one row — but one row within the ordinary 2D GoL plane. I'm sure the next iteration leaps off the line immediately. Search for "Blinker" here to imagine how it could start spreading off the line.
https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
Right, but that's not what adzm was asking about.
The GP understood that.
A tiny experimental "continuous-motion" Life glider I once made - an artistic take: https://bntr.planet.ee/lj/glider.gif
this is gorgeous! really illustrates the fundemental rules in a very aesthetically pleasing way
I love it that there are people obsessed enough to spend their time on this and our society can support it.
1D spaceship*
glider is a specific spaceship, but name for "moving pattern" is spaceship
Their own wiki points out they're sometimes used interchangably.
https://conwaylife.com/wiki/Spaceship
and the source linked by that wiki https://conwaylife.com/ref/lexicon/lex_g.htm#glider claims it as misuse
it's like calling all birds a parrot
This is one of those tricky things, highly dependent on context.
If you're talking about Conway's Game of Life patterns, then "gliders" are the 5-cell spaceships that travel diagonally, and all other moving things are "spaceships" but not "gliders". If you call a Conway's Life non-glider spaceship a "glider" you'll mostly just confuse people.
But if you're talking about other CA rules -- especially rules where there isn't any 5-cell diagonal spaceship -- then "glider" is very commonly used to refer to other moving patterns.
For example, David Eppstein's "Gliders in Life-Like Cellular Automata" database was active for decades -- recording spaceships across a large rulespace, not just Conway's Life. It's an accepted generalization of the term, somewhat like saying "Xerox machine" for any old copying machine whether or not it was built by Xerox.
Misue is still use, that's why the source adds the parenthetical to the mis in (mis)use. It's a novel field we can name things whatever we want.
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.
Can someone please ELI5 what this means? Thanks in advance.
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:
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...
As noted by others, the title is mistaken; this is a spaceship, not a glider. (As explained in the Wikipedia article, "glider" refers to a specific 5-cell pattern discovered very early on.)
> So finally 2/133076755768 ship of starting bounding box 3707300605x1 is here
My understanding is that 2/133076755768 is the speed, in (number of cells translated) / (number of generations to repeat).
spaceship*
glider is one specific spaceship, but name for moving patterns is spaceship
I knew what a glider was,
what I am personally still wondering is,
what is significant about making such a peculiar shape?
I find it difficult to believe that making a recurrent structure that translates in the grid (my lay language of doing what a glider does) requires a preposterously long structure like this,
so my guess was, is the excitement that someone made something extremely long, and there is some kind of race to make bigger and bigger structures with this behavior, akin crudely to the race to compute digits of Pi?
Or is it rather that no one has described a structure which "glides," with this preposterous number of cycles... which I would guess is coupled to the size?
Or is it rather that no one has described a 1D structure which "glides," at all...?
I would think that if what's desired is to find novel larger-scale structures, the best approach today would be to just fuzz noise of all kinds in large windows, let them iterate, and put the energy into the ML which evaluates the evolution of the world to categorize the results...
Thank you ^_^
This video is a great overview of spaceships\gliders: https://www.youtube.com/watch?v=5yLcsaewxJQ
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.
Anyone have a recording of what this thing looks like? I'm very curious to see it and didn't see any obvious links in the thread.
My understanding is that, it is so large and takes so long to run, there is really no way to visualize it
Golly with hashlife algorithm is quite amazing. You can simulate and visualize quite a bit of it.
Summary: In the end I was able to go through full period with the memory limit set to 35GB of memory. Most of the time all the action happens in 1+3x2 straight lines with different angles no more than 100 cells wide each. There were multiple distinct phases. Some one could definitely make an interesting visualization zooming in one the distinct regions at different stages of progression. General shape is horizontal line, <- shaped arrow, arrow with kite head, arrow with 2 nested kites, 2 giant nested kites, kite, arrow, horizontal line.
At first I was able to simulate first 15*10^9 generations quite quickly. And you could see some of initial stages. During first 2e9 generations it was using only 500MB of memory, somewhere between 2e9-4e9 it started to slow down. After bumping the memory it limit to 16G it was able to spedup again until ~15e9.
Initially it looks like 3 strings xxx. First one the shortest, second slightly longer and third even longer. Pattern xxx oscilates between horizontal and vertical giving stable form to store information.
Shortest string starts to get consumed from right to left.At some point it emits 2 gliders diagonally to the up/left and down left. After a while there are 2 vertical spaceships which collide with 2 diagonal gliders. After a bit more it starts to emit stream of gliders to the up right direction with overall shape being like arrow. At the back of arrows the gliders start to build a structure for next stage. The constructed structure starts creating bigger stream in the up right direction which in turn starts emiting stream down right back to the horizontal line. Once it meets original line it creates a new line towards first diagonal at more gradual angle. Thus an arrow like shape with tip consisting of 2 nested kites keeps expanding and consuming the line of oscilating xxx. By the generation 2e9 it has processed first 2 smallest of 3 sequences. At ~30e9 it reaches end of third line and inner kite starts to disappear outer kite keeps expanding. 37e9 Inner kite has fully disappeared.
At this point I further bumped RAM so that I can inspect zoomed in look at 1x speed. Now and probably previously what looked like sharp tip of arrow actually is more complicated machinery receiving in stream of gliders processing them and then emitting towards front in a way that reconstructs line of xxx. I am guessing at this point it is reconstructing initial line of xxx.
At ~44e9 first segment of line was reconstructed and machinery started to get torn down? It started to rebuild something near the outer edge of arrow front. And shortly creates new stream of spaceships along the outside of arrow. Most of the time structure consisted of 7+2 similar parallel streams. Some slowdown at ~66e9 probably transition to new phase. Front of kite detaches from central line, outer corner of kite also starts to tear separate and tear down. 88e9 back of kite has fully disappeared leaving only arrow. 95e9 central line start to shrink shorter. 105e9 central line has returned to sequence of xxx. The sides of arrow are still there. 117e9 sides arrow break in half and erase from middle. 133e9 back to single line and start from beginning.
There is of course a way to visualize it, but it would be more boring than a Tommy Wiseau film... with a less reasonable plot.
Hah, and a forum bug further down in the thread:
> Seems there is a bug in the forum, when more people write a post at the same time the post sometimes vanishes.
phpBB which they use for forum is littered with bugs and security vulnerabilities. This one is clearly a race condition, not unheard of.
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.
I'm beginning to think a FORTH coded in GOL is within our reach.
Would you be satisfied with a Lisp implementation?
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
Are there any screenshots or a video of some interesting parts or behaviors of the glider?
I'm on a smartphone, I'd like to look at the end result.
For software, use Golly, it has HashLife (pretty fast algorithm), can open many types of files, and supports scripting.
“History Doesn't Repeat Itself, but It Often Rhymes” – Mark Twain
Looking forward to the impending AI and crypto crash and have people run GoL simulations on expensive computer systems like it's 1972 again.
Off-topic, but like a lot of quotes attributed to Twain, there’s no evidence he said that.
https://quoteinvestigator.com/2014/01/12/history-rhymes/
As Mark Twain also said, "A lie can travel halfway around the world before the truth can get its boots on."
Of course he didn't say that one either: https://quoteinvestigator.com/2014/07/13/truth/
But he did call Mae West "my little chickadee", right?
I'm pretty sure Mark Twain wasn't around to say anything about internet exchanges.
What does 1D mean here? It's a single row of length 3.7b?
Yes. It lives in a standard 2D grid, but it starts on a single line.
What are the rules in 1d ?
It only starts out 1-dimensionally, it continues to evolve on a standard GoL grid.
Then, importantly, it collapses itself back down to a 1-dimensional copy of its starting representation, but translated.
Specifically, after 133_076_755_768 steps, the 1-dimensional pattern reoccurs translated by two pixels. On skimming the thread I haven't determined if that shift is parallel or perpendicular to the line.
I think it has to be parallel by symmetry.
Can it leave other bits behind after it moves?
By definition of a pure spaceship / glider, no it can't. If it emits persistent "exhaust" that's a "smoking ship"[0].
[0] https://conwaylife.com/wiki/Types_of_spaceships#Smoking_ship
IIUC, "smoke" is ephemeral by definition. A spaceship/glider that leaves persistent "debris" in its wake is called a "puffer":
https://conwaylife.com/wiki/puffer
Smoke refers to fairly long lived debris that eventually dies out, the term for one that leaves permanent debris is a puffer.
No, if it does it's called a puffer.
This seems like a great task as a test for AI.
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.
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
[0] https://www.scimagojr.com/shapeofscience/
“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.
You can change "might not" to "have not".
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.
Turing completeness relies on infinite state.
With finite state, one could theoretically brute force search every possible 1D sequence to find a glider shorter than the one discovered here.
Obviously that's impractical, but turns the whole thing into a search problem - find the best/a good solution in a huge search space.
This is specifically a task that LLMs would be utterly useless at. Because they can't execute loops.
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.
well...
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 [...]"
Adam P. Goucher's pi-calculator pattern is quite elegant, I'd say. It prints the decimal digits in-universe, with Conway's Life blocks for pixels.
https://conwaylife.com/wiki/Pi_calculator
yes you are right the question was ambiguous. WHat I was really looking for is if there is a way to physically derive PI out of some basic cellular automata operations. that does not necessarily have to involve circles etc. much less so about representing digits of PI itself. just that an pattern that evolves into ever more accurate values of pi (or a quantity derived from pi). this definitly must not be encoded or somehow preprogrammed into the GoL's initial condition. In fact I dont even care if the evolution rules of standard GoL are followed. just that SOME set of rules automatically produce PI-derivative.
the reason it would be cool is because then we've taken a most fundamental geometric constant and derived it from purely graph update type of mechanics. if you could do that then likely you can do a whole set of other things like physical laws.
Is there a video clip of the simulation anywhere? Would be interested to see it
RIP John Conway, a victim of Covid.
Wow this seems very interesting! Can we get a TLDR of how this was achieved?
While I understand very little of it, it is still very enjoyable to read the details further in the thread at https://conwaylife.com/forums/viewtopic.php?&p=222136#p22221...
>>>
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.
If the first Star Trek episodes were written today, they could have very well used GoL terminology as technobabble. The depth of the GoL community lingo always amazes me, as an outsider
[dead]
[flagged]
Pasting AI garbage you don't understand is worse than useless.
If it's garbage, it's reposting garbage. A huge percentage of posts are garbage anyway, whether because they are mere opinions, or because they are overconfident guesses from Internet Experts(TM).
If it's not garbage, it shines a light into the workings without each of us having to understand what's going on.
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.
I would like to see a video.
If each step was 1 frame, and the video played at 240 frames per second, the video would last about 17.5 years
[dead]
Since the video screen would be larger than 1 Bpxl wide, I would accept a FHD scaled-out video.
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.
They found the mothership!
1D? One dimensional? So it‘s just an unfathomably long line?
In which direction does it glide?
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.
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.
It is constructed by using modules with known behaviour. And some brute force.
How on earth did they find this? It's akin to creating a genome out of thin air and expecting a living creature to pop out at the other end.
It's engineered, not natural/random.