Calculate complexity of the game of life (cellular automata)

[paulrk]

I want to calculate the kolmogorov complexity of n evolution of a game of game of life(game of life is a kind of cellular automata). I’m not searching for the complexity of a certain pattern of cells but for the total complexity of an initial set of cells over n evolutions. Does it make sense to just add up every operation applied on the game(every creation/deletion of cells)? Since this basically describes all the information that has changed?

Greets

 

[jim mcnamara]

Definition I am aware of:

In algorithmic information theory, the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program that produces the object as output.

There are initial conditions for the Game of Life that have been shown to be undecidable. It is Turing complete I believe.

If I understand your post then you have a problems with your experiment
-- your idea of "n" which should measure algorithm size. Not steps.
-- some initial conditions do not result in a "final object" i.e., not computable

https://www.i-programmer.info/progr...-to-theory-kolmogorov-complexity.html?start=1

Someone who more is knowledgeable about this will step in and correct me if needed.

 

[paulrk]

so I guess the Kolmogorov complexity is not what I'm searching for then. Instead how about just the complexity of a game of life. Or the "amount of information" contained within a game of life with and initial matrix (cell config) over n evolutions?

 

[jim mcnamara]

Let's try this.
For just second:
Forget the name of the program. Forget about iterations.
Without guessing anything tell us - change "X" to some quality, property, or characteristic
"I want to know how to find X in a computer program."

Let's discuss "X" then move on Conway's Life. OK?

 

[paulrk]

sorry I'm not native, I don't really understand the question. if I understood you correctly though you are asking how I define a change "X"?

A change X is any operation that changes the state of a cell in a cellular automata. There are really only two possible operations, kill/create and maybe a "keep alive". Is that what you were asking for? Or is it what "value" or metric I'm looking for, if that's the case I'm looking for the amount of information/ complexity (of a game of life with init matrix m after n evolutions).

 

[jim mcnamara]

What you are doing is trying to solve some problem. But it looks like you are being diverted from getting to the thing you need, "what I need to look for" by guessing or maybe reading about Conway's game.

What I'm saying is that we could discuss the exact same abstract thing about any computer simulation.
You are getting tangled up in the details of the game, IMO. So I tried to go to a more abstract level.

Complexity is not truly measured when you determine some value for n operations. What if the game terminates before your arbitrary n? Or does not run at all on some input?

Calling @pbuk - can you help? I'm making things worse I think.

 

[paulrk]

ok than it has a different name because I'm searching for the "value" that describes only the changes done to the ("game of life" or any other) matrix by some algorithm. I thought that would be complexity but if it isn't I would be thankful four another term. lol ):

 

[jim mcnamara]

Much better answer. Thanks.
I pinged @pbuk -- another member. I'm a Population Biologist and have dealt with code since 1963. But that doesn't mean I'm always good at helping to solve some kinds of problems.

 

[pbuk]

Thanks for the probing Jim, but I'm still not sure what @paulrk is looking for. Does this paper help (or help formulate a question more precisely)?

It might also help if you could explain why you want whatever it is that you think you want: the shortest route from A to C is not always via B.

 

[Jarvis323]

I want to calculate the kolmogorov complexity of n evolution of a game of game of life(game of life is a kind of cellular automata). I’m not searching for the complexity of a certain pattern of cells but for the total complexity of an initial set of cells over n evolutions. Does it make sense to just add up every operation applied on the game(every creation/deletion of cells)? Since this basically describes all the information that has changed?

Greets

I am not sure exactly what you mean.

Kolmogorov complexity is a measure of complexity for a single instance of a binary string. If you take the configuration of the game of life at some iteration n as the binary string, then you could consider the K-complexity of that string. The K-complexity is the length of the shortest program (counting any input) that will print that string. K-complexity is in general un-computable. That doesn't mean that you can't compute the k-complexity in some instances, only that you are not guaranteed to be able to compute it, and there is no general algorithm you can apply to it. Also K-complexity is dependent on the language that is used.

For the game of life, I don't know how interesting it is to compute the K-complexity of a single configuration. It might be the complexity of predicting that configuration from a prior one that is more interesting.

For K-complexity, the worst case is the print program with the output itself just embedded/hard-coded into the program. This would be the case for example, for a uncompressed string.

With the game of life, you have some trick you could use, because you can derive one configuration from any of it's previous configurations, you at least know that the minimal program is one that includes the logic implementing the update rule, along with any previous configuration. That previous configuration could also be compressed, although you need to factor in the decompression algorithm into the complexity.

 

[Jarvis323]

