Thanks for this, it brings back memories. I did a similar search of rules way back when but much less systematic.
HighLife and Day and Night were two rules that I found and shared with a private mailing list that Conway was on. He was very complementary as I recall, I was elated.
Day and Night came from a deliberate search of the subset of rules that were self-inverse. For example the inverse of Life is a rule where the background is normally black and objects are white. But some rules have a symmetry where objects exist as well as their inverse.
Likewise HighLife came from a search of rules that supported the Life glider - there’s a subset of neighborhoods that aren’t involved in the glider evolution and can be set to other values. I noticed HighLife because it has a naturally occurring replicator, something very rare.
Given the nature of the complexity of some of the 'devices' generated in the GoL for some rules, doesn't the fact that in this study, the generation space was set constant at 100x100 cells potentially mean that the results could be strongly tied that that arbitrary choice- and that re-running the simulations with a significantly larger board size could result in markedly different complexity categorizations? That was my thought on first read through at least. Would be interesting to do the same thing at multiple scales, to see if the results hold. There's a whole other study there then in determining the potential complexity class dependence on observed board size.
This is very, very cool. The images of the game-space embeddings have so much interesting correlations that represent.... what? Who knows.
The four images at the bottom of the article, along with the first embedding image, strongly suggest that the game groupings are somehow lined up, with a single interrupted loop. Again, to the eye there are lots of correlations that imply categories and relationships. Would be fun to explore.
Truly awesome work. There is a weird second-order kind of beauty here, in that the act of classifying and visualizing the surprisingly-complex emergent behavior of simple CAs is, itself, a meta simple-CA-like algorithm that has managed to produce an astonishingly beautiful and complex result. The fact that this structure is just kinda “baked into” the universe/math and produced basically ex nihilo is mind-blowing.
Cool and everything, but not sure about the relation to Kolmogorov complexity.
1) Are there any assumptions about the compression algorithm that approximates KC? E.g., I can imagine a compression algorithm which stops as soon as it manages to compress data by a single byte, and I don't think that approximates KC.
2) Isn't the KC of all these cellular automata basically the same, and rather low? It's always just Life with different constants, right? (Sometimes a bit lower, when the constants allow for further compression.) Edit: I see the mistake now, the CA needs to include initial conditions
Idea for improvement: In the picker view, when holding down the mouse button, then update the game-canvas with the selected one and play a few iterations. This way you can get a live feedback.
This was a great read. I love the idea of an ordering on CAs to complex systems with extra dispersion about the midsection to help explain things like stability.
Very interesting. Would be nice to see if conclusions persist using something different from image compression algorithm to estimate Kolmogorov complexity
Astronomy actually is sort of about telescopes. Without telescopes, astronomy doesn't exist beyond some basic things. That's of course not true about computation, which is what I assume he meant by "computer science". Maybe a better analogy would have been astrophysics or cosmology.
The way I read this is that computers are a bit like telescopes, in that they allow us to appreciate the structure of the [logical] universe. These instruments sharpen our limited powers of observation, allowing us to see farther or more clearly than we would otherwise be able to do with merely pen and paper.
There's a similar sentiment in the first SICP lecture <https://youtu.be/-J_xL4IGhJA?t=48>, when Harold Abelson brings up the examples of computers and computer science, physics and particle accelerators, biology and microscopes and Petri dishes, and geometry and surveying instruments. All those tools definitely help, and indeed one would struggle at this stage to research without them, but the tools aren't the goals of the sciences.
I'm not sure what Dijkstra would have thought the "goal" of computer science was, but in the lecture Abelson seemed to think it was about describing procedures and processes in a formal manner.
That’s a good link to share and one I thought about earlier, as I have watched that series before. However, as usual, Abelson and Sussman put together a much more coherent and thoughtful argument.
I know what Dijkstra was going for, but I do think the astronomy analogy, though while pithy in his usual attention grabbing style, is not accurate because telescopes practically define astronomy.
What you linked is what anyone wanting to think about this line of thinking more should watch. I almost feel I should watch those lectures once a year.
In Buddhism there is a school that is different from those which think mainly about pure and trying just be in n. Or all beings in n. It is all about existence and emptiness together. And not Or.
You can still think about computer algorithms without a way to realise it though. And astronomy without observation as well. But what is the point.
HighLife and Day and Night were two rules that I found and shared with a private mailing list that Conway was on. He was very complementary as I recall, I was elated.
Day and Night came from a deliberate search of the subset of rules that were self-inverse. For example the inverse of Life is a rule where the background is normally black and objects are white. But some rules have a symmetry where objects exist as well as their inverse.
Likewise HighLife came from a search of rules that supported the Life glider - there’s a subset of neighborhoods that aren’t involved in the glider evolution and can be set to other values. I noticed HighLife because it has a naturally occurring replicator, something very rare.