cellular automata

For discussion of other cellular automata.
Post Reply
Karapet
Posts: 4
Joined: February 8th, 2013, 10:52 am

cellular automata

Post by Karapet » March 16th, 2013, 12:59 pm

deleted
Last edited by Karapet on March 17th, 2013, 8:15 am, edited 3 times in total.

User avatar
Mats
Posts: 42
Joined: August 10th, 2010, 7:40 am
Location: Stockholm, Sweden

Re: reversible cellular automata

Post by Mats » March 17th, 2013, 5:19 am

For a CA that is only dependent on the state at time t when the state at time t + 1 is computed you have:
b(r, t + 1) = F(N(r, t))

If the CA is time reversible you also have:
b(r, t - 1) = F(N(r, t))

So b(r, t + 1) = b(r, t - 1) for every t, which leads to N(r, t) = N(r, t - 2) for every t. And that holds regardless of the number of states in the CA.

That leaves only two possibillities. Either an RCA oscillates between two states (like B012345678/S) or the state is constant over time (like B/S012345678).

Karapet
Posts: 4
Joined: February 8th, 2013, 10:52 am

Re: reversible cellular automata

Post by Karapet » March 17th, 2013, 8:08 am

thank you much!!!!!!

edf
Posts: 5
Joined: March 29th, 2013, 9:42 am

Re: reversible cellular automata

Post by edf » March 30th, 2013, 1:13 pm

Mats wrote: For a CA that is only dependent on the state at time t when the state at time t + 1 is computed you have:
b(r, t + 1) = F(N(r, t))

If the CA is time reversible you also have:
b(r, t - 1) = F(N(r, t))

So b(r, t + 1) = b(r, t - 1) for every t, which leads to N(r, t) = N(r, t - 2) for every t. And that holds regardless of the number of states in the CA.

That leaves only two possibillities. Either an RCA oscillates between two states (like B012345678/S) or the state is constant over time (like B/S012345678).
****************************************************
You are correct. But you have only shown one way that reversibility won't work. However there are many other ways to achieve exact reversibility. One way involves 2 different functions, one (F) for forward evolution and the other (R) for backward evolution. Then (r, t+1)= F(r, t) and (r, t)=R(r, t+1). Both F and R must be reasonable functions, such as permutations. It won't work for G of L which is clearly irreversible. If F makes everything disappear, R won't brings things back. A better way is to have a second order CA. Unlike Life, 2nd order CA can always be exactly reversible for any (every) rule. In your notation, the state in a 2nd order CA would be {(r, t), (r, t-1)}

For example: (r, t+1)=F(r, t)-(r, t-1) and consequently (r, t-1)=F(r, t)-(r, t+1)

The Salt Model is an example of a 3-D reversible 2nd order CA. The laws of Physics are all reversible, but the reversibility is what is called CPT reversibility, meaning that in addition to time going backwards, left handed things change to right handed (and + goes to - and - to +). The Salt Model is also CPT reversible. While trying to be closer to physics than G of L, it is still as rich and fun while more complicated to look at because it is 3D.

Take a look at "Circular Motion of Strings and Other Surprises" at digitalphilosophy.org and/or busyboxes.org
busyboxes.org lets you try different configurations.

User avatar
Mats
Posts: 42
Joined: August 10th, 2010, 7:40 am
Location: Stockholm, Sweden

Re: cellular automata

Post by Mats » March 30th, 2013, 2:28 pm

It's a pity that the initial post has been deleted. It makes my post appear "out of context", so to say.

The question asked was whether time reversible CA:s exist where the state at t+1 is only dependent on the state at time t . In fact an example of a reversible CA where the state at t+1 is dependent on the state at t and t-1 was given in that post.

I might be wrong, but I thought there is a difference between "time reversible" and "time backtrackable". Then (r, t+1)= F(r, t) and (r, t)=R(r, t+1) would be a time backtrackable system, but not necessarily a time reversible system.

edf
Posts: 5
Joined: March 29th, 2013, 9:42 am

Re: cellular automata

Post by edf » March 30th, 2013, 6:44 pm

The answer to the question you asked is, technically, "Yes". It is easy to difine reversible systems where the state at t+1 is only dependent on the state at time t, and where the state t-1 is, of course, a different function of the state at t. However, those easily defineable reversible systems are usually either unintersting or complicated, compared to the second order ones which are often interesting while not complicated. You can always change a 2nd order rule (that is simple and interesting) into a more complicated first order rule that effectively evolves in a similar manner. So the answer to your question is, sort of, "Yes". Another way that is simple from a mathematician's point of view, is to use complex numbers (Gaussian Integers) to represent the state of a cell. (or to represent the amplitude of a QM oscillator). Going forwards involved multiplying the state by an imaginary number (and rounding to a Gaussian integer). It's really a mathematical disguise that allows a first order system to mimic a 2nd order system.

Some of the interesting consequences of a 2nd order reversible CA (like the the SALT model) are discussed in the paper I mentioned: "Circular Motion of Strings..." (at digitalphilosophy.org). Many physical processes are governed by conservation laws; a CA that has some conservation laws (because of time reversal symmetry), can have some similarities to some aspects of physics. E.g. To my knowledge, Salt CA (busyboxes.org), while very far from being a model of physics, exhibits a few properties and process more like physical phenomena than is the case for other CA.

User avatar
Mats
Posts: 42
Joined: August 10th, 2010, 7:40 am
Location: Stockholm, Sweden

Re: cellular automata

Post by Mats » March 31st, 2013, 3:34 am

edf wrote: Another way that is simple from a mathematician's point of view, is to use complex numbers (Gaussian Integers) to represent the state of a cell. (or to represent the amplitude of a QM oscillator). Going forwards involved multiplying the state by an imaginary number (and rounding to a Gaussian integer).
To time reverse such a system you don't just reverse the time. You also swich the RE and IM parts of the states of every cell. Correct?

Or is the case that you use one function to move forward in time and another function to move backwards? In that case the system would be backtrackable but not reversible - at least as I see it.

edf
Posts: 5
Joined: March 29th, 2013, 9:42 am

Re: cellular automata

Post by edf » March 31st, 2013, 10:55 am

I believe that common usage of the word "reversible", in regard to CA, includes, includes what you are calling "Back Trackable" A system is reversible if there is any process that can unabiguously compute a prior state from a current state. We assume that we can compute a future state from a current state.

For example, imagine that we keep both the initial state in a GOL and a count of the number of iterations. The system is then exactly reversible because when at state n, we can produce state n-1 by restoring the initial state and running forward n-1 steps. Theory is often not very practical.

2nd order systems are reversible if there are 2 functions of the 2nd order state (S(t), S(t-1)), one that computes the future S(t+1)=F1(S(t), S(t-1)) and one that computes the past S(t-1)=F2(S(t), S(t+1))
Or, since addition is the inverse of subtraction: S(t+1)=F(S(t))+S(t-1) S(t-1)=-F(S(t))+S(t+1) Where F is any deterministic function. These examples use arithmetic as opposed to a non-arithmetic function (law) as in GOL.

User avatar
Mats
Posts: 42
Joined: August 10th, 2010, 7:40 am
Location: Stockholm, Sweden

Re: cellular automata

Post by Mats » April 1st, 2013, 2:15 am

edf wrote:For example, imagine that we keep both the initial state in a GOL and a count of the number of iterations. The system is then exactly reversible because when at state n, we can produce state n-1 by restoring the initial state and running forward n-1 steps.
To keep a count of the number of iterations an infinite number of states are needed. One requirement of a CA is that it has a finite number of states, so this construction isn't a CA.

Post Reply