A New Kind of Science: The NKS Forum (http://forum.wolframscience.com/index.php)
- Pure NKS (http://forum.wolframscience.com/forumdisplay.php?forumid=3)
-- Rule 37R experimentation (http://forum.wolframscience.com/showthread.php?threadid=1601)

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.

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.

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

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 ?