wolframscience.com

A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > Pure NKS > Reversable CA 37R Question
  Last Thread   Next Thread
Author
Thread Post New Thread    Post A Reply
alan2here


Registered: Oct 2007
Posts: 12

Reversable CA 37R Question

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

Old Post 05-28-2009 12:41 AM
alan2here is offline Click Here to See the Profile for alan2here Visit alan2here's homepage! Edit/Delete Message Reply w/Quote
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

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

Old Post 05-28-2009 08:45 PM
Jason Cawley is offline Click Here to See the Profile for Jason Cawley Click here to Send Jason Cawley a Private Message Edit/Delete Message Reply w/Quote
alan2here


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

Old Post 05-28-2009 11:45 PM
alan2here is offline Click Here to See the Profile for alan2here Visit alan2here's homepage! Edit/Delete Message Reply w/Quote
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

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

Old Post 05-29-2009 11:39 PM
Jason Cawley is offline Click Here to See the Profile for Jason Cawley Click here to Send Jason Cawley a Private Message Edit/Delete Message Reply w/Quote
alan2here


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

Old Post 05-30-2009 11:11 AM
alan2here is offline Click Here to See the Profile for alan2here Visit alan2here's homepage! Edit/Delete Message Reply w/Quote
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

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

Old Post 05-30-2009 02:00 PM
Jason Cawley is offline Click Here to See the Profile for Jason Cawley Click here to Send Jason Cawley a Private Message Edit/Delete Message Reply w/Quote
alan2here


Registered: Oct 2007
Posts: 12

Thanks

Report this post to a moderator | IP: Logged

Old Post 05-30-2009 05:04 PM
alan2here is offline Click Here to See the Profile for alan2here Visit alan2here's homepage! Edit/Delete Message Reply w/Quote
Todd Rowland
Wolfram Research
Maryland

Registered: Oct 2003
Posts: 113

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

Old Post 06-17-2009 03:21 PM
Todd Rowland is offline Click Here to See the Profile for Todd Rowland Click here to Send Todd Rowland a Private Message Click Here to Email Todd Rowland Edit/Delete Message Reply w/Quote
KaL


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

Old Post 08-16-2009 02:16 PM
KaL is offline Click Here to See the Profile for KaL Click here to Send KaL a Private Message Click Here to Email KaL Edit/Delete Message Reply w/Quote
Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread


 

wolframscience.com  |  wolfram atlas  |  NKS online  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-14 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives