For general discussion about Conway's Game of Life.
David
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

Your theory can be unsure or difficult to understand, but it dosen't matter!

But, please don't reply anything being other CA-exclusive. Original GOL, or general CA only.

My theory is about speed boost of searching softwares. (especially WLS)

The probability of an OFF cell turning into ON cell ('Birth') is 8C3 / 2^8 = 7/32 = 0.21875
The probatility of an On cell staying its state ('Surviving') is (8C2 + 8C3) / 2^8 = 21/64 = 0.328125

I don't really know how can these help, but they seem so to me!

Edit: fixed 'principle' to 'theory'.
Last edited by David on March 10th, 2013, 7:17 am, edited 1 time in total.
Call me "Dannyu NDos" in Forum. Call me "Park Shinhwan"(박신환) in Wiki.

DocA
Posts: 11
Joined: January 20th, 2013, 11:43 am

My principle is about the cross-examination of CA rules through geometric shapes inputted into CA environments. A few things I do are nesting circles, squares and diamonds with radii/side lengths of {2,4,8,16,32,64,128,256,512,1028...}(powers of 2) or {3,8,18,38,78,158,318,638,1278...}(2n+2, starting with n=1/2 then using the previous number for n) or {1,2,3,4,5...}(qed). Then I load rules that preserve the shapes' symmetries without destroying the structure or freezing everything in place.

Tropylium
Posts: 406
Joined: May 31st, 2011, 7:12 pm
Location: Finland

David wrote:The probability of an OFF cell turning into ON cell ('Birth') is 8C3 / 2^8 = 7/32 = 0.21875
The probatility of an On cell staying its state ('Surviving') is (8C2 + 8C3) / 2^8 = 21/64 = 0.328125
Those are first approximations only. Not all of the 256 cell environments occur with equal probability, for starters because the overall density of cells is not 0.5.

For some more accuracy, assume that the density of cells is ρ.
birth frequency B = 52ρ³(1-ρ)⁶
survival frequency S = 52ρ⁴(1-ρ)⁵ + 28ρ³(1-ρ)⁶
Then solve the equation B+S = ρ to get finer results.

Still life-like and oscillator-like behavior also complicate this. In some areas (e.g. isolated still lifes, or a large block of zebra stripes) survival and abstinence may prevail until disturbed; in others (e.g. a large block of venetian blinds), birth and death.

For better accuracy, considering larger areas and timescales could help, e.g. 4×4 → 2×2 transitions rather than 3×3 → 1×1; or 5×5 → 1×1 over 2 generations.

---

Here's a hypothesis:

A. For all sufficiently large N, there are more N-cell pseudo still lifes than strict still lifes.
a1. FASLNTAM N-cell tieless pseudo still lifes than tieless strict still lifes.
a2. FASLNTAM N-cell tied pseudo still lifes than tied strict still lifes.
B. FASLNTAM N-cell tied still lifes than tieless still lifes.*
b1. FASLNTAM N-cell tied pseudo still lifes than tieless pseudo still lifes.
b2. FASLNTAM N-cell tied strict still lifes than tieless strict still lifes.
C. For any finite pattern of ON cells, either the shape cannot appear as a subset of any still life, or FASLN, there are more N-cell still lifes containing this pattern than not.

(Note that a1 & a2 implies A, and b1 & b2 implies B.)

Not much stats on the number of ties of N cells is available; I have no idea a priori how the amounts of ties and pseudo still lifes should relate to each other for large N. The concepts seem just about on level with each other.

*Ties are the contiguous analogue of pseudo still lifes. A still life is tied if it can be divided into two or more contiguous parts that are still lifes in their own right.

Mats
Posts: 42
Joined: August 10th, 2010, 7:40 am
Location: Stockholm, Sweden

Tropylium wrote:Here's a hypothesis:

A. For all sufficiently large N, there are more N-cell pseudo still lifes than strict still lifes.
a1. FASLNTAM N-cell tieless pseudo still lifes than tieless strict still lifes.
a2. FASLNTAM N-cell tied pseudo still lifes than tied strict still lifes.
B. FASLNTAM N-cell tied still lifes than tieless still lifes.*
b1. FASLNTAM N-cell tied pseudo still lifes than tieless pseudo still lifes.
b2. FASLNTAM N-cell tied strict still lifes than tieless strict still lifes.
C. For any finite pattern of ON cells, either the shape cannot appear as a subset of any still life, or FASLN, there are more N-cell still lifes containing this pattern than not.
Nice! I beleive them all to be true.

As far as I can see C implies B. Consider this pattern:

Code: Select all

``````x = 13, y = 13, rule = B3/S23
4bo\$3bobo\$3bob3o\$b2o5bo\$o6bobo\$b2o3bobobo\$2bo2bobo2bo\$2bobobo3b2o\$3bobo6bo\$4bo5b
2o\$5b3obo\$7bobo\$8bo!``````
Any still life where this one appears as a subpattern is tied, because the middle tub can be removed and the rest of the pattern will still be a still life. If C holds - FASLN this subpattern appears in more than half of the N-cell still lives, which implies that more than half of the N-cell still lives are tied. So C implies B.

A similar argument showing that C implies A should be possible to find.

Tropylium
Posts: 406
Joined: May 31st, 2011, 7:12 pm
Location: Finland

Mats wrote:As far as I can see C implies B. Consider this pattern:

Code: Select all

``````x = 13, y = 13, rule = B3/S23
4bo\$3bobo\$3bob3o\$b2o5bo\$o6bobo\$b2o3bobobo\$2bo2bobo2bo\$2bobobo3b2o\$3bobo6bo\$4bo5b
2o\$5b3obo\$7bobo\$8bo!``````
Any still life where this one appears as a subpattern is tied, because the middle tub can be removed and the rest of the pattern will still be a still life.
Ha, clever! This seems to hold, yes.
Mats wrote:A similar argument showing that C implies A should be possible to find.
Indeed:

Code: Select all

``````x = 16, y = 10, rule = B3/S23
4b2ob2ob2o\$3bobob2obobo\$3bo8bo\$2ob2o6b2ob2o\$bo3bob2obo3bo\$bo3bob2obo3b
o\$2ob2o6b2ob2o\$3bo8bo\$3bobob2obobo\$4b2ob2ob2o!``````
(pseudo still life with the center block remoovable no matter how the object is extended)

It also does not seem like a stretch to include a large proportion of oscillator rotors under C. If not all; I'm only wondering if sparkless, pulsating, external statorless oscillators can necessarily be incorporated into a non-strict object. (E.g. a simple blinker cannot really be combined non-trivially with any other object… it does occur though as a "variable induction coil" in some patterns so this isn't itself a counterargument.)