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?

  • 1
    $\begingroup$ good q for mo site. $\endgroup$ – 1.. Mar 20 '18 at 0:38
  • 2
    $\begingroup$ 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.] $\endgroup$ – Marzio De Biasi Mar 21 '18 at 16:08
  • 3
    $\begingroup$ [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. $\endgroup$ – Marzio De Biasi Mar 21 '18 at 16:09
  • $\begingroup$ 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. $\endgroup$ – Peter Shor Mar 23 '18 at 11:55
  • $\begingroup$ @PeterShor, this is not the first time I have observed a low period phenomenon. At 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. $\endgroup$ – Joseph Van Name Mar 24 '18 at 5:16

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.

  • $\begingroup$ -1. Erasing information decreases the amount of entropy a system, so irreversible cellular automata typically decrease in entropy. $\endgroup$ – Joseph Van Name Mar 20 '18 at 19:16
  • 1
    $\begingroup$ @35093731895230467514051, I'm confused. In the question you say that the Critters cellular automaton is reversible. Which is it, reversible or irreversible? $\endgroup$ – D.W. Mar 20 '18 at 22:07
  • $\begingroup$ Critters is reversible. $\endgroup$ – Joseph Van Name Mar 20 '18 at 23:47
  • 1
    $\begingroup$ Technically, reversible computation indeed does not change entropy. But the OP is talking about macroscopic entropy, not microscopic entropy. $\endgroup$ – Peter Shor Mar 21 '18 at 1:53
  • 1
    $\begingroup$ 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. If this is what the OP is asking about, this "answer" doesn't actually address the question;. $\endgroup$ – Peter Shor Mar 21 '18 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.