<p>Edit: Please see the comments for why this does not address the question, however, I think I should not delete it in order to preserve the discussion...</p>

<p>--</p>

<p>Not an expert, but my impression is that <strong>reversible</strong> computation does not by itself result in a change in entropy: the amount of information in the system has not changed, only the format in which it is stored. In other words such processes obey the second law with only a weak inequality, not a strict one. To get a strict increase in entropy, one has to erase or destroy information, i.e. irreversible computation. I don't see why the rest of the details in your question -- two dimensions, cellular automata, chaos, recurrence -- would affect this.</p>

<p>Happy to be corrected by any experts, however.</p>

CC BY-SA 3.0
2018-03-20T19:16:45.173Z
-1. Erasing information decreases the amount of entropy a system, so irreversible cellular automata typically decrease in entropy.
Joseph Van Name
CC BY-SA 3.0
2018-03-20T22:07:51.897Z
@35093731895230467514051, I'm confused.  In the question you say that the Critters cellular automaton is reversible.  Which is it, reversible or irreversible?
D.W.
CC BY-SA 3.0
2018-03-20T23:47:49.500Z
Critters is reversible.
Joseph Van Name
CC BY-SA 3.0
2018-03-21T01:53:26.423Z
Technically, reversible computation indeed does not change entropy. But the OP is talking about macroscopic entropy, not microscopic entropy.
Peter Shor 
CC BY-SA 3.0
2018-03-21T09:54:21.033Z
@PeterShor Could you explain what is macroscopic entropy, and how can it increase in a reversible way?
Emil Jeřábek
CC BY-SA 3.0
2018-03-21T10:51:38.600Z
Macroscopic entropy is when you ignore microstates. So divide the grid into blocks, and count the number of "on" cells in each block, and compute the entropy of these numbers. This is what physicists usually mean by entropy when they talk about the real world. [See Wikipedia](https://en.wikipedia.org/wiki/Microstate_(statistical_mechanics)). If this is what the OP is asking about, this "answer" doesn't actually address the question;.
Peter Shor 
CC BY-SA 3.0
2018-03-20T17:25:57.520Z
2018-03-21T13:52:11.507Z
2018-03-21T13:52:11.507Z
usul
<p>So the two-dimensional reversible cellular automaton Critters (which you can simulate online at <a href="https://dmishin.github.io/js-revca/index.html#" rel="nofollow noreferrer">https://dmishin.github.io/js-revca/index.html#</a>) on the Torus does not seem to follow the second law of thermodynamics. For example, if a $10\times 10$ block in the torus is filled with random data and the cells outside of this $10\times 10$ block are all zero, then there is a good chance that after several million generations on a $256\times 256$ grid, one can see the cellular automaton return to its original state. Why is the Poincare recurrence time for the reversible cellular automata Critters so small in this case? The rule Critters is universal for reversible computation, and it exhibits chaotic behavior that one would expect in a reversible cellular automaton. Therefore, one would expect that after running the cellular automaton for enough generations, the entropy would constantly increase and hence one would need to wait a very long time (much longer than several million generations) to observe the Poincare recurrence. Is there any explanation for this phenomenon? Are there other chaotic, reversible, universal cellular automata of dimension 2 that exhibit this phenomenon?</p>

CC BY-SA 3.0
2018-03-20T00:38:21.733Z
good q for mo site.
Turbo
CC BY-SA 3.0
2018-03-21T16:08:39.463Z
I made some experiments with small configurations (in a central grid of 5x5) and most of them have a small period. Probably with a 10x10 initial cfg, you cannot build complex enough "gliders" or "structures". When the gliders traverse the borders and hit back the central core they are usually absorbed and after a few generations the whole central mass reverses its evolution (the gliders are throwed out, and the whole computation reverses back to the original state)....[cont.]
Marzio De Biasi
CC BY-SA 3.0
2018-03-21T16:09:03.437Z
[cont.]... So I bet that in this case we are simply observing a reversible computation that reverses itself; and it has nothing to do with the Poincarre recurrence.
Marzio De Biasi
CC BY-SA 3.0
2018-03-23T11:55:01.267Z
I did a handful of experiments with $10 \times 10$ blocks, and never observed anything that looked like it was at all likely to cycle. Given @Marzio's comment, I suspect that you are observing a small-number phenomenon, and that if you took a random $20 \times 20$ block in a $256 \times 256$ grid, the Poincare recurrence time would be around as large as you expect.
Peter Shor 
CC BY-SA 3.0
2018-03-24T05:16:39.463Z
@PeterShor, this is not the first time I have observed a low period phenomenon. At https://crypto.stackexchange.com/q/55518/34766, I have observed that the composition of two involutions which are related in a special way often has a low mean Poincare recurrence time while in general, the composition of two unrelated involutions would have a long Poincare recurrence time.
Joseph Van Name
CC BY-SA 3.0
2018-03-24T05:21:04.140Z
Notice how the rule Critters is the composition of two functions where one function is for even generations and the other function is for odd generations; both the even and odd generation functions on the block are nearly involutions, so I predict that I am observing a similar phenomenon with Critters as I have with the composition of two involutions.
Joseph Van Name
CC BY-SA 3.0
2018-03-24T05:47:21.703Z
The low recurrence time phenomenon also holds for the similar rule 15,14,13,3,11,5,6,8,7,9,10,4,12,2,1,0 which happens to be the composition of two involutions.
Joseph Van Name
CC BY-SA 3.0
2018-03-25T21:36:07.793Z
@PeterShor. I am perplexed as to why you have not observed a cycle on $10\times 10$ blocks while Marzio and I have observed low periodicity. Could you give some more details on your experiments so that we are on the same page?
Joseph Van Name
CC BY-SA 3.0
2018-03-25T21:37:50.147Z
@MarzioDeBiasi. The low periodicity phenomenon also hold when the initial state consists of very complex gliders flying in different directions.
Joseph Van Name
<cellular-automata><reversible-computing>
Why don't the critters ever age?
Joseph Van Name
# Why don't the critters ever age?

(Asked by: username_0 on 2018-03-19)

So the two-dimensional reversible cellular automaton Critters (which you can simulate online at <https://dmishin.github.io/js-revca/index.html#>) on the Torus does not seem to follow the second law of thermodynamics. For example, if a $10\times 10$ block in the torus is filled with random data and the cells outside of this $10\times 10$ block are all zero, then there is a good chance that after several million generations on a $256\times 256$ grid, one can see the cellular automaton return to its original state. Why is the Poincare recurrence time for the reversible cellular automata Critters so small in this case? The rule Critters is universal for reversible computation, and it exhibits chaotic behavior that one would expect in a reversible cellular automaton. Therefore, one would expect that after running the cellular automaton for enough generations, the entropy would constantly increase and hence one would need to wait a very long time (much longer than several million generations) to observe the Poincare recurrence. Is there any explanation for this phenomenon? Are there other chaotic, reversible, universal cellular automata of dimension 2 that exhibit this phenomenon?

**Tags:** cellular-automata, reversible-computing

> **Comments:**
> **username_1**: good q for mo site.  
> **username_2**: I made some experiments with small configurations (in a central grid of 5x5) and most of them have a small period. Probably with a 10x10 initial cfg, you cannot build complex enough "gliders" or "structures". When the gliders traverse the borders and hit back the central core they are usually absorbed and after a few generations the whole central mass reverses its evolution (the gliders are throwed out, and the whole computation reverses back to the original state)....[cont.]  
> **username_2**: [cont.]... So I bet that in this case we are simply observing a reversible computation that reverses itself; and it has nothing to do with the Poincarre recurrence.  
> **username_3**: I did a handful of experiments with $10 \times 10$ blocks, and never observed anything that looked like it was at all likely to cycle. Given @Marzio's comment, I suspect that you are observing a small-number phenomenon, and that if you took a random $20 \times 20$ block in a $256 \times 256$ grid, the Poincare recurrence time would be around as large as you expect.  
> **username_0**: @PeterShor, this is not the first time I have observed a low period phenomenon. At https://crypto.stackexchange.com/q/55518/34766, I have observed that the composition of two involutions which are related in a special way often has a low mean Poincare recurrence time while in general, the composition of two unrelated involutions would have a long Poincare recurrence time.  
> **username_0**: Notice how the rule Critters is the composition of two functions where one function is for even generations and the other function is for odd generations; both the even and odd generation functions on the block are nearly involutions, so I predict that I am observing a similar phenomenon with Critters as I have with the composition of two involutions.  
> **username_0**: The low recurrence time phenomenon also holds for the similar rule 15,14,13,3,11,5,6,8,7,9,10,4,12,2,1,0 which happens to be the composition of two involutions.  
> **username_0**: @PeterShor. I am perplexed as to why you have not observed a cycle on $10\times 10$ blocks while Marzio and I have observed low periodicity. Could you give some more details on your experiments so that we are on the same page?  
> **username_0**: @MarzioDeBiasi. The low periodicity phenomenon also hold when the initial state consists of very complex gliders flying in different directions.  

---

## 1 answers

### Answer by username_4 on 2018-03-20. Score: 1

Edit: Please see the comments for why this does not address the question, however, I think I should not delete it in order to preserve the discussion...

--

Not an expert, but my impression is that **reversible** computation does not by itself result in a change in entropy: the amount of information in the system has not changed, only the format in which it is stored. In other words such processes obey the second law with only a weak inequality, not a strict one. To get a strict increase in entropy, one has to erase or destroy information, i.e. irreversible computation. I don't see why the rest of the details in your question -- two dimensions, cellular automata, chaos, recurrence -- would affect this.

Happy to be corrected by any experts, however.

> **Comments:**
> **username_0**: -1. Erasing information decreases the amount of entropy a system, so irreversible cellular automata typically decrease in entropy.  
> **username_5**: @35093731895230467514051, I'm confused.  In the question you say that the Critters cellular automaton is reversible.  Which is it, reversible or irreversible?  
> **username_0**: Critters is reversible.  
> **username_3**: Technically, reversible computation indeed does not change entropy. But the OP is talking about macroscopic entropy, not microscopic entropy.  
> **username_6**: @PeterShor Could you explain what is macroscopic entropy, and how can it increase in a reversible way?  
> **username_3**: Macroscopic entropy is when you ignore microstates. So divide the grid into blocks, and count the number of "on" cells in each block, and compute the entropy of these numbers. This is what physicists usually mean by entropy when they talk about the real world. [See Wikipedia](https://en.wikipedia.org/wiki/Microstate_(statistical_mechanics)). If this is what the OP is asking about, this "answer" doesn't actually address the question;.  

---

