dvgrn

The relatively-big, relatively-new thing at the moment is the application of SAT solvers to CGoL problems. Donald Knuth got the ball rolling on this, but we're still in the very early days of seeing what is possible with SAT solvers.

Every now and then a lucky or inspired SAT solver problem setup will throw out an answer to a really difficult-looking problem, with no apparent effort. But then that tends to tempt people into setting up more difficult problems to solve... and of course it's still very easy to set up problems that cover such a large search space that the search would take billions of years to complete on a planet-sized supercomputer.

So it's still very much an art form, rather than an exact science, to figure out what searches to try next.

Langton's Ant is one of many, many CA rules that run for a while, seeming to be "predictably unpredictable" -- creating lots of blobby chaos -- but then produce a highly recognizable emergent phenomenon (the final "highway", in this case).

For music generation you'd want to somehow avoid ending up with the music "going boring" when the highway appears... As with a lot of math-inspired art (I guess I'm thinking about Mandelbrot-set colorizations here) the key is going to be in very specific presentation choices -- color choices for still frames or videos, or the specific method of mapping sounds to frames in a Langton's Ant evolution. So you'll just need to have (or develop) tools to try a lot of options and see what looks the most compelling.

Still frames are probably not going to be that interesting -- the fun part about CAs is the predictable-yet-surprising motion, which can be either the usual visual form or converted to sound somehow.

A recent version of Golly ( https://golly.sourceforge.io ) added support for listening to evolving patterns -- see pop-sounds.py / pop-sounds.lua in the Scripts directory. That reduces patterns to a single dimension in an obvious way (just looking at population), ignoring a lot of the 2D complexity. No doubt there are a lot of other possible avenues to explore there.

It's going to have to be the opposite of trial and error, I would think -- though maybe in some sense some of the underlying searches for useful predecessors of patterns like Sir Robin could count as "directed super-high-speed trial and error".

The problem at the moment is that nobody can see how to direct those searches toward a predecessor that's made entirely out of gliders -- it's clear that the Sun will burn out long before a trial-and-error search would be at all likely to return a result.

We can easily make a huge number of non-Sir-Robin predecessor patterns that will evolve into Sir Robin -- and we can find ancestor patterns for most of those predecessors, too -- but each step backward always produces something that's a little bigger, a little blobbier, and a little more random and chaotic looking than Sir Robin was... so ultimately all we're doing is making the problem more difficult with each step.

Heh, well, I'm speaking as somebody who was fairly obsessed with making Rube Goldberg domino chains as a kid, spending hours at a time covering a large oak trestle table with precarious stacks of wooden blocks, rulers, tape cases, strings, marbles and so on -- and then knocking them all down. (This was long before YouTube, so I don't have any documentation of any of this.)

I would really have appreciated an "Undo" button for rewinding entropy and running those things over again, especially when they went disappointingly wrong halfway through...!

I've never had a good short answer to this kind of question. It's much more of a twenty-page essay question, with a lot of subtleties to dive into. I've tangentially crossed paths with Stephen Wolfram off and on for a bit over a decade now, starting with attending a Wolfram Summer School session --

  https://education.wolfram.com/summer-school/alumni/2011/

-- and every few years someone from Wolfram Research will show up for an email discussion about one interesting topic or another. I'm more of a "determined hobbyist" than a proper theorist along the lines of Ed Fredkin, though, so while I'll enthusiastically agree that _A New Kind of Science_ documents a whole lot of fascinating stuff... I might not be the best judge of whether it all adds up to something that should be called "revolutionary".

(I'm quite sure that I don't do anything "revolutionary" myself -- I just try to encourage Conway's Life research to continue. Discoveries have kept building on previous discoveries for fifty years now, and I'm just really curious to see what will happen next.)

I did a bit of homework before posting this, and there were just enough Hacker News hits on "AMA" (from Sam Altman, Peter Roberts, etc.) that it didn't look like there would be any harm in trying this experiment.

