Any interest in reversible rules (and their implications)?

For discussion of other cellular automata.
Post Reply
User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Any interest in reversible rules (and their implications)?

Post by pcallahan » March 14th, 2019, 2:36 pm

I spent a little time years back playing around with Critters, which is one of the most striking reversible CAs I know of. I think it is a very useful way of breaking incorrect human intuition about what makes things reversible or not. In Critters, you can literally crash a bunch of glider-like patterns into a big mess, then run the mess backwards and get them all back.

There was some recent news about "time reversal" that got me thinking again about reversibility.

I think very few people (present company excepted I hope) appreciate the point that there is no fundamental problem with perceiving "time's arrow" within physical laws that are completely reversible (whether or not actual physics is reversible, a point I lack the understanding to address).

I.e., you can embed computation in reversible physics (classical dynamics or a CA like critters). That point is beyond debate. Next, assuming you can embed intelligence in computation (AI), and assuming consciousness is a necessary outcome of self-referential intelligence (strong AI hypothesis), then it follows that conscious beings can inhabit reversible physics. (A couple of jumps in that logic, but if there is anything preventing consciousness in any dynamic systems, there is no reason to think it hinges on reversibility).

With reversible physical laws, you can unscramble an egg provided you haven't lost any information about how it was scrambled. But if you run it backwards from an approximation with even a small error, it will stay scrambled. By contrast, if you scramble an egg from any initial state it will still be scrambled when you're done. That's why "reverse movie" events are so unlikely.

