I have this vague impression that makes me think of life as “cheating” by “running backwards”.
In our own universe, quantum coin-flips make it look like one state can lead to more than one new state, and the universe “picks one”. However, this “picking” operation is unnecessary and we say “they all happen” and just consider it one (larger) state evolving into one new (larger) state. This makes me wonder why you can’t do the same thing for every set of laws that claims not to be a bijection between states.
In the game of life, we have cases where several states lead to one state, but not the other way around. From a timeless point of view, there’s still a choice at each transition that deletes information: “why the “initial” state that we chose?”. You can get rid of this by looking at all the initial states that lead to the next state, and now its starting to look like a branching universe run backwards with a cherry picked final state.
In our universe too, we can get things that look like second law violations if we carefully choose the right Everett branch and then look at time ‘backwards’, but because of the way measure works, we don’t consider that important.
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.
The perpetual motion machines you refer to are only that in a very metaphorical sense—they don’t allow an infinite extraction (edit: should be “increase”) of some energy-like metric. They just cycle between the same states, neither increasing nor decreasing entropy because of the full reversibility of such systems.
Okay, so what would be your energy (or disorder) metric in that case and how does the Glider gun violate it? You need to do more than just keep overwriting zeroes with ones.
What do you mean by “energy metric”? If you’re asking for a conserved quantity whose conservation is violated, then you’re not going to get that by definition.
What I mean by having no 2nd law of thermodynamics is that it’s possible to construct a Universal Turing machine that can operate indefinitely without using up any irreplaceable resources.
Something that works as a measure over the state variables for the purposes of Lyapunov’s stability theorems. That is, take a set of state variables that completely define the system, and take some measure that is always non-negative and is an increasing function of every variable. (Lyapunov’s theorem—one version—says that if you can find such a measure, and if it’s strictly non-increasing with time, the system is stable—but this isn’t guaranteed from the definition.)
Maybe you can find one that increases with out bound, but I don’t know what energy metric you have in mind.
What I mean by having no 2nd law of thermodynamics is that it’s possible to construct a Universal Turing machine that can operate indefinitely without using up any irreplaceable resources.
What does that have to do with the 2nd law? There are (physically possible) reversible computers that use no irreplaceable resources, so the fact that something is a Turing machine operating indefinitely does not mean that the 2nd law is being violated.
(I should also point out that Life defines time as an additional property of the universe, rather than a measure on the other properties, which is how time works in this universe. If you carry our universe’s manifestation of time, and check whether that phenomenon exists in Life, it’s not obvious that it does.)
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.
It isn’t true that irreversibility per se implies an increase of entropy—or at least I can’t see how it follows from the definition. (And couldn’t there be a universe whose ‘laws of physics’ were such that states may have multiple successors but at most one predecessor—so that by the ‘irreversibility’ criterion, entropy is decreasing—but which had a ‘low entropy’ beginning like a Big Bang and consequently saw entropy increase over time?)
In any case, it’s not clear (to me at least) how the definition of entropy applies to the Game of Life.
The observation that there would not be anything like the Second Law if our space-time continuum (our universe) did not start out in a very low-entropy state is in Penrose’s Emperor’s New Mind.
You can write a program general enough to be a universe but which doesn’t involve temperature and doesn’t involve inevitable information loss over time. Obviously none of them are going to be generating information from nowhere, but in principle it’s at least possible to break even. (One example, which is rather simple and almost borders on cheating, would be to include an API that would allow any agent to access any bit of information from any point in the past. As far as I can tell, there’s no reason why this wouldn’t be allowed. It would have the aesthetic disadvantage of having a fundamentally directional time dimension, but that shouldn’t cause any real problems to any agents living within it.)
doesn’t involve inevitable information loss over time.
Actually the lack of loss of information over time is precisely what generates the 2nd law of thermodynamics. Specifically, since all information from the past must thus be stored somewhere (unfortunately often in a way that’s hard to access, e.g., the “random” motion of atoms) that continuously leaves less room for new information.
Apparently I don’t actually understand this subject, so I hereby relinquish my previous opinion about it and won’t form a new one (beyond taking better-informed people’s word for it for now) until I’ve learned it better.
You could have a universe though that gains more “room” for entropy faster than it gains entropy… so entropy keeps increasing, but there’s an ever increasing entropy sink, right?
Does Conway’s “Life Universe” have something analogous to the second law of thermodynamics? (Eugine Nier’s comment would suggest otherwise, given that its ‘law of physics’ does not conserve information.)
[Citation needed.]
Conway’s game of life.
Edit: In particular it allows for perpetual motion machines.
I have this vague impression that makes me think of life as “cheating” by “running backwards”.
In our own universe, quantum coin-flips make it look like one state can lead to more than one new state, and the universe “picks one”. However, this “picking” operation is unnecessary and we say “they all happen” and just consider it one (larger) state evolving into one new (larger) state. This makes me wonder why you can’t do the same thing for every set of laws that claims not to be a bijection between states.
In the game of life, we have cases where several states lead to one state, but not the other way around. From a timeless point of view, there’s still a choice at each transition that deletes information: “why the “initial” state that we chose?”. You can get rid of this by looking at all the initial states that lead to the next state, and now its starting to look like a branching universe run backwards with a cherry picked final state.
In our universe too, we can get things that look like second law violations if we carefully choose the right Everett branch and then look at time ‘backwards’, but because of the way measure works, we don’t consider that important.
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.
The perpetual motion machines you refer to are only that in a very metaphorical sense—they don’t allow an infinite extraction (edit: should be “increase”) of some energy-like metric. They just cycle between the same states, neither increasing nor decreasing entropy because of the full reversibility of such systems.
Glider guns produce an endless stream of gliders to give the simplest example.
Okay, so what would be your energy (or disorder) metric in that case and how does the Glider gun violate it? You need to do more than just keep overwriting zeroes with ones.
What do you mean by “energy metric”? If you’re asking for a conserved quantity whose conservation is violated, then you’re not going to get that by definition.
What I mean by having no 2nd law of thermodynamics is that it’s possible to construct a Universal Turing machine that can operate indefinitely without using up any irreplaceable resources.
Something that works as a measure over the state variables for the purposes of Lyapunov’s stability theorems. That is, take a set of state variables that completely define the system, and take some measure that is always non-negative and is an increasing function of every variable. (Lyapunov’s theorem—one version—says that if you can find such a measure, and if it’s strictly non-increasing with time, the system is stable—but this isn’t guaranteed from the definition.)
Maybe you can find one that increases with out bound, but I don’t know what energy metric you have in mind.
What does that have to do with the 2nd law? There are (physically possible) reversible computers that use no irreplaceable resources, so the fact that something is a Turing machine operating indefinitely does not mean that the 2nd law is being violated.
(I should also point out that Life defines time as an additional property of the universe, rather than a measure on the other properties, which is how time works in this universe. If you carry our universe’s manifestation of time, and check whether that phenomenon exists in Life, it’s not obvious that it does.)
You can encode Turing machines in Life.
I’m a little sketchy on how a Turing machine in a universe proves that the universe can violate the 2nd law or lack a 2nd law analog.
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.
It isn’t true that irreversibility per se implies an increase of entropy—or at least I can’t see how it follows from the definition. (And couldn’t there be a universe whose ‘laws of physics’ were such that states may have multiple successors but at most one predecessor—so that by the ‘irreversibility’ criterion, entropy is decreasing—but which had a ‘low entropy’ beginning like a Big Bang and consequently saw entropy increase over time?)
In any case, it’s not clear (to me at least) how the definition of entropy applies to the Game of Life.
The observation that there would not be anything like the Second Law if our space-time continuum (our universe) did not start out in a very low-entropy state is in Penrose’s Emperor’s New Mind.
You can write a program general enough to be a universe but which doesn’t involve temperature and doesn’t involve inevitable information loss over time. Obviously none of them are going to be generating information from nowhere, but in principle it’s at least possible to break even. (One example, which is rather simple and almost borders on cheating, would be to include an API that would allow any agent to access any bit of information from any point in the past. As far as I can tell, there’s no reason why this wouldn’t be allowed. It would have the aesthetic disadvantage of having a fundamentally directional time dimension, but that shouldn’t cause any real problems to any agents living within it.)
Actually the lack of loss of information over time is precisely what generates the 2nd law of thermodynamics. Specifically, since all information from the past must thus be stored somewhere (unfortunately often in a way that’s hard to access, e.g., the “random” motion of atoms) that continuously leaves less room for new information.
Right, sorry, I was referring to subjective information loss. I understand that information is globally conserved.
Won’t help. You could have a universe that includes chronoscopes but still have the problem that it’s continuously filling up with entropy.
Apparently I don’t actually understand this subject, so I hereby relinquish my previous opinion about it and won’t form a new one (beyond taking better-informed people’s word for it for now) until I’ve learned it better.
You could have a universe though that gains more “room” for entropy faster than it gains entropy… so entropy keeps increasing, but there’s an ever increasing entropy sink, right?
That’s another way to do it.
One question one might ask is if our own universe has that property.
Does Conway’s “Life Universe” have something analogous to the second law of thermodynamics? (Eugine Nier’s comment would suggest otherwise, given that its ‘law of physics’ does not conserve information.)