I could certainly try an "Ask HN" at some point, but haven't been able to think exactly what question I would ask. "How many people know what a reverse caber tosser is?" is one that I'm curious about, but I suspect I'd get mostly just crickets. Really I wanted other people to ask questions... and I'm having lots of fun with the results so far!

I'd say there's no shortage of demonstrations of complexity emerging from the iteration of simple rules -- fractals like the Mandelbrot set, simple edge-matching rules for aperiodic tilings, the logistic map, etc., etc.

What makes Conway's Life particularly "catchy" (along with other 2D CAs) seems to be the motion. Humans love watching stuff move, especially when the motion is partly predictable and partly surprising -- i.e., like a screen-saver, not like TV static. And they like watching things blow up. A lot of Lifenthusiasts probably got their start by aiming gliders at carefully balanced Life patterns and gleefully watching the resulting explosions... it's a lot more fun than actually blowing things up, because you can always hit Undo and run it all over again, no harm done!

I think SmoothLife and Lenia are great fun -- lots of highly watchable "eye candy" tends to get produced by those types of experiments. The better you get at running experiments, the more new behavior you can turn up:

  https://www.youtube.com/c/Slackermanz

There's a channel on the ConwayLife Lounge on Discord called "#exotic-ca" that's devoted to these kinds of explorations. I just simply haven't had time to dig into those topics much, but if I could clone myself I'd definitely assign one copy to playing around with that kind of thing.

There have been a lot of "wow" moments in my Life career, watching complexity emerge out of the repeated application of simple rules -- but I guess I'd say that it was more a confirmation of things that I thought I knew already.

In 2001 I had already been playing around with things like the Mandelbrot set and aperiodic tilings and Douglas Hofstadter's strange loops for quite a few years, so I knew the kinds of magical things that the iterative application of simple rules could produce.

"Soup searching" generally means not looking for anything in particular. It just involves setting up a random initial configuration, letting it run until it stabilises ("goes boring") and then takes a census of what's sitting around in the ashes of the burned-out pattern.

Mostly, of course, the census just reports piles and piles of blinkers and blocks and beehives and boats and everything else that you almost always see when you run a random scribble -- but every now and then something turns up that has never ever been seen in the history of Life, and that turns out to be useful and building new mechanisms that weren't possible before:

  https://mathematrec.wordpress.com/2016/07/05/richs-p16/
  https://conwaylife.com/wiki/Rich%27s_p16

Yup, the Quest for Tetris project caused an entertaining stir for a while. The people that worked on that were the best kind of "hacker" -- fearless experimenters who didn't let their lack of Life-specific knowledge get in the way of cobbling together an amazing structure that fit the bill for simulating Tetris.

The project has at least one unnecessary extra layer of abstraction in it, but somehow nobody has quite gotten around to rebuilding it 100x smaller. A "HashLife-friendly" version could run thousands of times more quickly in Golly.

Since then, several people have invented their own independent computer architectures in Conway's Life, so that kind of experimentation is still going on. See, e.g.,

  https://conwaylife.com/wiki/8-bit_programmable_computer

A really impressive number of discoveries have been made since 2001 -- there's been kind of a proliferation of new sub-fields, so it seems like there's never any shortage of things for newcomers to work on.

There are definitely areas that haven't really been explored fully yet, like the use of SAT solvers in new and inventive ways to tackle difficult Life problems that are currently just beyond our reach.

Just for example, there's the problem of finding a fast elbow for a 2c/3 "signal wire" --

  https://conwaylife.com/wiki/Wire#2c/3_wire

It's not clear if SAT solvers can be applied usefully to glider synthesis questions, like "is it possible to collide gliders to build a Sir Robin spaceship?" At the moment that particular question seems way beyond reach, but maybe in a few years we'll be running an AI that is experimentally setting up new SAT solver problems, and something will pop up that we just haven't managed to think of yet.

