There are unreachable states (“gardens of Eden” in the lingo) which means that (per the Garden of Eden Theorem) there exist states which are the successor of more than one possible state. This is an irreversibility (you cannot infer the previous state from the present one), implying an increase of entropy.
While this logic is technically correct its a very weird way to reason, since Garden of Eden patterns are very hard to find in CGL but sets of patterns which converge on the next step are trivially easy to find (e.g. the block and the two common pre-blocks all become blocks on the next step).
I don’t see how that matters: if there exist any states for which it is impossible to infer the previous state, that is a loss of information and therefore an increase in entropy.
I agree it’s hard to know “the” way to map the 2nd law onto an arbitrary universe and see how it applies, but based on some heuristics (checking for irreversibility, agent-perceived flow of time) it seems like Life doesn’t violate it.
I never said you were wrong, I agree with your main point. I was just pointing out that you were reasoning in a very strange way, deriving a simple fact using a very difficult to establish one. People knew that life wasn’t backwards deterministic long before they knew about Garden of Eden patterns.
Sort of like arguing that 8+8 != 27 by appealing to Fermat’s Last Theorem instead of just pointing out that 8+8 = 16 which is a different number to 27.
Good point. I was basing my argument on the backwards non-determinism, and wanted to give the easiest way for readers (who might not have known this about Life) to verify it, so I gave them a term they can look up.
Also, was it really that long before they knew about GoE patterns? Their existence is a trivial implication of multiple states mapping onto the same state. They may not have found specific GoE patters, but they surely had the concept (if not by that name).
Their existence is a trivial implication of multiple states mapping onto the same state. They may not have found specific GoE patters, but they surely had the concept (if not by that name).
I’m not entirely sure it is a trivial implication:
In a sense, you’re right, in that on any finite life-field run on a computer, which has only a finite number of possible states, the existence of convergent patterns does trivially imply Garden of Eden patterns. However, most life-theorists aren’t interested in finite fields, and it was considered possible that Garden of Eden patterns might only work by exploiting weird but uninteresting things that only occur on the boundary.
In an infinite field, you have an uncountable infinity of states, and uncountable sets can have functions defined from them to themselves that are surjective but not injective, so the trivial implication does not work.
On the other hand, if you only look at a finite subset of the infinite field, then you find that knowing the exact contents of a n by n box in one generation only tells you the exact contents of an (n-2) by (n-2) box in the next generation. You have 2^(n^2) patterns mapping to 2^((n-2)^2) patterns, the former is 16^(n-1) times as large as the latter. This makes the existence of convergent patterns trivial, and the existence of Garden of Eden patterns quite surprising.
Another way to look at this is to see that the smallest known Garden of Eden pattern is a lot larger than the smallest pair of convergent patterns.
On the other hand, if you only look at a finite subset of the infinite field, then you find that knowing the exact contents of a n by n box in one generation only tells you the exact contents of an (n-2) by (n-2) box in the next generation. You have 2^(n^2) patterns mapping to 2^((n-2)^2) patterns, the former is 16^(n-1) times as large as the latter. This makes the existence of convergent patterns trivial, and the existence of Garden of Eden patterns quite surprising.
I agree with the GoE part, but does this really single-handedly imply convergent patterns? Two n×n states that produce the same (n-2)×(n-2) successor don’t necessarily have the same effects on their boundaries. Contrapositively, the part about only determining a (n-k)×(n-k) successor applies to any cellular automata that use a (k+1)×(k+1) neighborhood, even reversible ones.
While this logic is technically correct its a very weird way to reason, since Garden of Eden patterns are very hard to find in CGL but sets of patterns which converge on the next step are trivially easy to find (e.g. the block and the two common pre-blocks all become blocks on the next step).
I don’t see how that matters: if there exist any states for which it is impossible to infer the previous state, that is a loss of information and therefore an increase in entropy.
I agree it’s hard to know “the” way to map the 2nd law onto an arbitrary universe and see how it applies, but based on some heuristics (checking for irreversibility, agent-perceived flow of time) it seems like Life doesn’t violate it.
I never said you were wrong, I agree with your main point. I was just pointing out that you were reasoning in a very strange way, deriving a simple fact using a very difficult to establish one. People knew that life wasn’t backwards deterministic long before they knew about Garden of Eden patterns.
Sort of like arguing that 8+8 != 27 by appealing to Fermat’s Last Theorem instead of just pointing out that 8+8 = 16 which is a different number to 27.
Good point. I was basing my argument on the backwards non-determinism, and wanted to give the easiest way for readers (who might not have known this about Life) to verify it, so I gave them a term they can look up.
Also, was it really that long before they knew about GoE patterns? Their existence is a trivial implication of multiple states mapping onto the same state. They may not have found specific GoE patters, but they surely had the concept (if not by that name).
I’m not entirely sure it is a trivial implication:
In a sense, you’re right, in that on any finite life-field run on a computer, which has only a finite number of possible states, the existence of convergent patterns does trivially imply Garden of Eden patterns. However, most life-theorists aren’t interested in finite fields, and it was considered possible that Garden of Eden patterns might only work by exploiting weird but uninteresting things that only occur on the boundary.
In an infinite field, you have an uncountable infinity of states, and uncountable sets can have functions defined from them to themselves that are surjective but not injective, so the trivial implication does not work.
On the other hand, if you only look at a finite subset of the infinite field, then you find that knowing the exact contents of a n by n box in one generation only tells you the exact contents of an (n-2) by (n-2) box in the next generation. You have 2^(n^2) patterns mapping to 2^((n-2)^2) patterns, the former is 16^(n-1) times as large as the latter. This makes the existence of convergent patterns trivial, and the existence of Garden of Eden patterns quite surprising.
Another way to look at this is to see that the smallest known Garden of Eden pattern is a lot larger than the smallest pair of convergent patterns.
I agree with the GoE part, but does this really single-handedly imply convergent patterns? Two n×n states that produce the same (n-2)×(n-2) successor don’t necessarily have the same effects on their boundaries. Contrapositively, the part about only determining a (n-k)×(n-k) successor applies to any cellular automata that use a (k+1)×(k+1) neighborhood, even reversible ones.
This is correct.
Thanks for pointing that out.