Building arbitrary Life patterns in 15 gliders
btm.qva.mybluehost.me
btm.qva.mybluehost.me
My hope is that by reading only the amount of background on the blog already in the Waterbear post (referenced immediately in the introduction), you have all you need to grok the post. But that's certainly an optimistic hope, and maybe unfounded.
I have read quite a bit about GoL before over the years, programmed and experimented with it and many variants etc But never tried to build a.. well, it's high level programming in GoL isn't it, or like building UNIX tools in GoL and doing cool things with complex combinations of them. I had my mouth open in amazement reading it. Bunch of maniacs. This is an extreme sport. Thank you!
Advanced gol is just getting past that first hurdle of understanding the densely compressed info behind the jargon. And it doesn't ever need to be done for all of the concepts. You can be versed in just one. I started out in a super specialized corner in self constructing spaceships. That said I'm a bit of a whiz in other areas so I can't be used as evidence that it works for everyone..
Probably I'm a good case in point. I'm definitely not a particularly clever mathematician, but it seems like it's possible to understand any new Life technology just by tinkering with the pieces for long enough.
If anyone wants to follow along with that kind of learning process, just start working through the Life textbook that kryptiskt mentioned. (Full disclosure, I'm one of the authors.)
Even though in my life, I can't make the time for doing something on the grandiose scale required, I can live vicariously through reading about your sheer dedication and intellectual effort expended.
RCT is basically one very unreasonable end of a wide spectrum: you can use a very small number of gliders to build something, as long as you're content to have the construction take a ridiculously long time. Conversely, you can build that same thing in a lot less time, but it will take a lot more gliders.
The glider positions might very well require more storage than the desired pattern itself.
But the number that says how far apart those corners are from each other has very roughly half a million digits. The exact number depends on exactly what pattern is being encoded by the RCT pattern -- I think the example construction of Alan Hensel's decimal counter pattern needs somewhere around a 450,000-digit number.
There are some optimizations underway to decrease that number by a few percentage points, but it's always going to be a very big number!
The pattern it generates are pretty amazing as you can see here: https://youtu.be/0Kx4Y9TVMGg
(I have to say the presentation style of the video gets on my nerves a bit though, especially the "typing on a keyboard" sound effect. But hey, if it helps them reach a wider audience)
EDIT: why didn't you also link the original website of Jeffery Ventrella though?
Clearly, number of gliders is no longer a good measure of complexity of constructions. Perhaps one should fix a straightforward way to encode a set of gliders by position (e.g. using [1]) and orientation and take the minimum number of bits of such a description.
Just one question:
> 1274729 – build a DBCA and pass control to it
> 192584 – build a new constructor that reads stored data instead of live data
> The final 200093 bits get stored in the Binary Storage and Retrieval device, these same 200093 bits are counted below:
How come this adds up to 1667406, which is 1615 more than the claimed total of 1665791 bits?
I can verify this later.
I'm no expert here but some basic ideas are that some small number of gliders (two?) can hit each other and produce a "glider gun", allowing for just a few gliders to "upgrade" to producing a steady stream of gliders. There's a "Reverse Caber Tosser" (RCT) structure which has a stationary element that "tosses" a glider back and forth with a structure moving away (or towards?) it, emitting another glider in another direction after each toss, allowing for logarithmic glider/population growth. Another key idea looks to be the "glider producing switch engine" (GPSE) which incorporates the ideas of the RCT with a delay and some other logic?
The distances involved are astronomical because they're encoding everything in the distance but they still manage to make it Turing machine equivalent with only 15 gliders.
Anyway, I'm floored at the ingenuity of the GoL community. It's as close to programming with butterflies as I've ever seen [0].
4 gliders hit each other to make a stream of gliders. This isn't a gun, because a gun costs more. instead it's a GPSE, which looks like a gun from the barrel end, but has a limit. As it approaches that limit, the RCT mechanism lets another three GPSEs generate an arbitrary list of bits, controlled by the precise location of the first (as a binary number). The final count 15 comes from the naive 4×4 minus one from being able to piggyback one of the constructions off a neighbor to save a single glider.
From bits to an embedded turing machine is gol magic that the blog post treats better than my comment could.
The difference is that where the real world doesn't allow for storing anywhere near that level of precision in a mark on a stick, the Conway's Life universe is considered to be unbounded, so there's as much room as we need to implement this RCT trick.
¹ directly?
² amount of activity? mass?
The idea that all neighbors move to the next tick simultaneously is a fundamental assumption in cellular automata in general. If you try changing that, the optimizations that allow us to simulate CAs at any kind of reasonable speed ... all stop working, pretty much. It's kind of painful even to think about.
Which means there are probably very interesting rules out there somewhere, where CAs run faster/slower depending on pattern density -- it's just going to be very tricky to explore that particular search space.
(A Doppler effect does show up in Conway's Life sometimes, but that's about as far as we get with analogies to the physical universe...!)
Quantum discord: https://en.wikipedia.org/wiki/Quantum_discord :
> In quantum information theory, quantum discord is a measure of nonclassical correlations between two subsystems of a quantum system. It includes correlations that are due to quantum physical effects but do not necessarily involve quantum entanglement.
From "Convolution Is Fancy Multiplication" https://news.ycombinator.com/item?id=25194658 :
> FWIW, (bounded) Conway's Game of Life can be efficiently implemented as a convolution of the board state: https://gist.github.com/mikelane/89c580b7764f04cf73b32bf4e94...
Conway's Game is a 2D convolution; without complex phase or constructive superposition.
Convolution theorem: https://en.wikipedia.org/wiki/Convolution_theorem :
> In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution of two functions (or signals) is the pointwise product of their Fourier transforms. More generally, convolution in one domain (e.g., time domain) equals point-wise multiplication in the other domain (e.g., frequency domain). Other versions of the convolution theorem are applicable to various Fourier-related transforms.
From Quantum Fourier transform: https://en.wikipedia.org/wiki/Quantum_Fourier_transform :
> The quantum Fourier transform can be performed efficiently on a quantum computer with a decomposition into the product of simpler unitary matrices. The discrete Fourier transform on 2^{n} amplitudes can be implemented as a quantum circuit consisting of only O(n^2) Hadamard gates and controlled phase shift gates, where n is the number of qubits.[2] This can be compared with the classical discrete Fourier transform, which takes O(n*(2^n)) gates (where n is the number of bits), which is exponentially more than O(n^2).
If not on an infinite grid, then some subset (i.e. 100% of 1x1 patterns are build-able, 80% of 3x3 patterns, 60% of 5x5 patterns, etc.)
If we limit ourselves to glider interactions, the article links to the following patterns which cannot be constructed (including garden of eden patterns): https://conwaylife.com/wiki/Category:Patterns_that_can_not_b...
If the GoL wizards can construct an expanding and initially configurable 'GoL in GoL' grid [1], they could configure the 'garden of eden' as the initial configuration for their 'GoL in GoL' simulation.
It's not the same thing, of course, but it would allow you to run Garden of Eden patterns still starting with just your initial 15 gliders.
To construct a garden of eden pattern, you must first construct the universe :)
[1] similar to https://www.youtube.com/watch?v=xP5-iIeKXE8
We already have GoL turing machines (with "tape factories" that travel faster than the read/write head); we could likewise use those to emulate GoL with arbitrary input, just by setting up an appropriate "tape". The result is far less pretty though ;)
I touched on this in a sibling comment: https://news.ycombinator.com/item?id=33799084
Or are these "discoveries" being done by hand?
On the other hand the smallest known orphan is 12 by 8, and we also know that all still lifes (unchanging patterns) with up to 21 cells can be built.
https://catagolue.appspot.com/census/b3s23/synthesis-costs/x...
On the other hand, pseudo-still-life and quasi-still-life arrangements are much easier to construct on average than strict still lifes with the same number of cells.
I think the consensus is that someone could figure out how to construct any given stable 21-bit configuration. The non-strict cases are just a bit too numerous and not interesting enough, so nobody has gone through and formally checked them off the list.
* Is there an oscillator of every possible period? (We have them all except 19 and 41.)
* If you start off the entire plane in a random starting state, does its density tend to a limit as time goes to infinity?
* Is there a 'phoenix' oscillator, in which every live cell dies every generation, of period greater than 2?
* Can every pattern be destroyed by bombarding it with gliders?
* Is there an indestructible pattern?
At the moment people are working on building a spaceship which is only 1 cell tall in its starting state: https://conwaylife.com/forums/viewtopic.php?f=2&t=2040.
(... and encounter other AIs that act as hegemonising swarms, eg. that populate the plane with copies of themselves)
What's been done with GoL is fascinating, but I think the next emergent layer of fascination for me is universal constructors which can handle a certain level of constant distributed noise or interference. A lot of times people just shrug and say, "well this pattern will always be critical/vulnerable in these locations, and cannot be made robust. But to me that opens up the door for entire classes of patterns which measure, embed and repair state of surrounding entities.
Conway's Life design work is kind of like building robots out of masses of subcritical uranium. Everything's fine until two robots unexpectedly bump into each other... which means you have to start out with everything very carefully balanced, such that that never happens.
So I guess one fairly obvious insight is that real-world physics supports more reliable and less explosive low-level structures than Conway's Life does, and those low-level structures can then safely be used as the basis for new levels of organization -- atoms -> molecules -> DNA -> bacteria -> eukaryotic cells -> multicellular organisms -> colonies of organisms -> ecosystems.
It's not clear how those higher levels of organization would work in Conway's Life. If they're possible, then they seem to be far beyond our current ability to simulate them -- though there's some recent research vaguely along these lines, about self-replicators that might be able to exert some control over the space around them:
"Interesting", they might say. Or, "Fascinating!" even.
And then you show them this article. Just imagine how mind blowing it would be to them.
Original SciAm article -> https://www.ibiblio.org/lifepatterns/october1970.html
Ever since 2001 I've been keeping a close eye on new developments so I don't get surprised like that again.
Below that we'd need some significantly different mechanism that nobody has thought of yet. It doesn't seem likely that anyone will be able to prove that universal construction is impossible with a single-digit number of gliders -- but if a solution exists it might take an omniscient being to find it.
... Or maybe some clever hacker will figure it out tomorrow! That's what happened to get us to the current minimum. We were stuck at a minimum of 32 for quite a while, until Daniel Vargas (MathAndCode) suddenly showed up with a new idea.
Bonus question: can this string be "folded" so that it occupies a radius of O(sqrt(N))?
(now we have a close analogue of DNA! It's fascinating that indicates the universality of DNA and life -- we seem to be somewhat limited universal constructors)
Other questions: are there "Constructor classes" -- non-universal constructors specialized in building a certain "chemistry", a useful subset of all structures? What is the minimum (restricted) efficient contructor capable of building (a) A copy of itself; (b) A Turing machines; (c) Turing machine and construction tapes.
Also I've been thinking about reliability. Is there a constructor that can tolerate a flip ("error") anywhere inside? That can tolerate any single glider collision? Or can tolerate "most" bit flips? An interesting difference between CGoL and our universe is that we live in a thermal and quantum bath. So in a sense (that's up to QM metaphysics) there is inherent randomness in particles, and of course all particles chaotically "wiggle" at positive temperatures (it might be argued CGoL also has wiggle, but in CGoL you can have non-chaotic, periodic large systems -- it's essentially easy to have 0 temperature systems).
I've been playing with simulation of CGoL that have a proportion of random flips each generation. I've been investigating whether interesting structures come out of the "soup" -- this is more interesting, I believe, that just starting from a soup and seeing if something survives (in a deterministic universe), because you can have "multi-step evolution": maybe some small structure comes up, and then random perturbations slowly make more interesting structures emerge -- in a faint analogue to the origin of life, or just faint analogues of chemistry/proto-evolution -- the population of patterns evolves with time. It would be really cool to have a crowdsourced set of long-time simulations of such a field.
Another important open problem related is how to define a 'Life detector' (in Life). A Life detector is an algorithms that given a pattern and a few generations, tells you how complex, interesting, and 'alive' that pattern is. Very fun and significant problem I believe. Together, this means we can run massive crowdsourced searches to understand environments that tend to evolve interesting patterns (although of course anything close to a bona fide lifeform is probably still far out of reach of our computing power, and might benefit from other kinds of analysis)..
However, von Neumann's design uses a cellular-automaton with many more rules, and those were specifically chosen to help define that constructor (Langton Loops are a more extreme example of choosing rules to make construction easier). In constrast, the rules for Game of Life (GoL) were chosen to be simple and interesting, not fine-tuned for any particular patterns (for an even simpler set of rules, see the Rule 110 cellular-automaton).
We know the GoL is Turing-complete, so it can emulate any computable system; including those other cellular-automata, e.g. von Neumann's universal constructor. Such emulations will typically use a large GoL pattern to represent each emulated cell (e.g. see "life in life"): if we emulate a universal constructor, we can use it to assemble any pattern of those emulated cells. We could also emulate GoL inside some other cellular-automaton, and hence use a universal constructor to assemble any pattern of emulated GoL cells. But the question still remains: can we assemble any pattern of "native" GoL cells? That's what the constructors in the article are doing (at least, for a broad class of patterns).
The rest is a matter of "code golf", trying to make the patterns smaller and faster (and indeed feasible to run on a real PC!)
https://en.wikipedia.org/wiki/Von_Neumann_universal_construc...
https://en.wikipedia.org/wiki/Langton%27s_loops
https://en.wikipedia.org/wiki/Rule_110
Equally, compression, is this an avenue worth exploring and a whole new way of doing things awaiting to be tapped?
The Life pattern that most evokes DNA and self-replication is another megapattern from several years ago, the 0E0P metacell, which even has a visible "nucleus" for its "DNA":
https://conwaylife.com/wiki/0E0P_metacell* Download Golly https://golly.sourceforge.net/ and play around drawing random patterns. Have a look at the example patterns.
* Have a look around on the LifeWiki https://conwaylife.com/wiki/Main_Page. Click anything that looks interesting.
* Read the free online book https://conwaylife.com/book/
* Make an account on the forums https://conwaylife.com/forums/, or just lurk and see what people are talking about.
* Hang out on the Discord https://discord.gg/uA6uaGv3
Nevertheless, it’s a fantastic example of how simple rules can give rise to complex systems.
The RCT design is very much a mathematical construct, as opposed to anything with a biological inspiration. And the RCT's ability to construct itself is more of a theoretical afterthought at this point -- the engineering work hasn't been done yet to produce a demo of that kind of thing.
The point is well taken, about the fragility of Conway's Life with respect to environmental noise. That topic has also come up here and there in these comments, e.g., https://news.ycombinator.com/item?id=33797799#33800301
Edit: thanks you people for the explanation, makes sense. Nice hack to make it feasible.
The middle of the RCT pattern where all of the action happens, reads its first bit 2^N generations B.S (before singularity, or before splat, whichever you prefer). Next bit is 2^(N-1) B.S. Next would be 2^(N-2), but this is what the semilator changes.
During the franky enormous gap between 2^(N-1) and 2^(N-2) generations B.S, extra spaceships come in at an orthogonal direction. These have two possible configurations, giving equivalent results to either of the possible bit reads. This accelerates the speed of bit reading, and means that N of millions can be emulated by a pattern with N less than 30. Much less initial distance, much less time. The addition of millions of cells of spaceships doesn't make the overall pattern smaller in an informational sense, just in the scale of time and distance between its constituent parts.
But the 'recipe' contains 1665791 bits, meaning the signal has to bounce back-and-forth 1665791 times. Because the distance to the GPSE halves every time, it would have to start at a distance of 2^1665791, which is impractically large.
So instead we only have it bounce back-and-forth a small number of times (26), and insert the other 1665765 bits 'manually' by adding streams of 1665765 spaceships that collide near the construction site.
I would find it interesting trying to formalize notions that we easily perceive into computer-understood definitions.
May end up with strange formalizations to make things as orthogonal as possible: IE a beehive is a glider speed zero.
Hypothesis: if the interaction of any pair of oscillators can theoretically be represented by a single oscillator, this could also be possible with 4 and 6 (larger) gliders, simply because (4 over 2) = 6, (6 over 2) = 15.
The above may only hold in a continuous-valued GoL, or it may not hold at all.
"Some patterns require a very large number (sometimes hundreds) of glider collisions"
At that time Andrew Wade had already created the self-constructing Gemini spaceship, which needed 173449 gliders to build ( https://conwaylife.com/wiki/Glider_synthesis#Spaceship_synth... ). The recipe could have been reworked to be a little cheaper, but nobody bothered at the time -- and now it can be done in fifteen gliders instead.
If you want to see the construction happening, I'd definitely recommend the old Gemini recipe over an RCT-based one, though! RCT cuts down the cost in gliders to a minimum, but at a terrible cost in the time you have to wait around to see the completed object.
Gliders are generally considered to be the "lowest common denominator", though, so adding complexity by allowing more types of spaceships isn't usually seen as an improvement.
... It also becomes possible to cheat: I suspect we could put together something like an "RCT8" if we allowed Corderships as well as gliders in the list of allowed moving objects that we start with. (2-engine Corderships' "engines" are switch engines, and we have to build four switch engines to get the RCT reaction started. Could probably just shoot down the extra switch engine with one glider, and go from there.)
At 1:57 it even looks like someone draws a line casually with a mouse.