Question 2: Wikipedia's articles tend to be very good quality -- partly because if they weren't, there are a lot of Lifenthusiasts with some experience maintaining the LifeWiki who would immediately go and fix any technical errors that might show up on Wikipedia. But the really detailed documentation on Life is definitely kept in the LifeWiki, not on Wikipedia:

  https://conwaylife.com/wiki/

Yup, there's an increasing amount of GPU use these days, mostly related to soup searching -- see https://catagolue.hatsya.com/home for the software and a tabulation of results from the last several years of collaborative searching.

Caching is very very heavily used for running the biggest universes, which are truly mind-bendingly large. Golly's "HashLife" algorithm can in practice handle patterns that are over a trillion cells in each dimension:

  https://conwaylife.com/forums/viewtopic.php?&p=153609#p153609

Patterns with interesting behavior very often have a lot of repeating patterns, with the interesting stuff happening as complex interactions between those predictable patterns. HashLife capitalizes on remembering interactions that it has seen before, so basically the more memory your computer has available, the better HashLife will do in the long run at simulating that type of pattern.

Yes, please -- I'd like to hear more about that! I've got the poem memorized, but mostly what I know about it is that Carroll thought of the last line first --

"For the Snark _was_ a Boojum, you see."

and ended up writing the other umpteen dozen verses just so that that would make sense as a punch line.

Not quite, unfortunately! I almost had the opportunity, briefly, in 2019 when I was contributing some patterns to a short film that Will Cavendish was working on with Conway, called "Thoughts on Life":

  https://www.thoughtsonlifefilm.com/

But there was never really a good excuse to arrange a meeting, given Conway's very fragile health at that point -- and then COVID came along.

Conway regularly attended the bi-annual Gatherings for Gardner in Atlanta for quite a while, but by the time I started attending he could no longer travel that far.

If a glider shows up somewhere by accident, like in an an otherwise random-looking arrangement of floor or wall tiles in a bathroom or somewhere, then I'll certainly pick it out immediately (and be unwarrantedly cheerful for the next half hour or so). But that doesn't happen all that often.

It seems like I rarely have dreams about Life patterns, though it does happen. Maybe some people with better-resolution imaginations might have a different experience, but Life patterns need a lot of precision and focus, and in my dreams everything is always fluid and shifting and I can never find my car keys or my homework, let alone any interesting Life configurations.

These days, without knowing more about preferred programming language or the purpose of the implementation, I'd probably start by pointing to this very thorough series of blog posts by Eric Lippert, from LifeWiki/Tutorials:

  https://conwaylife.com/wiki/Tutorials/Coding_Life_simulators

Life simulators have been coded in so many different ways, in so many languages, by so many different people in the last half-century ... that it takes several dozen articles to work through a reasonable survey of the possible ideas and methods.

Heh, I think I can find answers for "surprising" a lot more easily than for "useful". The main practical use for Conway's Life is as a teaching tool, giving a nice explorable example of layers upon layers of incredible complexity that can arise from very simple rules. So I suppose that people who can benefit from that kind of insight might find Conway's Life "useful", in a way -- engineers, mathematicians, and just anyone who is curious about the universe we live in and the physical laws that seem to underly its behavior.

The big surprise that I've been spending the most time on lately is the utterly strange result that if you can build something by colliding gliders together -- no matter now many gliders and no matter how big the final pattern is -- then you can also build it by starting with exactly fifteen gliders in an otherwise empty Life universe:

  https://biggieblog.com/building-arbitrary-life-patterns-in-15-gliders/

It's a mind-bending result -- partly just a mathematical trick, since you end up encoding a whole lot of information in the space between the gliders -- but it's just really amazing that all the details have actually been figured out to make the trick work, and that it's possible to simulate the whole process on a personal computer.

