Registered: Oct 2007
Posts: 12

On page 440 in the NKS book a CA is shown that is like a fundamental CA except it looks two states into it's past.

Supposedly any combination can be input as long as two lines are input and the previous states can be worked out, it is as I understand reversable for all inputs not just some, like some of the normal fundamental CA's are only it looks as if logic gates are possible in it.

My question is that if a binary multiplier was created with two 3bit inputs and a 6bit output, 6 was input into the end of the adder where the output goes and the pattern was played backwards what would come out of the input.

It would have to be 1*6, 2*3, 3*2 and 6*1 suggesting that it would not be reversable.

Last edited by alan2here on 05-28-2009 at 12:47 AM

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

Not transparently clear.

The scheme that ensures reversibility is explained on page 437, and its diagram. Obviously reversibility is a restriction on all possible maps of the same range. Here, reversibility for the whole rule follows trivially from the time-symmetry of all of its individual rule-cases. As long as each subrule (case) has the same value above and below, the whole rule must behave the same way whether it is run forward or backward. There is nothing in the mapping itself that favors either direction for the arrow of time, so there can't be any in the resulting behavior.

Not every possible coloring of the 5 cells of each case (center cell 2 steps back, left center and right one step back, and new value of center cell), across all of the cases, would correspond to a reversible rule. They must have the additional property that they have the same upper center and lower center cell values. That still leaves a 3 bit to 1 bit map, as in a traditional 1-range, 2-color CA, since the center cell 2 steps ago is not independent if the rule is to be reversible, but is instead forced to equal the output (next value of center cell).

I hope this helps.

Report this post to a moderator | IP: Logged

Registered: Oct 2007
Posts: 12

Take a look at the one on page 440 and the writing below.
http://www.wolframscience.com/nksonline/page-440

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

I am quite familiar with it. "Every collision" refers to possible structures occuring within the individual rule (state configurations in other words). The rule is in the reversible class because it is contructed according to the scheme explained on page 437, that I cited above.

Report this post to a moderator | IP: Logged

Registered: Oct 2007
Posts: 12

Does that mean that it is not able to be reversed given every valid input or that logic gates despite how it looks cannot be constructed?

Edit: I think I get it from what you said in your post. You can only start from situations like this one and somehow that means you effectivly can't do as I was sugesting?

0101100
0101100

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

Pronouns are ambiguous; here "it".

That specific reverible rule is certainly reversible for all state-configurations. You can start from any configuration of 1s and 0s you like. If you then want to program it, so to speak, to perform a logic calculation in its forward or backward evolution, the program mapping (encoding and decoding I mean) is either going to restrict itself to reversible behaviors or it isn't going to be reversible itself.

There are logical operations that are convergent, that throw out some previous state-information. Reversible operations do not, they are information-preserving. If you "or" 16 terms together and get an answer "yes", you can't reverse that "yes" into the specific branch of the tree of "or"s that got you there. There will be 2^16-1 prior states that would have resulted in that "yes", and from only that ending "yes" you can't possibly tell them apart.

Report this post to a moderator | IP: Logged

Registered: Oct 2007
Posts: 12

Thanks

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 103

The question of how can a reversible system emulate a nonreversible process comes up every now and then. See e.g. the materials from my 2007 NKS conference talk.

One answer is that the extra information can radiate away.

Report this post to a moderator | IP: Logged

Registered: Dec 2005
Posts: 10

What is remarkable with {0,...,255}R rules is that it's always impossible to reduce entropy while using them on binary data... I already tested them all and that's my conclusion. They either exhibit fast entropy growth, or going back and forth between initial entropy state and slightly higher entropy state (periodic behavior)
My question is... Is there any combination of R-Rules which could exhibit entropy reduction (usable for data compression, for example) ?

Report this post to a moderator | IP: Logged