0
$\begingroup$

In order to calculate the Kolmogorov complexity one has to "count" the minimum amount of operations it takes for a certain task(from here). Since the game of life (or cellular automata) outputs are non predictable and not compressible the amounts of rules applied should equal the Kolmogorov complexity? Or does the fact that a certain combination of cells is achievable via different paths make it "compressible" because there is a most efficient path to the combination(but that shouldn't matter if I'm only interested in the Kolmogorov complexity of a certain combination of cells after n iterations)?

thx

Improve this question
$\endgroup$
3
  • $\begingroup$ "the game of life (or cellular automata) outputs are non predictable and not compressible" This is false. The outputs of Game of Life contain no orphan patterns so they are definitely compressible. $\endgroup$
    – Ilkka Törmä
    Commented Oct 30, 2021 at 10:51
  • $\begingroup$ Admittedly I’m not good in explaining things but I also mentioned that “garden of Eden phenomena” here “ Or does the fact that a certain combination of cells is achievable via different paths make it "compressible" because there is a most efficient path to the combination”. But after that I also mentioned that for my question that maybe does not matter because I don’t care about the complexity of the final pattern but for the complexity leading to the pattern $\endgroup$
    – Peter Hackman
    Commented Oct 30, 2021 at 12:38
  • $\begingroup$ See also (possible duplicate): cs.stackexchange.com/questions/145203/… $\endgroup$
    – Discrete lizard ♦
    Commented Nov 27, 2021 at 18:05

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.