Page 1 of 1

cellular automata

Posted: March 16th, 2013, 12:59 pm
by Karapet
deleted

Re: reversible cellular automata

Posted: March 17th, 2013, 5:19 am
by Mats
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).

Re: reversible cellular automata

Posted: March 17th, 2013, 8:08 am
by Karapet
thank you much!!!!!!

Re: reversible cellular automata

Posted: March 30th, 2013, 1:13 pm
by edf
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.

Re: cellular automata

Posted: March 30th, 2013, 2:28 pm
by Mats
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.

Re: cellular automata

Posted: March 30th, 2013, 6:44 pm
by edf
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.

Re: cellular automata

Posted: March 31st, 2013, 3:34 am
by Mats
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.

Re: cellular automata

Posted: March 31st, 2013, 10:55 am
by edf
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.

Re: cellular automata

Posted: April 1st, 2013, 2:15 am
by Mats
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.