Back to Critters, it is a nearly ideal platform for constructing these unscrambling events. What can't you do? Well, you can't build a CGOL-like glider gun because if you kept running it back to the no-glider state, there would be no way to keep track of how far back it went after that (but maybe that's fixable). You can't build AND and OR gates without figuring out what to do with the information "lost" in the process. For all that, it can still be done (e.g. Fredkin gates). You can even have two isolated systems in a Critters-like universe running opposite to each other according to the ordinary understanding (gliders can uncrash in one region while others crash together some distance away).

Our perception of time's arrow may simply be that our consciousness always works as a forward movie. The flow of time is just the result of the way consciousness itself emerges from computation, combining information and attempting (in a reversible universe) to erase information (by definition impossible) and thus folding it into microstates that we interpret as entropy.

The paragraph above describes the "forward movie". The action consists of the results we want to keep, while the discarded past state is a random-looking cloud. No matter how you started the forward movie (up to small changes) you get a similar outcome and a cloud. When you run the "backward movie", you are extracting past state from the cloud. This works fine as long as the cloud is exactly as you left it. But make a small change to the cloud, and you will not retrieve anything like the past state.

So in short, entropy is fixed, not increasing in a deterministic system, but we model it as increasing in thermodynamic terms because we model the cloud as random, made up of many microstates (corrections welcome in case I have made a big mistake here). In fact, the cloud (because it is deterministic) has a unique microstate preserving a a record of the past.

I'm not sure why this matters so much to me. I think it is because in the outside world, and even in the Life community, it seems to be taken as a given that you need irreversible computation to explain a lot of things. Of course, it is convenient because all the past states need to reside somewhere if they are not discarded. It would be interesting some day to seem the same level of activity put into reversible CAs as we see for CGOL.
Last edited by pcallahan on March 14th, 2019, 2:45 pm, edited 1 time in total.

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: Any interest in reversible rules (and their implications)?

Post by Moosey » March 14th, 2019, 2:41 pm

You also can’t synthesise any periodic objects. I was talking about how limited reversible rules are just the other day at my home.
not active here but active on discord

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Any interest in reversible rules (and their implications)?

Post by pcallahan » March 14th, 2019, 2:47 pm

Moosey wrote:You also can’t synthesise any periodic objects. I was talking about how limited reversible rules are just the other day at my home.
There are ways around this. It depends a bit on initial conditions. You can definitely get oscillators as the result of glider collisions in Critters, though you will necessarily also need to get some gliders out as well.

In effect, Life has the useful property that many things can be turned into empty space, but that is clearly an outcome that loses information and is irreversible. If instead the synthesis collisions emit particles that move away from the synthesis, you can have a reversible CA that appears locally to permit this kind of synthesis. I do not know how to get that to work in Critters, but I do not think the problem is with reversibility as such. What you see as a synthesized oscillator is really a periodic oscillator and some gliders flying off into the distance. Run it in reverse and they will eventually undo the synthesis.

I also had a speculative idea for a glider gun that could exist in a reversible CA. Say it is running with 10 gliders now receding. Reverse it back a full period and you have 9 gliders, 8, etc. Suppose that when you go back to 0, it begins firing gliders in the opposite direction. Now you can reverse it as far back as you want without losing state. Critters cannot do this as described (it conserves the number of live cells) but there is no conflict with the need for reversibility.

Maybe the question is what do infinite growth and synthesis look like in a reversible CA? It is simply incorrect to say "you can't do it." The problem is that unlike Life, you don't have the carpet of empty space to sweep the past under. But there appears to be no problem at all with sending the complete record of a collision off into space. In fact, give that space around the active pattern is empty and infinite, you have something analogous to an open system in which entropy can be reduced locally by sending it outside the system.

Also of relevance: Simulation of irreversible automata. I don't know Toffoli's construction, but this result implies that there is a 3D reversible CA that embeds Life. Presumably an irreversible operation like a vanishing collision of gliders would keep enough information in the 3D embedding to run it in reverse.

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Any interest in reversible rules (and their implications)?

Post by wildmyron » March 15th, 2019, 12:01 am

I think it's fair to say that there's been a lot less exploration of reversible rules on this forum, particularly by the long term active members, but there certainly has been some interest. There are a few discussions which have happened here which I'll just list below for reference.

Reversible Wireless World - a second-order reversible CA along with a few closely related variants. Probably the most active topic on this board relating to reversible CA.

The Single Rotation Rule - A Margolus neighbourhood rule with population conservation.

Salt, a 3D reversible, universal CA - Also referred to as Busy Boxes. Includes some discussion of the 2D Salt rule as well. As noted by Andrew at the end of the thread Golly comes with 3D.lua which can simulate the Busy Boxes CA.

A brief discussion about reversible CA.

I wrote a script to generate Golly ruletables which emulate CA with asynchronous update of cells over 4 generations. Requires an initialisation script to correctly initialise the universe. According to the original request a certain class of these rules are reversible.

There's also been various discussions and explorations of Billiard Ball Machines (BBM), HPP and other lattice gases in a few different threads.

Reversible logic gates but not in a reversible CA:
Challenge: Minimal Toffoli gate - various implementations of Toffoli gates in CGoL.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Any interest in reversible rules (and their implications)?

Post by simsim314 » March 16th, 2019, 1:37 pm

Quantum collapse is technically irreversible (your input is infinite wave function and your output is X location of interference pattern). Before the collapse the time might be reversible indeed. The only model which has complete reversible quantum reality is multiverse, and inside such robust models - you can address CGOL as reversible as well. Take an infinite list of all life states. Think about a snake that covers the whole infinite grid - this makes life state irrational number from inside [0,1] interval. Now CGOL is just a function f:[0,1]->[0,1). The reversion of state y is the subset of all numbers {xi} such that f(xi) = y. Grey goo is trying to work with finite sets of this sort, along the lines of multiverse.

Reversibility in my opinion is not connected with consciousness only turing completeness.

What is interesting in reversible rules to me is cryptography. Using critters as proof of work. Encrypt/decrypt your messages with 1M iterations of critters sounds to me as better idea than other encryption strategies. We can write a small encryption library for this purpose and try to compete with the big names.

EDIT @wildmyron I can't seem to find computational and construction universal reversible rules (assume you get half plane filled with "particles" and the other half empty).

I also couldn't find even the simplest Salt construction, someone posted 3d patterns - but I'm looking for 2d reversible universal CA.

EDIT2 @pcallahan I think this could be very helpful for the margolius 2d tiling.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Any interest in reversible rules (and their implications)?

Post by pcallahan » March 31st, 2019, 1:45 am

This is mostly to record my own thoughts, but I would appreciate any discussion.

I am finally trying to pin down the known reversibility results in specific terms as they could apply to "Life-like" CA (something that has confused me over the years). I think a useful analogy is "heat" and "cooling", capturing some of the issues of entropy but in a more mechanical sense of what you need to embed computation in reversible rules--mostly, you need a way to remove the "heat" consisting of lost states that irreversible rules discard automatically. So as I work through this, I think "Aha, that's where we put the cooling fins!"

Start with wikipedia on Reversible cellular automata (RCA in the following).

CGOL, which is irreversible, can be embedded in a 3D RCA. Another way to make an RCA from any CA is to use a second-order CA. "However, the behavior of the reversible cellular automaton determined in this way may not bear any resemblance to the behavior of the cellular automaton from which it was defined."

Hertling 1998 proves (though I have not tried to follow the reasoning) that a 2D CA with a Garden of Eden, like Life, cannot be embedded in a 2D RCA, at least not by preserving locality in the way we'd expect (a key restriction that we may want to reconsider).

So with respect to CGOL (Conway's Game of Life), that leaves us with the 3D embedding. Rather than work through the theory, let's just start with something simple and tangible. We have a 3D integer grid ℤ×ℤ×ℤ or in other words, triples (i, j, k) of integers, and for each triple, there is a cell C(i,j,k) 0 ("dead") or 1 ("live").

Define the CGOL transition L(i, j, k) as applied to the cell C(i,j,k) and its neighbors C(i±1, j±1, k), C(i±1, j, k), C(i, j±1,k). (I'll assume everyone here can write this function out.)

Apply the above transition rule directly, and you get CGOL on each layer separately for some fixed value of k. It is irreversible. One way to embed it in a reversible rule (there are other ways) is to use a Margolus-like transition between layers. Apply this rule at each step, alternating between even and odd values of k (⊕ is xor):

(C(i, j, k), C(i, j, k+1)) → (C(i, j, k), L(i, j, k)⊕C(i, j, k+1))

This rule is its own inverse. That is, whatever the particulars of L(i, j, k), it cancels itself out when you apply the rule twice. (It won't help find a previous step in CGOL, but that's not the point.)

Now place the initial Life pattern in the plane k=0. Fill all other planes with 0. (This approach will work for any CA rule in which all zeros produce zeros). Abuse the definition of L to apply to an entire pattern p, and extend ⊕ to apply to planes, and 0 to an entire plane full of zeros. Then the first generation of the rule consists of these layers:

... 0, 0, 0, 0, p, 0, 0, 0, 0, ...

Apply the rule for even k, and the next generation is:

... 0, 0, 0, 0, p, L(p), 0, 0, 0, 0, …

Apply for odd k, and we get:
… 0, 0, 0, 0, L(p), L(p), L(L(p)), 0, 0, 0, ...

Again for even k.
… 0, 0, 0, 0, L(p), L(L(p))⊕L(p), L(L(p)), L(L(L(p))), 0, 0, ...

Note that layer k at step k always has the kth generation of CGOL. So it is a faithful embedding of Life rules. The way it implements reversibility is just to keep an entire history of past generations, though some of them get scrambled with xor. The final generation is always available because it is xor’d with 0. (Note that if you reverse the rule to generations prior to 0 you get the exact same results.)

This is not especially interesting from the standpoint of reversibility, but it illustrates the idea of adding an explicit “cooling system” to an irreversible rule to make it reversible. In this case, the cooling fins are on every Life cell. Effectively, it accepts “cool” zeros and produces “hot” pseudorandom bits for all the information it throws away in the process of applying Life rules.

Moving to 3D is kind of a cheat because we are really just storing history in an obvious way. A more interesting question is whether you could implement unit Life cell in a less contrived RCA like critters. The problem here is the result of Hertling 1998, but maybe the situation is not quite settled.

What I’m imagining here (in addition to an energy source to deal with live cell conservation in Critters) is a set of devices with explicit cooling systems to remove the excess gliders that are always emitted when computing an irreversible function. Instead of sending the “heat” off into a convenient 3rd dimension, we could have channels around cells to carry off history/wasted information/heat.

There is still a problem (not surprisingly, since we can’t get a truly local embedding according to Hertling 1998). Consider an n×n grid of Life cells. This throws away O(n^2) bits every generation, but any 2D disposal system can only remove O(n) of them around the boundary every generation.

The problem is not fatal if you accept a slowdown. Instead of calculating generations at a constant clock tick, a reversible Life cell could determine first if there is room in the cooling channel, like waiting for a spot in a garbage conveyor. Until there is room, it would hold its state and stay dormant. This could be adaptive to the cell values. For instance, empty regions of Life are reversible, so the “heat” is proportional to the number of live cells in sparse patterns.

So in short, I think Critters could simulate Life with an infinite source of new gliders and an O(n) slowdown, where n is the number of live cells. It would be a difficult construction assuming its possible.

Finally, it’s worth observing that real chips are more or less 2D and require 3D space to eliminate waste heat. Ordinary engineering does not remove heat in anything like the controlled fashion described above, but it might become necessary e.g. for nanotechnology.
Last edited by pcallahan on April 1st, 2019, 9:51 am, edited 2 times in total.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Any interest in reversible rules (and their implications)?

Post by pcallahan » March 31st, 2019, 11:55 am

Follow up (and new post) on the general method of making a reversible d+1 CA used above. I am not sure what the standard method is, and settled on using the 1D Margolus transition after convincing myself I could also make a second-order CA but XOR after shifting layers (so we are XORing with 0s and not a previous state with values). I'm sure there are other ways, but I like the simplicity of the 1D Margolus neighborhood.

Am I alone in trusting a computer example more than a mathematical proof? I always worry that I will fudge some step in the argument. So I decided to use the approach to convert an irreversible 0D CA (or just a state machine) to a 1D reversible CA and then run an example I could look at.

The 0D rule uses states corresponding to non-negative integers (finite-bounded to make it an FSA) and applies:
0 → 0
n → n-1 if n>0

So it counts down to 0 and then stays at 0 (at which point it is irreversible). Call that rule t(n) and define an array v of values. Then the reversible CA rule is (applied alternate for even and odd i):
(v[i+0], v[i+1]) → (v[i+0], t(v[i+0])⊕v[i+1])
In this case ⊕ is applied to integers by treating them as bit vectors containing their binary representation.

For implementing with fixed-length arrays, it is reasonable to add a periodic boundary condition. The CA rule is still reversible in that case, but it comes with a penalty in terms of simulating the original rule. In general, we can read the state of the original CA as long as we are XORing with 0. With periodic boundaries, we eventually collide with the past history ("heat") at which point, we lose the state that we really want to run in the original rule. Again, my intuition (and I find it useful at least) is to think of this as converting an irreversible rule like Life to a reversible rule with infinite cooling capacity. Once you set a finite limit, it only works until your immediate surroundings reach a state of high entropy (only in a rough sense, though, because it is fully reversible, but it is pseudorandom).

Some Python code to illustrate converting 0D to 1D:

Code: Select all

def transition(n):
  return n - 1 if n > 0 else 0


def reversible_rule(a, b):
  return a, transition(a) ^ b


def apply_rule(values, offset):
  for i in range(offset % 2, len(values), 2):
    b_ix = (i + 1) % len(values)
    values[i], values[b_ix] = reversible_rule(values[i], values[b_ix])
  return 1 - offset


def to_string(values):
  return  " ".join(["%d" % x for x in values])

values = [6, 0] +[0] * 10

print(to_string(values))
# run 10 steps of the rule
offset = 0
for step in range(10):
  offset = apply_rule(values, offset)
  print(to_string(values))

print("now reverse")
# now reverse and run 10 in reverse
offset = 1 - offset
for step in range(10):
  offset = apply_rule(values, offset)
  print(to_string(values))
The repl.it link

Output:

Code: Select all

6 0 0 0 0 0 0 0 0 0 0 0
6 5 0 0 0 0 0 0 0 0 0 0
6 5 4 0 0 0 0 0 0 0 0 0
6 0 4 3 0 0 0 0 0 0 0 0
6 0 4 3 2 0 0 0 0 0 0 0
6 5 4 0 2 1 0 0 0 0 0 0
6 5 0 0 2 1 0 0 0 0 0 0
6 0 0 0 2 0 0 0 0 0 0 0
6 0 0 0 2 0 0 0 0 0 0 0
6 5 0 0 2 1 0 0 0 0 0 0
6 5 4 0 2 1 0 0 0 0 0 0
now reverse
6 5 0 0 2 1 0 0 0 0 0 0
6 0 0 0 2 0 0 0 0 0 0 0
6 0 0 0 2 0 0 0 0 0 0 0
6 5 0 0 2 1 0 0 0 0 0 0
6 5 4 0 2 1 0 0 0 0 0 0
6 0 4 3 2 0 0 0 0 0 0 0
6 0 4 3 0 0 0 0 0 0 0 0
6 5 4 0 0 0 0 0 0 0 0 0
6 5 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0 0
Last edited by pcallahan on December 4th, 2019, 3:38 am, edited 1 time in total.

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Any interest in reversible rules (and their implications)?

Post by wildmyron » November 13th, 2019, 3:07 am

Whilst exploring literature relating to Reversible Partitioned Cellular Automata I came across a paper describing self-replication in a 2D RPCA labelled SR_8. In this CA, cells are divided into 5 partitions (4 for von Neumann neighbourhood plus centre) with each partition being in one of 8 states. This is equivalent to a regular CA on the von Neumann neighbourhood with 32,768 states[*]. The self replicating worms are modelled on Langton's Loops and are programmed with a sequence of commands which controls their shape, the position of their daughters, and a branching command which facilitates replication. Details: Self-reproduction in a reversible cellular space, K. Morita and K. Imai, Theoretical Computer Science, Vol 168 (2), 1996, pp 337-366.

As I understand it, the local function of the CA is defined only for the configurations of interest, ensuring that there are no duplicated resulting states. This implies that the remaining undefined transitions can be chosen to ensure the local function of the PCA is bijective, and therefore the global CA is reversible.

This is quite a different beast to the "Life-like" CA described in the previous few posts, but I though it was relevant to this thread. There are also various other papers by the same research group which describe computation universal RPCA with only 2-states on a variety of neighbourhoods. Some of these have been discussed on the Partitioned Cellular Automata thread.

[*] Corrected number of states of equivalent CA on von Neumann neighbourhood. Thank you PHPBB12345.
Last edited by wildmyron on November 14th, 2019, 11:46 pm, edited 1 time in total.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

User avatar
PHPBB12345
Posts: 1096
Joined: August 5th, 2015, 11:55 pm
Contact:

Re: Any interest in reversible rules (and their implications)?

Post by PHPBB12345 » November 14th, 2019, 11:24 pm

wildmyron wrote:
November 13th, 2019, 3:07 am
This is equivalent to a regular CA on the von Neumann neighbourhood with 390,625 states.
Actually is 32768 states.

Post Reply