otismo wrote: November 29th, 2020, 2:27 amThe question now before us is exactly how do we quantify how much information resides in any particular CGoL Pattern ? How would we measure it ? What are your thoughts ?
A problem with this question is that there are multiple possible ways to measure the information of a pattern.
One possibility is if we measure the amount of information that the pattern can use, i.e. the pattern is a computer. In this case, more compact storage (and more compact ways to access and possibly change the stored information) would result in increased information per size.
Another method of measurement is if we only require a human looking at the pattern to be able to get information from it. For example, suppose that we agree upon a system where information is encoded in the placement of blocks, with a gap of one cell between two adjacent blocks on the same row signifying a zero and a gap of two cells between two adjacent blocks on the same row signifying a one. Using this system, here is the word "blocks" in ASCII.
Code: Select all
x = 155, y = 2, rule = B3/S23
2o2b2o2b2ob2ob2ob2o2b2ob2o2b2o2b2ob2o2b2o2b2ob2ob2o2b2o2b2ob2o2b2o2b2o
2b2o2b2o2b2o2b2ob2ob2ob2o2b2o2b2o2b2o2b2ob2o2b2ob2o2b2o2b2o2b2o2b2o2b
2ob2ob2o2b2o2b2o$2o2b2o2b2ob2ob2ob2o2b2ob2o2b2o2b2ob2o2b2o2b2ob2ob2o2b
2o2b2ob2o2b2o2b2o2b2o2b2o2b2o2b2ob2ob2ob2o2b2o2b2o2b2o2b2ob2o2b2ob2o2b
2o2b2o2b2o2b2o2b2ob2ob2o2b2o2b2o!
Of course, I could squeeze more information in per space by also allowing snakes, and I could also allow more objects by increasing the row height. Every new possibility that I add increases the amount of information per space, and at the extreme limit, including dropping the restriction that the pattern must be stable or repeating, is using each cell to store one byte.
Code: Select all
oobbbobooboobbooboooooobbboooobobooooobboo
Of course, there are also more efficient (in terms of information entropy) ways to store text limited to the lowercase letters of the modern English alphabet than ASCII, but this method would work equally well with them. In addition, by using row breaks as part of the information encoding, one could increase the maximum entropy even further. However, the vast majority of the resulting patterns will quickly decay, and some may even be Gardens of Eden if one uses enough rows and columns.
An arguably more practical method is based off of the following question: Given some pattern of settled ash, how many bits of information would an encoding algorithm optimized for efficiently encoding settled ash from ConwayLife require to encode it? For example, blocks and blinkers show up pretty commonly, so the encoding algorithm shouldn't have to use too many bits of information to express them, but giving a rare object, such as a loafer, a relatively short (bitwise) encoding would take up a significant chunk of the binary (or analogous) tree, forcing at least one fairly common object to settle for a smaller chunk of the binary (or analogous) tree, corresponding to a longer (bitwise) encoding, than it otherwise would have.
However, this method is not as simple as using Huffman or arithmetic coding to list the objects then figuring out some efficient way to store the displacement from each object to the next because certain objects tend to be arranged relative to each other in certain ways. For example, a honey farm is more likely to form than four beehives arranged randomly with a similarly-sized bounding box to a honey farm, such as this example.
Code: Select all
x = 14, y = 12, rule = B3/S23
4bo$3bobo$3bobo$4bo2$b2o$o2bo7b2o$b2o7bo2bo$11b2o$4b2o$3bo2bo$4b2o!
Likewise, the ash of an R-pentomino is more likely to form than the ash of an R-pentomino except that a block near the center has been displaced by one cell. The problem in this case is to find some way to gauge how likely a given pattern of settled ash is to form.
One idea is glider cost, but it has several problems. First of all, a universal constructor requires at most seventeen gliders, so a fireship would be considered no less likely to occur out of a random soup than a Gemini by that metric. Even if one prohibits universal constructors, there are still some problems. For one thing, glider cost is not a perfect gauge of accuracy: A tub is more common than a fishhook, and an R-sequence is more common than a two-glider mess. In addition, modifications of common patterns may have cheaper glider syntheses than their actual likelihood would suggest. For example, the ash of an R-pentomino with a table added to the ship or something probably has a similar, possibly the same, glider cost as the result of an R-pentomino hitting a couple of blocks around generation 300, but I suspect that the latter is more likely. Another idea is the cell count of the smallest predecessor, but while this may be somewhat better than the glider cost, it still has the same flaws because it is capped by five times the glider cost.
Simply telling the algorithm which collections of ash are common won't work. For one thing, there are too many possibilities of a common active region hitting a common object or another common active region for the program to realistically be able to store all of them. Another hurdle is the nuances in common constellations. For example, simply telling the computer that traffic lights are common will inevitably result in it rating this object as either too likely or not likely enough.
Code: Select all
x = 11, y = 11, rule = B3/S23
2b3o2$o5bo$o5bo$o5bo2$2b3o3b3o2$6bo$6bo$6bo!
Another interesting problem is to design an algorithm that can gauge the likelihood of active regions instead of just settled ash. This would be useful for backtracking, and while it may initially seem to be not very difficult, as it is relatively easy for a human to identify an easily edgeshootable region or the child of one, but anything doing back more than a few generations turns out to be difficult. For example, without playing the pattern until it settles or using some search program to search for small predecessors, which of the following active regions seems most likely to occur naturally?
Code: Select all
x = 47, y = 39, rule = LifeHistory
2.D8.A.2A17.4D5.A.2A$.D.D6.5A17.D3.D3.5A$D3.D3.2A6.A15.D3.D.2A6.A$D3.
D3.2A6.A15.D3.D.2A6.A$5D3.2A3.A2.A15.4D2.3A2.A2.A$D3.D5.A3.2A16.D3.D3.
A3.2A$D3.D6.3A18.D3.D4.3A$D3.D6.3A18.D3.D4.3A$D3.D27.4D22$2.4D5.A.2A16.
4D6.A.2A$.D4.D3.5A16.D3.D4.5A$.D4.D.2A6.A14.D4.D.2A6.A$.D6.2A6.A14.D4.
D.2A6.A$.D6.2A3.A2.A14.D4.D.3A2.A2.A$.D8.2A2.2A15.D4.D3.2A2.2A$.D4.D4.
3A17.D4.D4.3A$.D4.D4.3A17.D3.D5.3A$2.4D25.4D!
#C [[ VIEWONLY ]]
The correct answer is C because it is generation 12 of the century, but any reasonable person or computer algorithm who has not memorized the intermediate states of common active regions or searched through them just now could have chosen B or D. As another example, besides being symmetric, the typical honey farm great-grandparent seems relatively unlikely to form, but it is not surprising that the active object nine generations earlier is fairly common.
In addition, any algorithm for assessing the likelihood of any active region or region of ash would also have to take into account the geometry of the field (e.g. toroidal), the initial density, the size of the initial soup, and likely other factors.
To summarize the second half or so of this post, assessing how reasonably a given pattern could have evolved in ConwayLife is not at all trivial.
