Natural Information Entropy of CGoL

[quintopia]

I've just finished reading Susskind's The Black Hole War in which the maximum information entropy of any volume of space is computed (a bound which is met by black holes). So this got me to thinking about what exactly the information entropy of GoL might be. It's obvious that n cells are capable of storing n bits of information, but the question is not how much information they /could/ store but how much they usually /do/.

So let's say that the "natural" information entropy of one cell is calculated as "the fraction of all configurations of n contiguous cells that can occur in some pattern that is not a Garden of Eden and does not require a Garden of Eden ancestor, as n goes to infinity."

We can approximate this as the log base 2*mu of the number of configurations meeting the above requirements for n cells, divided by n, as n goes to infinity. (where mu is the polyomino constant, 3.96<mu<4.64)

Now, there is no guarantee that this limit should exist, but neither can I see any reason to believe that if it does, it is equal to 1 (although for small values of n, we will obviously get 1). It is clear to me that actually calculating this value or proving that it has a particular value would be quite difficult. Does anyone have any insights or known past results along this line?

More questions:
Can we restrict ourselves to square regions and still get the same results?
Exactly how difficult is it to determine that a given soup could have a non-GoE ancestor? (my gut here says "nearly impossible")
Is there a way to sample patterns with a degree of randomness that seems almost uniform or approaches uniformity such that it is impossible to sample a GoE?

[137ben]

Rather than basing your calculations around polyominoes, it may be a good idea to use polyplets, as they are more natural in the Moore neighborhood.

Can we restrict ourselves to square regions and still get the same results?

You might get a different value for each sized square. The limit as the side-length approaches infinity should be the value we seek.

Exactly how difficult is it to determine that a given soup could have a non-GoE ancestor? (my gut here says "nearly impossible")

An exhaustive search of possible predecessors can easily produce every parent of a bounded pattern. From there, simply search for every grandparent, ect until you go back n generations. Unfortunately, the number of potential predecessors to be searched grows very quickly with n, making this method unfeasible for sampling the limit as n--> infinity (unless the NIE converges very quickly. In that case, the above method could give a decent approximation of the true NIE, which might work as a starting point for proving bounds).

[calcyman]

An upper bound for the information entropy of one cell is log(2^121-5)/log(2^121).

http://www.wolframalpha.com/input/?i=lo ... 2%5E121%29

(There are at least five known 11*11 gardens of Eden.)


This is very close to unity, for obvious reasons.

[quintopia]

Rather than basing your calculations around polyominoes, it may be a good idea to use polyplets, as they are more natural in the Moore neighborhood.

Good point. This will the log base higher, obviously. I should look up the bounds on the growth rate of the polyplet sequence.

The limit as the side-length approaches infinity should be the value we seek.

What leads you to believe that the limit of the sequence for squares will be the same as the limit of the sequence for polyominoes or polyplets?

From there, simply search for every grandparent, ect until you go back n generations.

Unfortunately, we can't even say that n generations is enough. It may be that the smallest pattern in which a particular contiguous region has a particular configuration and the pattern is descended from some non-GoE is huge, and that many smaller patterns containing it reduce to GoEs thousands upon thousands of generations before.

(There are at least five known 11*11 gardens of Eden.)

It is true, yes, that any pattern containing a GoE is itself a GoE? Or is this only true of some GoEs?

[calcyman]

It is true, yes, that any pattern containing a GoE is itself a GoE?

Correct. That is why I can validly assert the upper bound of log(2^121-5)/log(2^121) bits per cell.

[quintopia]

No, the bound is still too low given what we know. You can't use 121 as your denominator if we're going to use polyonimoes/polyplets. However, if you are using (without saying) mu as the base your logarithm, then yes, that would be correct.

[calcyman]

You can't use 121 as your denominator if we're going to use polyonimoes/polyplets.

I'm talking about configurations in general (power sets of Z^2), not polyominoes or polyplets.

However, if you are using (without saying) mu as the base your logarithm, then yes, that would be correct.

The base of the logairthm is irrelevant, since log_a(x)/log_a(y) = log_b(x)/log_b(y) (for all real a,b,x,y > 0).


If we're using base 2, then my logic proceeds as follows:

At most 2^121-5 states can exist in an 11*11 box.
At most log_2(2^121-5) bits can be stored in an 11*11 box.
At most log_2(2^121-5)/121 bits can be stored in a single cell.

[quintopia]

And here's my counterargument: Although that cell can't store more log_2(2^121-5) bits of information with respect to its contribution toward any particular 11x11 square it is in, it may be storing some small amount of information with respect to a polyplet not contained in that square, for instance a diagonal line of 121 cells passing through it, which I would expect would be able to take on all 2^121 configurations. I'm not yet convinced we can state any bounds that don't take into consideration every possible configuration.

