Registered: Dec 2005
Posts: 10

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 860 time(s).

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

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 103

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

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

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