Hierarchies in the Game of Life

[hpstricker]

I'd like to learn more about the hierarchical complexity of structures that can arise in Conway's Game of Life (GoL).

I know several generic kinds of patterns -- still-lifes, oscillators, spaceships, guns and puffer trains -- (each of rather low hierarchical complexity), and that these patterns can hierarchically compose higher structures up to a univeral Turing machine (UTM).

1. Is there a general theory of hierarchical structures that can arise in GoL? (... their ways of composition, and the hierarchical level they can reach)

2. How are - eventually - the conceputally necessary mediating structures directing to an UTM be named?

3. What is the most complex structure "discovered" in GoL (with respect to a supposed "level of hierarchy")?

[dvgrn]

3. What is the most complex structure "discovered" in GoL (with respect to a supposed "level of hierarchy")?

Maybe Calcyman's Universal Computer-Constructor? Lots more versatility there than in a mere Turing machine or Minsky register machine (which can only calculate things) or in a Geminoid replicator unit (which can only build things).

Now, the 2009 model of the UCC had some interesting limitations; among other things it gave new meaning to the term "memory leak" -- a glider escaped to infinity every time you read a "1" on the memory tape. But it wouldn't take that much work to fix that little problem, and then eventually someone might take up the challenge of figuring out how to actually program a UCC to do something interesting.

I'm not sure what the next level on the hierarchy would be: cooperating populations of self-replicating UCCs? UCCs with self-modifying program code? A UCC that emulates a human brain, perhaps?

If a computer can do it, so can a Conway's Life pattern... as long as you don't want it done particularly quickly. Myself, I very much prefer patterns that Golly can actually run. Patterns toward the end of the list might need more ON cells than there are electrons in the known universe, and/or more ticks than there have been nanoseconds since the Big Bang... so please don't take them too seriously.

[simsim314]

I'm not sure what the next level on the hierarchy would be

On my opinion it's pretty obvious: Make C compiler. Write code in C and this code will generate a pattern in Life. More than that have some "interface" to show the result, like in Pi calculator there is something similar to "console", that you can use printf or WriteLine functions. Not only "calculate" but also "present" the result in nice way.

For example: write a chess engine in Life, that obviously use some sort of UCC, but also can "interact" with the user.

Human brain is currently impossible to simulate in real computers as well.

-----

By the way I'm not sure that chess engine in Life would play "worse" than real life chess engine. Because in Life you can have "parallel" computation very naturally. And although the regular chess engines also have access to parallel computing, they usually don't use it in such extent as it can be used in Life.

Myself, I very much prefer patterns that Golly can actually run.

I think you're a bit too depend on golly limitations. One can improve golly algorithms, to perform better in some cases. Like the "different direction gliders", they could be improve using a bit smarter "HashLife" algorithm. Or even some "external application" outside of golly that made to be optimized for replicators (or any other similar application). I do agree that patterns that could be executed on computer, are preferred to patterns that are not. But golly HashLife is not the "end of the line". There are plenty of ways to improve and optimize, especially with certain "types" of models (like we could write a special utility that works better than golly for the current linear replicators, we just need to introduce the concept of "glider" which is not that complex).


----

As for the initial question I don't think we have some "restricted" hierarchy of objects. I'm currently trying to work with sort of "basic" operational object, like reflectors and duplicators. See the Geminoid Praticle rule as an example viewtopic.php?f=11&t=1353.

[dvgrn]

Myself, I very much prefer patterns that Golly can actually run.

I think you're a bit too depend on golly limitations.

Yes, I was being a little too specific there. "Golly" was shorthand for "Golly, or some other hypothetical program, but Golly is what we have right now".

But golly HashLife is not the "end of the line". There are plenty of ways to improve and optimize, especially with certain "types" of models (like we could write a special utility that works better than golly for the current linear replicators, we just need to introduce the concept of "glider" which is not that complex).

Yes, there are all kinds of wonderful tricks that could be played. For example, with some relatively minor adjustments HashLife could super-efficiently simulate a repetitive grid that wasn't a power of two, just by assigning various sized hashtiles with null columns and/or rows in the appropriate places. One thing I'd love to see is a way to simulate an infinite agar properly -- not just a single small tile bent around into a torus, but an unbounded universe that is assumed to be full of some MxN repetitive tile. At the moment Golly assumes that untouched parts of the universe are empty, but it could just as well be set up to assume an infinite 'stripes' agar, or some periodic pattern, or even an unending array of OFF metapixel cells.

For replicators there are various sneaky ways to set up the universe so that Golly would know that the SE-traveling glider streams have nothing to do with the NW-traveling glider streams, so that even the larger hashtiles never have both streams on them at the same time. But special cases tend to turn into headaches... a lot of the power of the current Golly HashLife is its amazing simplicity: it can often do wonders just with brute force and memory, without knowing any of the finer points of a specific pattern.

[oblique]

I'd like to learn more about the hierarchical complexity of structures that can arise in Conway's Game of Life (GoL).

I know several generic kinds of patterns -- still-lifes, oscillators, spaceships, guns and puffer trains -- (each of rather low hierarchical complexity), and that these patterns can hierarchically compose higher structures up to a univeral Turing machine (UTM).

1. Is there a general theory of hierarchical structures that can arise in GoL? (... their ways of composition, and the hierarchical level they can reach)

2. How are - eventually - the conceputally necessary mediating structures directing to an UTM be named?

3. What is the most complex structure "discovered" in GoL (with respect to a supposed "level of hierarchy")?

I'm not quite sure that I get your question completely.

One type of pattern that might interest you, tho: you can build a game of life simulator *within* game of life (it has been done: if you have golly look at the metapixel examples). You can easily prove that you could theoretically use this to build a pattern that simulates a pattern simulating another one ...