It's hard to choose one these days -- a whole pile of open problems actually got solved in the last few years, like omniperiodicity, glider syntheses of really complicated things like spacefillers, fixed-cost universal construction (it only takes fifteen gliders to build anything buildable) and still lifes and oscillators that solve the "unique father problem" (i.e., there are groups of cells that, if they're found in the Life universe at any point, they must have been there from the beginning of time.) So now I don't know what to wish for next!

I suppose if I get a free wish for anything I want, I'd love to see a glider synthesis for Sir Robin, which a big oblique spaceship discovered in 2018. It's currently way beyond our ability to figure out how to build it out of gliders -- but twenty years ago the same was true of just about every Life spaceship, and now we have recipes for dozens of them.

There's been quite a lot of experimentation with 3D versions of Conway's Life -- including rules where you can easily emulate Life on a 2D slice of the 3D plane. Carter Bays did some investigations and published papers back in the 1980's:

  https://conwaylife.com/wiki/Three-dimensional_cellular_automaton

There's been a little bit of revived interest lately, when newer versions of Golly ( https://golly.sourceforge.io/ ) started to include at least some support for 3D rules. Other programs have been showing up recently, though some of them are more ways of visualizing the history of a 2-dimensional rule in three dimensions.

There are a couple of big difficulties that seem to prevent 3D rules from getting a lot of attention. It's just plain a lot more computationally intensive to emulate 3D rules. Also it's a lot harder to see what's going on in the middle of an active 3D pattern -- a lot of the detail tends to get hidden.

There have been some experiments along these lines for "hat" tilings:

  https://conwaylife.com/forums/viewtopic.php?p=161571#p161571

As far as I know, HatLife hasn't been adjusted to make SpectreLife yet, but it's probably only a matter of time!

Actually, that was the way I read it -- was going to post something about that but then noticed you'd already brought up the idea. If every word in the title weren't capitalized (as titles usually are) then I think the title would have been

"Elusive 'einstein' solves long-standing math problem"

which is certainly true -- aperiodic monotiles have been _very_ elusive. Not sure if the author was trying for a double meaning... if so, it does seem like the incorrect secondary meaning has overtaken the primary meaning in a lot of people's minds.

The reference that comes to mind for me is something out of one of Martin Gardner's _Aha! Insight_ books from decades ago -- the idea of encoding something like the Encyclopedia Britannica into one big long bitstring, then converting it into a fraction... and putting one single very careful mark on a stick to represent that fraction.

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.

Heh, yes, same here more or less -- I wrote an assembly-code Life program for my family's first personal computer (TRS-80 Model I) in the early 1980s, then mostly forgot all about Life for almost two decades ... until it became possible to search the Internet for "Conway's Life". At that point I was completely floored by how much progress had been made since the last time I was paying attention.

Ever since 2001 I've been keeping a close eye on new developments so I don't get surprised like that again.

Yup, the connection to self-replication has showed up mostly in the discussion here, in relation to true self-replicating patterns like the https://conwaylife.com/wiki/0E0P_metacell -- which does have a few vaguely cell-like attributes.

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

Heh, not necessarily, that's true, in the sense that all the possible arrangements haven't been tested and shown to be constructible.

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.

Definitely! It's hard to summarize that insight in any kind of concise way, though ... The Game of Life universe seems a bit too "fragile" to allow for the kind of emergent complexity that real-world physics supports. We can build self-constructing things like the https://conwaylife.com/wiki/0E0P_metacell , but if anything gets slightly out of place, the usual result is a truly horrific catastrophic explosion.

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:

https://conwaylife.com/forums/viewtopic.php?f=2&t=5364

(Not just any such pattern, though -- a still life also means that it doesn't change when you evolve it according to Life rules.)

If you want to see what these 21-bit still lifes look like, their glider construction recipes are all stored online, on Catagolue (no, that's not a misspelling):

https://catagolue.appspot.com/census/b3s23/synthesis-costs/x...

It's not impossible that we could come up with a way of crashing less than 15 moving objects together to get an alternate RCT pattern.

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.)