Follow

Thread about Reversible Cellular Automata!

RCA is CA that has exactly one previous and exactly one next state. For example, Conway's Game Of Life is not reversible, because you can have multiple states converge to emptiness. And GoL can have [0; inf) previous states, and exactly one next. Thus, non-reversible CA constantly lose information.

The GIF shows glider in a RCA called "Single rotate", it uses Margolus neighorhood with block of size 2. (Source dmishin.blogspot.com/2013/11/t)

· · Web · 2 · 6 · 10

You can get RCA by constructing it using special methods:
• Margolus neighborhood: replace each 2x2 block according to the rules, then offset a grid diagonaly by 1 block and do the same (first picture)
• Partitioned neighborhood: replace inner block of points according to rules using outer points (second picture) (DOI 10.1007/s11047-017-9655-9)
• Second-order CA (see wikipedia on RCA)

RCA is interesting, because quantum mechanics is reversible too (source: wikipedia), and RCA is closer to our physics than non-reversible ones. This is why losing information in black holes seems like a big problem.

And you can simulate RCA backwards in time! It means that you can get previous states for any of your bit images. Gif shows how random state evolves to the text "hi" in invertible rule called Critters.

Simulator link: dmishin.github.io/js-revca (check out help page, it's nice)

Margolus neighborhood can be extrapolated to more colors, more block size, and more or less dimensions. For example, on first picture this is how 1D invertible automata with block size 2 looks like. Time goes from top to bottom. For 1D 2-block-size automata you get \(2^2!=24\) possible rules.

For it I found that there exists 4 rule transformations that joins similiar rules together. Second picture shows 4 different groups of rules. (source: optozorax.github.io/p/invertib)

This was an interesting short thread! 

@optozorax This automata gif is so calming. I had never heard of reversible computation. Wikipedia says even reversible universal Turing machines exist.

@leonardopacheco I want to append this post with more information, didn't expect it to blow up immediately 😅, I need something like deferred posts.

Sign in to participate in the conversation
Mathstodon

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!