I will agree that, over all configurations of 121 cells, at least five of those are not possible, but I'm not convinced that we can reduce the question to squares.

I might be missing something, though, so forcibly correct me if you see it.

[calcyman]

Again, I'm considering infinite planes, not polyplets. Let f(n) be the number of non-Garden-of-Eden states a n*n torus can occupy. As n approaches infinity, the value of log(f(n))/log(2^(n^2)) will approach a constant, k, slightly less than unity.

There are at least 51992 unreachable configurations in an 11*11 box, leading to a tighter upper bound on k.

Indeed, 30/56 < k < log(2^121-51992)/log(2^121).

Or, numerically:

0.5357142857142857142857142857142857142857 < k < 0.9999999999999999999999999999999997668174

[quintopia]

oh okay, got it. is 11x11 the largest area searched for GoEs so far?

[calcyman]

11x11 is the smallest area known to contain GoEs (apart from 10x12, which has a much smaller quantity of known GoEs). The largest area known to contain no GoEs is 5x6, which is the basis of my lower bound for the information entropy of CGoL.

[quintopia]

It turns out that what I mean when I said Gardens of Eden was Orphans. I would assume that all the 11x11 known GoEs are also Orphans, and that the 11x11 area has been completely searched? (I saw 14 12x12 GoEs on the wiki, but that gives a worse bound.)

[calcyman]

As far as I know, 'Garden of Eden' and 'Orphan' are synonymous, or at least equivalent. The 11*11 area has not been completely searched, nor do I expect it to be in the immediate future (2^121 is such a large number; Moore's Law will require many decades to reach that).

The fact that 5*6 is the largest area known to be GoE-free means that not even 6*6 has been exhaustively searched.

[quintopia]

Well, the wiki made a point of distinguishing the two. I got the impression, that Garden of Edens were the set of patterns that did not have predecessors, but Orphans were the set of patterns such that any pattern containing it as a subpattern had no predecessor. It is not immediately obvious to me that, by these definitions, all GoEs are Orphans, although it is clear to me that you believe this is so. Do you have a proof? Or perhaps, a different definition that makes it trivial to see?

[calcyman]

A pattern A is said to contain a pattern B, if and only if there is a pattern C such that A = B + C.

'+' represents the union operation. However, should we take the union over (a) both live and dead cells, or over (b) live cells alone?

In case (b), we can allow A to be a solid rectangle, and C to be the symmetric difference of A and B. As C has a predecessor, A is not an orphan, so no orphans exist.

In case (a), a pattern is any 2-colouring of Z^2, and thus the only pattern containing B is B itself. In this case, 'contains' and 'is identical to' are equivalent, so the definitions of Garden of Eden and orphan are equivalent.

[137ben]

A pattern A is said to contain a pattern B, if and only if there is a pattern C such that A = B + C.

'+' represents the union operation. However, should we take the union over (a) both live and dead cells, or over (b) live cells alone?

In case (b), we can allow A to be a solid rectangle, and C to be the symmetric difference of A and B. As C has a predecessor, A is not an orphan, so no orphans exist.

In case (a), a pattern is any 2-colouring of Z^2, and thus the only pattern containing B is B itself. In this case, 'contains' and 'is identical to' are equivalent, so the definitions of Garden of Eden and orphan are equivalent.

For the definition of orphan, I always took "contain" to mean that pattern A and pattern B are assumed to be finite rectangles (or polyominos) lain adjacent to each other. This better fits what is needed to find the natural information entropy.

Anyways, using http://homepage.tudelft.nl/37b0y/ this new 10 by 10 GoE, there are at least 72 GoEs in a 10 by 10 box, giving an upper bound of Log[2^100-72]/Log[2^100]
=0.9999999999999999999999999999991805782845422567341,
which is slightly better than calcyman's estimate.
EDIT: Also, how did you get from having no GoEs in a 5 by 6 box to the lower bound of 30/56?

[calcyman]

Has this new 10*10 GoE been proven? I'll send it to Nicolay to verify; I'm not convinced of its validity until it's been properly tested.

Anyhow, I count 512 possible configurations (with rotations and reflections considered distinct -- and quite rightfully so) in the 10*10 box, leading to a bound of:

log(2^100-512)/log(2^100) = 0.9999999999999999999999999999941730011345227145539212737977

For the 30/56 bound, we can partition the plane into 7*8 rectangles, like so:

Code: Select all

00000000
0??????0
0??????0
0??????0
0??????0
0??????0
00000000

They can store 30 bits of information whilst having predecessors, so we have a lower bound of 30/56.