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 > Rule 37R experimentation
  Last Thread   Next Thread
Author
Thread Post New Thread    Post A Reply
KaL


Registered: Dec 2005
Posts: 10

Rule 37R experimentation

I wanted to reduce the entropy of binary files using rule 37R (file coimpression application in mind), and found that using reversible rules will never reduce the entropy of the binary stream.

It will maybe fluctuate between the initial value and the maximal entropy value, but it will NEVER decrease.

Also, if you look closely to the values obtained using 37R you will notice that the entropy function for both past and present state is actually periodic.

Does somebody knows why the entropy in 37R (or any other R-rule) will never go under the entropy of the initial configuration ?

Also, is there any cellular automata or dynamical system in which the entropy will decrease under the entropy value of the initial condition ? [and that could be reversed without too much info about initial conditions (Maybe trying to reverse this process, will lead to possible compression alg.)

Thanks.

Attachment: rule37r.zip
This has been downloaded 1125 time(s).

Last edited by KaL on 11-08-2008 at 03:15 AM

Report this post to a moderator | IP: Logged

Old Post 11-06-2008 05:30 AM
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
Todd Rowland
Wolfram Research
Maryland

Registered: Oct 2003
Posts: 113

Wasn't able to view the attachment (is it a special excel file?), so sorry about responding before seeing.

One thing about the rule being reversible is that one can take the last two steps, reverse their order and use them as an initial condition. The rules of this type are self-reversible so you can use 37R to make the reverse evolution of the original.

If the original had entropy increasing, the reversed version has entropy decreasing.

Because high entropy states outnumber low entropy states, when a rule has the behavior of changing entropy it has to increase entropy most of the time. (i.e. one can't break the theorems of information theory with this approach). So almost always one will see entropy follow the second law.

There are some technicalities about the right background for the infinite case, but for the finite case one is theoretically always going to cycle.

Last year I gave a talk on 37R at the NKS conference and there are some tools in those materials.

You can see pictures of typical evolutions from highly ordered states in the book, e.g., p.454. See also the discussion there about how this helps us understand the second law.

Report this post to a moderator | IP: Logged

Old Post 11-07-2008 12:33 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

Thanks, I was actually looking for this document :)
By the way, I changed the attachement, it's an Excel 2003 file now.

Report this post to a moderator | IP: Logged

Old Post 11-08-2008 03:17 AM
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
KaL


Registered: Dec 2005
Posts: 10

Okay...
And uh, what about searching for a Reversible-CA composition so the entropy of byte array is actually reduced ?
Does it make sense, somehow ?

Report this post to a moderator | IP: Logged

Old Post 12-08-2008 04:10 AM
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  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  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