so I guess the Kolmogorov complexity is not what I'm searching for then. Instead how about just the complexity of a game of life. Or the "amount of information" contained within a game of life with and initial matrix (cell config) over n evolutions?

You need to be clear about complexity. There are many ways to think about complexity. The one that I think you might find the most interesting in this context is non-parallelization logical depth.

https://en.wikipedia.org/wiki/Logical_depth

Logical depth is the minimum number of steps needed to produce the binary string using the minimal program. This is unfortunately also not computable (you even need to know the shortest program and that is not computable in the first place).

But the concept is still worth looking into. If you fix the computational system to be the game of life itself, then it might be interesting. You can ask, for the least complex initial condition (starting configuration with least K-complexity) how many iterations does it take to produce the target iteration?

 

[valenumr]

Let's try this.
For just second:
Forget the name of the program. Forget about iterations.
Without guessing anything tell us - change "X" to some quality, property, or characteristic
"I want to know how to find X in a computer program."

Let's discuss "X" then move on Conway's Life. OK?

Hehe, somebody got their button pushed.

But really, my grad school chair for applied math really was hung up on Conway. It was annoying. Had nothing to do with my studies honestly, because it was more "using computers to approximate hard math problems" with a side of "error estimation", with latter application being "knowing when to stop".

 

[paulrk]

Thanks for the probing Jim, but I'm still not sure what @paulrk is looking for. Does this paper help (or help formulate a question more precisely)?

It might also help if you could explain why you want whatever it is that you think you want: the shortest route from A to C is not always via B.

I’ve already seen that paper but it’s not what I’m searching for, although it is certainly very interesting!

I am not sure exactly what you mean.

Kolmogorov complexity is a measure of complexity for a single instance of a binary string. If you take the configuration of the game of life at some iteration n as the binary string, then you could consider the K-complexity of that string. The K-complexity is the length of the shortest program (counting any input) that will print that string. K-complexity is in general un-computable. That doesn't mean that you can't compute the k-complexity in some instances, only that you are not guaranteed to be able to compute it, and there is no general algorithm you can apply to it. Also K-complexity is dependent on the language that is used.

For the game of life, I don't know how interesting it is to compute the K-complexity of a single configuration. It might be the complexity of predicting that configuration from a prior one that is more interesting.

For K-complexity, the worst case is the print program with the output itself just embedded/hard-coded into the program. This would be the case for example, for a uncompressed string.

With the game of life, you have some trick you could use, because you can derive one configuration from any of it's previous configurations, you at least know that the minimal program is one that includes the logic implementing the update rule, along with any previous configuration. That previous configuration could also be compressed, although you need to factor in the decompression algorithm into the complexity.

