Life Lessons...?

For general discussion about Conway's Game of Life.
SiobhanRoberts
Posts: 1
Joined: September 18th, 2020, 9:44 am

Life Lessons...?

Post by SiobhanRoberts » September 18th, 2020, 9:55 am

Greetings Lifenthusiasts,

On the occasion of the 50th anniversary of the Game of Life, I am researching/searching out "Life Lessons" — ie, What did you learn, scientifically or philosophically or otherwise, from the Game of Life that has stayed with you/that is still resonant and compelling today? Or more generally, what aspect of Life do you think is important to highlight at this moment in time? And, bonus question, what is your favorite Lifeform, and why?

Siobhan

User avatar
pcallahan
Posts: 854
Joined: April 26th, 2013, 1:04 pm

Re: Life Lessons...?

Post by pcallahan » September 18th, 2020, 1:57 pm

The most obvious ones are connected to emergence.

"Law of small numbers" Specifically with respect to gliders and other small spaceships and oscillators. There are relatively few ways to arrange 5 cells in a connected pattern, so it should not come as a big surprise when the same thing comes back (shifted, rotated, or indeed glide-reflected) after applying some rule. Takeaway: Don't try to design CA rules. Start with the simplest ones and see what they already do.

Universality. It should not be surprising when any mathematical system with infinite memory is as powerful as a Turing machine. It is harder to design a system that is not universal than one that is. This is (I hope) part of current intuition, but it was not 50 years ago, or at least the intuition was not as widespread (consider Hao Wang's initial, incorrect conjecture that Wang tiles should always admit a periodic tiling).

A less obvious one has occurred to me after spending time on Critters, a reversible Margolus-rule CA:

Erasing information is just as useful as generating it! In the context of Life, this explains why vanishing reactions and eaters, among other things, are a crucial part of so many engineered designs. Often an initial discovery produces what you want plus some extra stuff that you don't want, even if in a different context it could be "useful." The ability to "clean" the result makes a difference as to whether it is applicable to larger patterns or just an isolated curiosity. The connection to reversibility is that you cannot have vanishing reactions in reversible CAs, because this would imply a state with a non-unique predecessor. (However, you can still do everything you need in a reversible CA, but the "vanishing" must be carried out with the explicit release of patterns that recede to infinity and carry the history. This is much like removing waste heat in real-life engineering.)

I don't have a favorite pattern, but I am going to put in a vote for the https://www.conwaylife.com/wiki/Herschel since it is such a versatile component of stable technology.
Last edited by pcallahan on September 18th, 2020, 11:39 pm, edited 1 time in total.

User avatar
pcallahan
Posts: 854
Joined: April 26th, 2013, 1:04 pm

Re: Life Lessons...?

Post by pcallahan » September 18th, 2020, 3:55 pm

Also, aside from technical lessons, a "social" lesson. A sufficiently motivated hobbyist community can move far in advance of universities and industry. The explicit examples of self-replication in Life and the novel patterns found through search have no parallel in peer-reviewed literature. I'm not exactly sure why this is. And in fact, when academic research does make a reference to Conway's Game of Life, it usually lacks the depth of understanding of this community.

This is not really the work of amateurs. Many have a "day job" involving more conventional research, and know more about CGOL than ostensible experts in cellular automata. Maybe it's the inability to pigeonhole it into a research field (so no university interest) and no way to monetize it (so no industry interest). I suspect that there are some learnings that will be useful to keep in mind when we start to build real-life self-replicating machines (whether nanotechnology or some other approach). I'm not alone in the frustration that this "hobby" has produced very sophisticated work by experts and yet is not taken seriously.

Naszvadi
Posts: 1248
Joined: May 7th, 2016, 8:53 am
Contact:

Re: Life Lessons...?

Post by Naszvadi » September 18th, 2020, 5:30 pm

Wait, are you that Siobhan Roberts who interviewed J. H. Conway? :?:

wwei23

Re: Life Lessons...?

Post by wwei23 » September 19th, 2020, 9:30 am

pcallahan wrote:
September 18th, 2020, 1:57 pm
Takeaway: Don't try to design CA rules. Start with the simplest ones and see what they already do.
Well, I would disagree slightly with that. It can be fun to design rules with gimmicks like this one:

Code: Select all

x=3, y=2, rule=B3-cy4e5i6ck/S23-kq4w5j8
3o$bo!

User avatar
pcallahan
Posts: 854
Joined: April 26th, 2013, 1:04 pm

Re: Life Lessons...?

Post by pcallahan » September 19th, 2020, 10:55 am

wwei23 wrote:
September 19th, 2020, 9:30 am
Well, I would disagree slightly with that. It can be fun to design rules with gimmicks like this one:

Code: Select all

x=3, y=2, rule=B3-cy4e5i6ck/S23-kq4w5j8
3o$bo!
I could have phrased it better. There's nothing wrong with designing rules. My point, I guess, is that you don't have to in order to find something interesting.

wwei23

Re: Life Lessons...?

Post by wwei23 » September 19th, 2020, 11:06 am

pcallahan wrote:
September 19th, 2020, 10:55 am
My point, I guess, is that you don't have to in order to find something interesting.
That is something I perfectly agree with.

User avatar
wzkchem5
Posts: 127
Joined: April 17th, 2020, 2:19 am
Location: Valles Marineris, Mars

Re: Life Lessons...?

Post by wzkchem5 » September 19th, 2020, 12:43 pm

SiobhanRoberts wrote:
September 18th, 2020, 9:55 am
Greetings Lifenthusiasts,

On the occasion of the 50th anniversary of the Game of Life, I am researching/searching out "Life Lessons" — ie, What did you learn, scientifically or philosophically or otherwise, from the Game of Life that has stayed with you/that is still resonant and compelling today? Or more generally, what aspect of Life do you think is important to highlight at this moment in time? And, bonus question, what is your favorite Lifeform, and why?

Siobhan
I would add the intriguing possibility that our own universe is simulated by an automaton. This is the view that Stephan Wolfram is always holding, though in recent years his interest shifted to network-based dynamic systems, rather than cellular automata.

When supporting this view, people often cite the emergence of particle-like structures (especially spaceships) in Life and other CAs, the reactions between these structures, and, for certain CAs, the resulting Turing completeness. And I would like to add a new argument, which is rarely (if ever) discussed before. In fact this gives the much stronger claim that: a typical universe simulated by an automaton will probably look the same from the view of intelligent beings that live in it, regardless of which Turing complete rule you are using!

Since a Turing complete system can simulate any other Turing complete system, if you simulate a very dilute and very large soup in Life (or any other Turing complete CA), then theoretically you will observe spontaneous emergence of patterns that simulate every other Turing complete system (including but not limited to CAs) with arbitrary initial conditions. They will themselves give rise to patterns that simulate all possible Turing complete systems, which will themselves carry out their own simulations, ad infinitum. Now consider: of all simulations of Turing complete systems that pop up from the Turing complete system I with the initial condition i, how many will (directly, without simulating another Turing complete system as an intermediate level) simulate some Turing complete system J with the initial condition j? Denote the result by N({I,i},{J,j}). Gathering the N({I,i},{J,j}) values for all combinations of I, i, J, j, we get an infinite matrix N. Thus, the number of instances of Turing complete system-initial condition pair {J,j} that will be simulated by the system-initial condition pair {I,i} is given by the {I,i}'th row of the matrix N. Now the salient point is: by basic linear algebra we find that the {I,i}'th row of the matrix N^2 gives the number of instances of {J,j} that can be simulated by those Turing complete systems simulated by {I,i} (i.e. on the second level of the "simulation hierarchy"), and the {I,i}'th row of the matrix N^3 gives the number of instances of {J,j} that can be simulated by those Turing complete systems simulated by those Turing complete systems simulated by {I,i} (i.e. on the third level of the "simulation hierarchy"), etc. And according to a theorem in linear algebra, whenever the largest eigenvalue of N is greater than 1 and non-degenerate, and that the associated eigenvector has a non-zero {I,i} component, the {I,i}'th row of the matrix N^(infinity) will, apart from an infinitely large multiplicative constant, be independent of {I,i} and proportional to that eigenvector. This means that, under the above assumptions, the proportion of simulations of a particular Turing complete system-initial condition pair {J,j} will be completely independent of the bottom-level Turing complete system-initial condition pair {I,i}!

Some far-reaching consequences are:

(1) The universes simulated by different Turing complete systems will be totally indistinguishable from the viewpoint of the creatures that live in the universes themselves, since the creatures can only probe the top level of the simulation hierarchy (i.e. if A simulated B which then simulated C ... which then simulated Z, they can only know the rule Z and its associated initial condition), and with the above assumptions the top level of the simulation hierarchy is independent of the bottom level of the hierarchy. Thus, they will be totally and forever clueless as to the bottom level reality of their universe, apart from the fact that the eigenvector corresponding to the largest eigenvalue of N has a non-zero entry for the {I,i} pair that corresponds to the true bottom level reality. They cannot even say which {I,i} pair is more likely the right answer than some other {I,i} pair.

(2) Our own universe as we know it is Turing complete too, and it has an initial condition. Thus, the list of {I,i} includes our universe, which we denote as {U,u}. If in addition the eigenvector corresponding to the largest eigenvalue of N has a non-zero entry for {U,u} (and the eigenvalue is larger than 1), then in the far, far future of our universe, there will be computers that simulate other universes, which then give birth to computers that simulate yet other universes ... Moreover since our own universe is also simulated infinitely often in this simulation hierarchy, it is infinitely more likely that we ourselves are simulated than we are real. Then we will be the creatures in (1) - we will never have any idea about the bottom level reality of our own universe (i.e. the aliens that used computers to simulate computers that simulate computers that ... simulate us), other than that it has a non-zero share in the eigenvector of matrix N that corresponds to its largest eigenvalue.

(3) Under the above assumptions, the probability that a Turing complete universe has a certain set of physical rules and initial condition (as viewed by its creatures themselves) is uniquely defined from pure mathematics, since this is nothing but the aforementioned eigenvector of N. Although the probability is very likely uncomputable, suppose that we have a non-trivial estimate of it. Then we can explain why our universe looks like the way it does, by showing that our universe has a relatively large probability than other candidate universes. If however our universe turns out to be a very improbable one, then this must be solely due to anthropic origins, and nothing else. People have tried to define such a probabilistic measure of possible universes using string landscape etc., and then invoke the anthropic principle to explain all the unexplained fine-tunings, but the present approach does not even need the assumption that strings exist at all, and is fully non-empirical.

Of course the above argument is kind of hand-wavy because there are lots of infinities which may easily ruin the whole argument, but I hope that this convinces you that it is an exciting aspect of CAs that is previous overlooked and worths pursuing.

(And, for that matter, my favorite Lifeform is the infinitely dilute soup, if that really counts as a Lifeform; it retains every single possibility of Life patterns but gives them a non-empirical probabilistic measure, and allows us to distinguish the more natural phenomena from largely artificial ones.)
The Red Phoenix, The Yellow Phoenix, The Pink Phoenix And The Multicolored Phoenix

User avatar
dvgrn
Moderator
Posts: 10671
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Life Lessons...?

Post by dvgrn » September 19th, 2020, 1:20 pm

A slightly different and not entirely serious angle:

Conway's Life has also turned out to be a fairly effective Sorting Hat, so to speak, that can divide up Lifenthusiasts into "mathematician" and "engineer" categories.

At least the way I hear the story, Conway proved in the very early 1970s that the Game of Life was Turing complete and allowed for universal construction... and then apparently he was immediately able to check off whole classes of problems as being relatively uninteresting, not particularly worthy of further investigation.

Calculate the digits of pi, or build a replicator with quadratic population growth? "Yeah, that's proven to be possible, why talk about that any more?" Stable glider reflectors now seem like a basic building block for many Life patterns. But oddly enough, stable glider reflectors languished in that "They Definitely Exist But We Can't Exhibit A Pattern" category -- for more than a quarter of a century.

Engineers To The Rescue, Whether They're Wanted or Not
However, possibly somewhat to Conway's dismay, many Lifenthusiasts turned out not to be particularly interested in non-constructive proofs of what was possible for Brobdignagian patterns in unmanageably huge grids. They kept right on working on basic research, finding new simpler mechanisms, new ways to search for solutions to problems, and so on. Gradually over the years, dozens of problems have moved from "theoretically possible but most likely we'll never be able to build something that does X" to "Here's a pattern that does X".

A very recent example is the last few years of intermittent work on the reverse caber-tosser design. It has been "proven" -- we think -- that any pattern constructible by gliders can be constructed with exactly 17 gliders. (That's a result from just this morning; last week the number was 32, and before that it was 42, and it started way up at 329.)

But though some Lifenthusiasts are reasonably happy to say "17 gliders is the maximum needed for any construction", others are not quite comfortable with that. They want to see a sample pattern in action before they'll really believe it. A non-constructive proof of the existence of something seems somehow unsatisfying; it doesn't really seem to be quite "existence" at all, in fact!

My sympathies tend to lie with the "engineer" camp. When a proof gets complicated enough, there's always the possibility that there's a flaw in the proof somewhere. The only really good antidote for that kind of small gnawing doubt is a proof by construction.

Not surprisingly, my favorite Conway's Life pattern is the ultimate example of proof by construction, Adam P. Goucher's 0E0P metacell.

(However, the double-wickstretcher technology in Pavel Grankovskiy's Speed Demonoid -- just completed yesterday -- seems to imply that the 0E0P is quite a bit bigger than it really needs to be...!)

User avatar
pcallahan
Posts: 854
Joined: April 26th, 2013, 1:04 pm

Re: Life Lessons...?

Post by pcallahan » September 19th, 2020, 6:30 pm

dvgrn wrote:
September 19th, 2020, 1:20 pm
Conway's Life has also turned out to be a fairly effective Sorting Hat, so to speak, that can divide up Lifenthusiasts into "mathematician" and "engineer" categories.
Good point. (Speaking as someone content to sort into Hufflepuff and just say no to elitism, but that's for another day and probably an entirely different website.)

Throughout my education, I was partially socialized into the view that once you can see something is possible, actually doing it is irrelevant. A lot of algorithms in theoretical computer science are like that, particularly some of the massively parallel algorithms in vogue at the time (early 90s). But I don't think I ever really felt that way. A design for an airplane is not an airplane you can fly. A proof that heavier than air flight is possible is not even a design for an airplane. I would like to fly an airplane, not just know that I could.

One thing is that I don't trust my mathematical ability nearly enough to believe a proof until I have some kind automatic implementation that doesn't rely on my potentially faulty brain wiring. The other thing is that it is just more fun. The fact that people have actually constructed explicit self-replicating machines in Life is significant because for one thing, there could always have been some spacing or timing issue that was just not resolved as well as everyone thought, and for another, it is something living and breathing, not just a static plan.

Added: this is getting far afield, but it does raise a philosophical question. I wonder sometimes what is the difference between existence and potential to exist. The universe is a system obeying certain laws apparently capable of embedding conscious entities. Other systems can be described that are just as capable of such an embedding. I "know" this one exists or at least that instant of my consciousness exists with something that I perceive to be the universe as I know it. In a mathematical sense, all the other ones "exist' too. I don't think they exist in the same way. I think it's significant that this one in particular is realized and I experience it. Why is that? (And this is juvenile and I'm sure competent philosophers have been all over it.)

Life does provide an interesting context in which to consider this kind of thing. You can specify a pattern with an undecidable outcome. You can watch it run for a hundred or a million generations. It seems that it has actually run for those generations but that its future, which can be specified notationally g^n(P) lets say, where g is the rule, P is the pattern and n is the number of steps has not really "run" unless you can say something about actual cell values. That matters to me. I suspect it matters less to some mathematicians, though they would probably want to be able to say something about the future (asymptotic cell count for instance) before claiming to understand it.

Now the same is also true of a Turing machine or for that matter a conventional computer. But I think it's more compelling in the context of Life because it "feels" more like a physical system with geometry and dynamics.

So I guess the "Life lesson" here is the possibility of an in vitro universe and all of the speculation that comes from being able to reproduce and observe it.

NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Re: Life Lessons...?

Post by NickGotts » September 26th, 2020, 12:03 pm

Conway's Life has also turned out to be a fairly effective Sorting Hat, so to speak, that can divide up Lifenthusiasts into "mathematician" and "engineer" categories. - dvgrn
I think I belong to a third category (possibly the only active member!): "naturalists". I'm mostly interested in what kinds of complexity can emerge from "simple" rules and initial conditions, and I've never come across a formal system better suited to such investigations than CGoL.

Siobhan, I got interested in CGoL when Martin Gardner published his first article on it in Scientific American. For most of that time, I've been most interested in (a) "minimal cell-count problems" - what's the fewest cells that can give rise to a given type of pattern?, (b) whether there are finite patterns that go on producing certain types of novelty* indefinitely and (c) what happens in "Sparse Life" - an infinite (or arbitrarily large) CGoL field with an arbitrarily low (but non-zero) random scattering of "On" cells - this was the subject of some speculation early on, and also in the late 1990s, but AFAIK I'm the only person to have done systematic work on it. Topics (a) and (c) are connected, and (b) and (c) both tell us quite a bit about the nature of complexity, and how it comes into existence. I'm talking here about structural and behavioural complexity, which is distinct from algorithmic complexity (the definition of which makes a patternless string of digits more "complex" than one with a pattern) and computational complexity, which is about how the resources needed to solve problems of a given class grow with the size of the problem - and I think is closer to the everyday meaning of the term than either of those. Difficult to summarise what I think CGoL shows (I have published papers on it if you're interested), but the patterns I'm interested in tend to be multi-scale, with the different spatial and temporal scales partially but not wholly distinct, so you can make a reasonable prediction what they will do by looking at the larger/coarser scales, but sometimes events at the finer scales will prove you wrong! A bit like a lot of natural and social structures and processes, in my view. One small observation on these lines: popular and even academic treatments of "complex systems" often claim you can't predict them except by running them step-by-step. But among cellular automata, this is only true of highly "chaotic" kinds (which are not complex in the sense I'm interested in). It's not true of CGoL - if it were, the Hashlife algorithm would never gain you anything (it doesn't, much, if you apply it to an asymmetric strating pattern in a chaotic rule like "Persian rug", B234/S). Another: growing complexity from small, simple starting patterns in CGoL always seems to involve what I call a "ramifying feedback network" - one or more waves or streams of gliders that interact with each other, and with growing but largely static structures, in increasingly convoluted ways, producing a series of novel interactions that continues for (at least) billions or trillions of ticks.

As for a favourite lifeform, has to be a particular variant of the switch engine, found by Paul Callahan back in 1998. All other infinite-growth patterns are engineered from simpler components (even ones like spacefillers where the components are always in contact). This (along with 5 trivial variants) is the smallest from which infinite growth just emerges "naturally":

Code: Select all

x = 6, y = 8, rule = B3/S23
o2$2o2$2b3o2$3b3o$4bo!
*We know there are patterns that will, for example, construct an unending series of Universal Turing Machines, and apply each UTM to a different starting tape, some of which would never lead to a halt, but this would not be the kind of novelty I want: each would remain obediently within its own strip of cells, never interfering with its neighbours, or producing new kinds of spaceship, gun, or puffer.

User avatar
pcallahan
Posts: 854
Joined: April 26th, 2013, 1:04 pm

Re: Life Lessons...?

Post by pcallahan » September 26th, 2020, 1:40 pm

NickGotts wrote:
September 26th, 2020, 12:03 pm
One small observation on these lines: popular and even academic treatments of "complex systems" often claim you can't predict them except by running them step-by-step. But among cellular automata, this is only true of highly "chaotic" kinds (which are not complex in the sense I'm interested in). It's not true of CGoL
I think it is "true" or at least can be made into a true statement with the right FOL quantifiers. The point is that there exist patterns that cannot be predicted out to n steps without doing the equivalent work of running them, if not "step-by-step" then at least requiring f(n) work, where f is possibly sublinear but "reasonable" (e.g. can be expressed in closed form in some conventional notation).

This is not contradicted by Hashlife. You can accelerate the simulation, but you can't predict its far future without a great deal of work. It is also not contradicted by a single glider. While the glider's future is completely known in a reasonable sense, there are other CGoL patterns that are not.

You can make qualitative distinctions. E.g. "most" random finite starting states below a certain size settle into an "ash" of oscillators and escaping spaceships or gliders, now predictable. Above a certain size, you find switch-engines leaving the boundaries, but it's still predictable. Beyond that, there should be some point at which truly unpredictable embeddings of universal TMs appear spontaneously, though I'm not sure what that point is.

This stands in contrast to e.g., a CA based on finding an XOR of neighbors. In this case, it is possible to write a formula for individual cell states far into the future. These kinds of CAs are the exceptional cases though, and the unpredictable ones are the norm. (And trivial CAs that just erase the cell values are obviously predictable.)

Anyway, that is my take on the claim that "you can't predict them."

Life lesson (if I didn't mention it already): CGOL is interesting because it contains many "predictable systems" subject to analysis within a framework that is ultimately unpredictable.
Last edited by pcallahan on September 26th, 2020, 4:29 pm, edited 1 time in total.

User avatar
rowett
Moderator
Posts: 3815
Joined: January 31st, 2013, 2:34 am
Location: UK
Contact:

Re: Life Lessons...?

Post by rowett » September 26th, 2020, 2:15 pm

I discovered Conway's Game of Life several decades ago. It immediately became my go to problem for implementing in every new computer language I stumbled across, like a rosetta stone for programming.
Simple to implement yet fascinating to watch. An excellent return on investment: a little time, a big reward.

I'm not particularly a Life enthusiast. I'm not motivated in finding the next significant undiscovered pattern.

I do like the art. The visualisations.

But most of all I like how the software tools enable sharing and productivity. Every time there is a new or enhanced tool it stimulates a flurry of research and activity that moves the field into brand new areas.

If Conway and the team 50 years ago had the tools at their disposal that we have now...

User avatar
pcallahan
Posts: 854
Joined: April 26th, 2013, 1:04 pm

Re: Life Lessons...?

Post by pcallahan » September 26th, 2020, 3:02 pm

rowett wrote:
September 26th, 2020, 2:15 pm
If Conway and the team 50 years ago had the tools at their disposal that we have now...
It would be hard to convince anyone in the early 1970s that we would have no base on the moon (indeed no human presence at all), but that billions of us would be carrying phone-size devices that could run the original Breeder at 20 frames/second--and that this was not even close to the limits of what was possible.

I agree that the sharing and productivity part is a big deal, and it is certainly enabled by LifeViewer. (I'd still like a moon base though.)

User avatar
rowett
Moderator
Posts: 3815
Joined: January 31st, 2013, 2:34 am
Location: UK
Contact:

Re: Life Lessons...?

Post by rowett » September 26th, 2020, 3:18 pm

pcallahan wrote:
September 26th, 2020, 3:02 pm
I agree that the sharing and productivity part is a big deal, and it is certainly enabled by LifeViewer. (I'd still like a moon base though.)
I was thinking about Catagolue, the plethora of search tools and SAT solvers, Discord with Caterer, the glider synthesis database, LifeWiki, the Forums here, Golly, and many other tools. (Me too.)

User avatar
pcallahan
Posts: 854
Joined: April 26th, 2013, 1:04 pm

Re: Life Lessons...?

Post by pcallahan » September 26th, 2020, 3:57 pm

rowett wrote:
September 26th, 2020, 3:18 pm
pcallahan wrote:
September 26th, 2020, 3:02 pm
I agree that the sharing and productivity part is a big deal, and it is certainly enabled by LifeViewer. (I'd still like a moon base though.)
I was thinking about Catagolue, the plethora of search tools and SAT solvers, Discord with Caterer, the glider synthesis database, LifeWiki, the Forums here, Golly, and many other tools. (Me too.)
Well, don't rule out the significance of an embedded pattern viewer. It accelerates interaction in incalculable ways. I remember when the web first came out dismissing it as just putting a nice UI on top of FTP and email. Clearly I was wrong. Integrating tools is as important as developing them in the first place.

Even the process of having to copy-paste some RLE into Golly or equivalent reduces the probability by some amount that any particular person will look at a pattern or appreciate what you're trying to illustrate.

User avatar
wzkchem5
Posts: 127
Joined: April 17th, 2020, 2:19 am
Location: Valles Marineris, Mars

Re: Life Lessons...?

Post by wzkchem5 » September 27th, 2020, 11:29 am

NickGotts wrote:
September 26th, 2020, 12:03 pm
I think I belong to a third category (possibly the only active member!): "naturalists". I'm mostly interested in what kinds of complexity can emerge from "simple" rules and initial conditions, and I've never come across a formal system better suited to such investigations than CGoL.
You are not alone - I'm also a naturalist by your definition! And I really appreciate your work on infinitely dilute, random soups!
The Red Phoenix, The Yellow Phoenix, The Pink Phoenix And The Multicolored Phoenix

User avatar
pcallahan
Posts: 854
Joined: April 26th, 2013, 1:04 pm

Re: Life Lessons...?

Post by pcallahan » September 27th, 2020, 12:07 pm

NickGotts wrote:
September 26th, 2020, 12:03 pm
popular and even academic treatments of "complex systems" often claim you can't predict them except by running them step-by-step.
I want to get back to this with an explicit example.

A two counter machine is universal. That is, a finite state automaton augmented with infinite storage consisting only of two counters that can be incremented, decremented, and tested for 0, can simulate any Turing machine. (This result should be well known to CGOLers because it is used to prove that a pattern with block-pusher based counters is universal.)

On the other hand, it's really not all that interesting to run a machine like this. You can encode a Turing tape with counter values and have it plug away. The simulation requires exponential slowdown as the tape bits must be read off a unary encoding of very large integers.

It's not quite true that you can only predict it by running "step-by-step". I can think of many ways to accelerate the operation. For any given state and large enough counter values, you can predict the next step at which one of the counters will reach 0 (before then, the counter values do not matter). (I haven't thought this through, but it seems correct).

It is still fair to say that a 2-counter machine is unpredictable except by running it. I think my interpretation is standard. Is it?

User avatar
dvgrn
Moderator
Posts: 10671
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Life Lessons...?

Post by dvgrn » September 27th, 2020, 5:04 pm

pcallahan wrote:
September 27th, 2020, 12:07 pm
It is still fair to say that a 2-counter machine is unpredictable except by running it. I think my interpretation is standard. Is it?
Seems pretty standard to me. There are often entertaining shortcuts where one Turing-complete system can be emulated very efficiently by another Turing-complete system.

So Unpredictable except by running it always has an unstated corollary, ...or by running some other equivalent system that might be more efficient, but ultimately is still also unpredictable except by running it.

I guess the other thing that that phrasing doesn't make quite clear, is that a 2-counter machine isn't always unpredictable no matter how you program it; many programs can in fact be analyzed and predicted reliably, as far into the future as you want, without running the program. It's just that you can always find a way to program a task for which there aren't any such shortcuts.

User avatar
Kazyan
Posts: 1247
Joined: February 6th, 2014, 11:02 pm

Re: Life Lessons...?

Post by Kazyan » September 28th, 2020, 10:33 am

Philosophical/scientific observation: Conway's Game of Life does not have any properties that are easily expressed as a conservation law, and it's better for it.

This sticks out to me because conservation laws are everywhere, not just in science, but in art. I enjoy the occasional video game, and I like the setting-building aspects of fantasy stories. In media critique, such costs and limits need to be plentiful in order for a setting to be taken seriously, and in mathematics, adding strict conservation principles usually makes things more interesting rather than less. But the opposite case applies in Conway's Game of Life. If you want more gliders, you can have them. Having trouble with your signal circuitry? We'll just invest nicer things. Is the technology set in stone? Someone just scripted a jackhammer. There's almost always a way to get around an engineering limitation if you search long enough for the right micropattern.

Aspects to highlight: In addition to the mathematician/engineer distinction, there are clear "micro" and "macro" distinctions in the engineering category. "Micro" is a matter of searching for conduits, reflectors, glider syntheses, etc., where "macro" assembles it all into bigger parts--like the Speed Demonoids. I'm not sure how to comment on it, but we have regimes where 1,000,000 HD is a cozy space to work within, and others where a loafer is gigantic.
Tanner Jacobi
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.

User avatar
pcallahan
Posts: 854
Joined: April 26th, 2013, 1:04 pm

Re: Life Lessons...?

Post by pcallahan » September 28th, 2020, 12:34 pm

Kazyan wrote:
September 28th, 2020, 10:33 am
But the opposite case applies in Conway's Game of Life. If you want more gliders, you can have them.
I agree. I think most people would like to do magic, and in the CGOL universe, the magic really works.

Just to put the "conservationists" at ease, though, I wonder if there is a nice 3D embedding that is reversible and preserves the count of live cells. I don't see why there wouldn't be. What I imagine is a CGOL operating in one plane while usable energy in the form of an endless regular stream of live cells comes from below for each 2D position, and heat is output above. You can also run it in reverse. Of course you won't reverse the Life pattern past step 0. It will just start up again in forward order and the energy and heat will be swapped.

(I have already worked on a reversible 3D rule but I'm not sure what it would take to make it follow physics-like conservation laws.)

Margolus critters is somewhat Life-like but has conservation laws. In many ways it is not as fun to work in, but it can be pretty cool to watch in reverse.

ntdsc
Posts: 68
Joined: November 13th, 2017, 1:12 pm

Re: Life Lessons...?

Post by ntdsc » September 28th, 2020, 1:43 pm

One other thing Conway worked on is the monster group, which is involved in symmetry. This physicist says machine learning is associated also with symmetry: https://www.youtube.com/watch?v=0DEJ4QL5bcs

And I quote from a mathematical subject of monster group: "Borcherds’s creation fulfilled Dyson’s hope that the monster would somehow be embedded into the structure of the universe, or at least took it a step in that direction. His proof demonstrated that the monster is the symmetry group not of a lattice or a code but of conformal field theory, part of the mathematical language of string theory." And it is interesting also that in wolfram's new physics project, his theory generates relativity and quantum mechanics but he hasn't stressed string theory.

wwei23

Re: Life Lessons...?

Post by wwei23 » October 6th, 2020, 12:51 pm

Continuing on the emergence thing, I'd like to mention that I don't design rules to try and make unusual replicators like this one, rather I have a script try random rules and hope that an interesting replicator appears.

Code: Select all

x = 29, y = 24, rule = B2e3aiky4jnqtwz5cjqry6aei/S1c2-k3ajry4cjkrt5-eqr6i
7b3o9b3o$8bo11bo$8bo11bo$7b3o9b3o$12bo3bo$11bobobobo$11bobobobo$12bo3b
o7$8bo11bo$7b3o9b3o$7bobo9bobo2$12bo3bo3$b2o23b2o$o2bo21bo2bo$b2o8b2o
3b2o8b2o!

MathAndCode
Posts: 5142
Joined: August 31st, 2020, 5:58 pm

Re: Life Lessons...?

Post by MathAndCode » October 7th, 2020, 9:06 pm

There are two ways to think about ConwayLife: cell-based and pattern-based. The cell-based approach focuses on the individual cells and whether they're on or off. The individual cells do not move. They merely turn on or off. The pattern-based approach focuses on entire patterns. Unlike the cell-based approach, the pattern-based approach allows objects, such as gliders, to move.
A while ago, I was learning about different religions, and I found a cell-based view of the Universe versus a pattern-based view of the Universe to be a helpful analogy for understanding a concept in Hinduism.
I am tentatively considering myself back.

User avatar
wzkchem5
Posts: 127
Joined: April 17th, 2020, 2:19 am
Location: Valles Marineris, Mars

Re: Life Lessons...?

Post by wzkchem5 » October 8th, 2020, 1:08 am

MathAndCode wrote:
October 7th, 2020, 9:06 pm
There are two ways to think about ConwayLife: cell-based and pattern-based. The cell-based approach focuses on the individual cells and whether they're on or off. The individual cells do not move. They merely turn on or off. The pattern-based approach focuses on entire patterns. Unlike the cell-based approach, the pattern-based approach allows objects, such as gliders, to move.
A while ago, I was learning about different religions, and I found a cell-based view of the Universe versus a pattern-based view of the Universe to be a helpful analogy for understanding a concept in Hinduism.
Which concept?
The Red Phoenix, The Yellow Phoenix, The Pink Phoenix And The Multicolored Phoenix

Post Reply