That does sound interesting though. If I understood you correctly, the trick you are relating to is basically what I meant. Because, what I suggested (adding the amount of operations over n evolutions, translates to what you call "the minimal program is one that includes the logic implementing the update rule, along any previous configuration[...]" but as you mention next, by leveraging that trick I forget about the compressed configurations(the ones that lead to the same result with a different previous configurations).
Does that somehow make sense?

"you need to be clear about complexity" - I honestly thought there was only one meaning. very naive indeed .

But things start to make sense. I guess it's a misunderstanding on my side. I will just try it the other way around and describe the "value" to you and maybe there is a proper name for that (probably not complexity though lOl :D)

My goal is to rate a certain initial cell configuration over n evolutions. And to start off easy I wanted to rate it by the amount of operations per initial cell configuration over n evolutions. And the name complexity seemed plausible since (at least in my light minded head) a game gets more complex if there are more operations taking place. Maybe a better name would be "information" per game?
pls help .-.

I'm 19 yo and in what you would call high school in Germany and definitely no "theoretic" computer science or math guy so I'm not trusted the concept of "complexity" sorry. Going to be studying cs next year so apperantly there are still new things to learn. Although I'm, as I've said, not a fan of theoretical cs but I guess it's an important component, never needed it though and as an autodidact you don't know things you don't need.

Currently I'm working on a project in which I try to train a reinforced neural net to "play" the game of life. In other words I try to maximize certain characteristics of a game "game of life" (such as [portably wrong name apparently]).
I'm working completely on my own but I try to document everything I do so you can find everything including a README which explains everything on the projects GitHub page: AiPoweredGameOfLife
btw. here(noise.gif) you can see the result of a game of life with the amount of operations maximized by the reinforcement learning algorithm. As expected there is noise. It does get really interesting though when I start maximizing other "game of life" characteristics such as entropy or the "Algorithmic Specified Complexity in the Game of Life" with the final goal to have a potent ai "game of life" research platform to find stable life.
Note that everything, the characteristics to maximize as well as the game of life are exchangeable, that's what makes this setup so great for "research".
greets from Franconia Germany

 

[pbuk]

the final goal to have a potent ai "game of life" research platform to find stable life.

What is your definition of stable life?

 

[paulrk]

What is your definition of stable life?

haha, not going to pretend I would have an exact definition. My intuition in first place was to build this environment (which was a challenge already). Now that I have it all working I'm planning on playing around a bit and am trying to find "stable life". My idea of stable life is anything that a) moves(or has any "activity) b) has a certain size and appearance. That's it. A basic Glider(Subsequent stages of the glider pattern on Conway's Game of Life... | Download Scientific Diagramresearchgate.net) would already be sufficient :D.

As I said I really feel like an engineer at heart and as such my challenge was to build the environment and the platform. I've fun in "researching" but it's not really what turns me on so I'm just playing around right now and maybe, who knows I will find something new.

 

[pbuk]

My goal is to rate a certain initial cell configuration over n evolutions. And to start off easy I wanted to rate it by the amount of operations per initial cell configuration over n evolutions. And the name complexity seemed plausible since (at least in my light minded head) a game gets more complex if there are more operations taking place. Maybe a better name would be "information" per game?
pls help .-.

I don't think you mean you want to rate a certain (i.e. only one particular) initial cell configuration, and there is standard terminology for talking about cellular automata like Conway's Life which you should use.

So let me reprhrase, tell me if I am missing the target:

In the context of Conway's Life, I want to rate (initial) patterns by looking at the resulting pattern after n generations. How do I calculate how 'good' a pattern is?

And here is the problem: you can't. The only way you can tell what will happen to a pattern in the future is to run the algorithm.

I think you should probably do a bit more research on the extensive wiki at https://www.conwaylife.com/wiki/Main_Page, and perhaps look in the forums there to see what others have done that you can draw inspiration from.

 

[Jarvis323]

haha, not going to pretend I would have an exact definition. My intuition in first place was to build this environment (which was a challenge already). Now that I have it all working I'm planning on playing around a bit and am trying to find "stable life". My idea of stable life is anything that a) moves(or has any "activity) b) has a certain size and appearance. That's it. A basic Glider(Subsequent stages of the glider pattern on Conway's Game of Life... | Download Scientific Diagramresearchgate.net) would already be sufficient :D.

As I said I really feel like an engineer at heart and as such my challenge was to build the environment and the platform. I've fun in "researching" but it's not really what turns me on so I'm just playing around right now and maybe, who knows I will find something new.

You might want to look into the study of the game of life as a complex dynamical system.

Nonlinear dynamics of the cellular-automaton ‘‘game of Life’’​

https://journals.aps.org/pre/abstract/10.1103/PhysRevE.48.3345

Conway's game of life is a near-critical metastable state in the multiverse of cellular automata​

https://journals.aps.org/pre/abstract/10.1103/PhysRevE.89.052123

Hidden complexity in Life-like rules​

https://journals.aps.org/pre/abstract/10.1103/PhysRevE.100.052133

A Symbolic Dynamics Perspective of Conway’s Game of Life​

https://ui.adsabs.harvard.edu/abs/2016IJBC...2650035C/abstract

​

 

[paulrk]

Okay, I don’t think it does not make sense to continue from here on. Might be my lack off terminology or just my incompetence in explaining anything.it’s always the same when I ask anybody anything via text on a digital platform. I always get misunderstood. I’m certain that that’s some skill I lack and definitely my fault but it’s always depressing.

I don't think you mean you want to rate a certain (i.e. only one particular) initial cell configuration, and there is standard terminology for talking about cellular automata like Conway's Life which you should use.

So let me reprhrase, tell me if I am missing the target:

In the context of Conway's Life, I want to rate (initial) patterns by looking at the resulting pattern after n generations. How do I calculate how 'good' a pattern is?

And here is the problem: you can't. The only way you can tell what will happen to a pattern in the future is to run the algorithm.

I think you should probably do a bit more research on the extensive wiki at https://www.conwaylife.com/wiki/Main_Page, and perhaps look in the forums there to see what others have done that you can draw inspiration from.

Just a last Note addressing the problem.as I have already said, you misunderstood me.I’m not searching for a mechanism to read without executing the algorithm. I know that I have to execute it, it’s only about what and how to rate after the execution.
And I don’t have a problem, the whole project is working as intended I’m just searching for a name of the mechanism I described earlier. But what I learned so far is that it does not seem to be “complexity”.