## Use Smoothiness to classify rules

For discussion of other cellular automata.
shouldsee
Posts: 406
Joined: April 8th, 2016, 8:29 am

### Re: Use Smoothiness to classify rules

I tried to calculate eigval on a sample of similar sum-cov. Not sure whether eigval provides enough resolution. (I don't really know what I am doing now... )

The rulelist is as follows

Code: Select all

``````ind	rulename	sumcov
---------with gliders
1	B01345/S1235	0.0912147502
2	B0126/S025	0.1299489189
3	B0136/S013	0.1593021491
4	B012346/S12347	0.1204068196
5	B01246/S2345	0.1854712866
6	B3578/S2467	0.0522633236
7	B0246/S1234678	0.0623930655
8	B0123478/S13456	0.1088542398
9	B023/S3	0.1159036992
---------without gliders
10	B3568/S457	0.3578531118
11	B478/S0124568	0.0918053741
12	B47/S12356	0.065023128
13	B4678/S2346	0.0581188588
14	B46/S34578	0.2144241111
15	B458/S12358	0.0814490097
16	B458/S03467	0.1833115434
17	B4578/S02357	0.1356104473
18	B457/S13458	0.115943888
19	B457/S125678	0.0436899157
20	B4568/S14678	0.508908881
21	B4568/S01456	0.2100663449
22	B4568/S012468	0.061893223
23	B456/S2457	0.3785563758
24	B456/S13468	0.1271470884
25	B45/S34678	0.4383271243
26	B45/S13467	0.1688287676
27	B45/S023578	0.0873226637
28	B38/S2458	0.1988019786
29	B38/S126	0.1747732816
30	B38/S1258	0.1485976947
31	B38/S1235	0.050525254
32	B38/S0137	0.1123109091
33	B37/S1258	0.1774642187
34	B37/S03467	0.1820389739
35	B368/S1268	0.177318408
36	B368/S024678	0.1543197406
37	B368/S01456	0.0994167225
38	B3678/S234678	0.1762317684
39	B3678/S014678	0.212859524
40	B367/S34678	0.2414952442
``````
Another run of statistics with eigval-wise entropy added.

Code: Select all

``````ind   rule  sumcov     ent-eigval effective gennum
1	B01345/S1235	0.013576356	0.682650437	122
2	B0126/S025	0.0157049499	0.043839301	113
3	B0136/S013	0.0131982053	0.1878726607	62
4	B012346/S12347	0.0140107965	0.341077261	47.5
5	B01246/S2345	0.0138134507	0.0563178535	87
6	B3578/S2467	0.0170394302	0.984168541	122
7	B0246/S1234678	0.0151378362	0.8287909057	122
8	B0123478/S13456
9	B023/S3	0.0151171728	0.2377043381	122
10	B3568/S457	0.0149634938	0.0449841591	60
11	B478/S0124568	0.0142574139	0.1374848235	44
12	B47/S12356	0.0161531784	0.1395905735	78
13	B4678/S2346	0.0143078978	0.1940198251	91
14	B46/S34578	0.014481117	0.163092486	82.5
15	B458/S12358	0.0141966238	0.0601296873	104
16	B458/S03467	0.0140630358	0.0461868486	58
17	B4578/S02357	0.0141081254	0.0445851141	63
18	B457/S13458	0.0147691258	0.0657322013	122
19	B457/S125678
20	B4568/S14678
21	B4568/S01456
22	B4568/S012468	0.0185119068	0.2313700629	122
23	B456/S2457	0.0164543766	0.2653815401	112.5
24	B456/S13468	0.0174584745	0.5196705014	122
25	B45/S34678	0.0137175951	0.0496711468	69
26	B45/S13467	0.0161772229	0.0750878961	122
27	B45/S023578
28	B38/S2458
29	B38/S126	0.0196320049	0.2153741964	59
30	B38/S1258	0.0134766179	0.2583403383	119
31	B38/S1235	0.0175393482	0.4831116569	83.6666666667
32	B38/S0137	0.0160080466	0.3347883123	94
33	B37/S1258	0.0163332189	0.1827366728	100
34	B37/S03467	0.0135733608	0.0483822069	58
35	B368/S1268	0.0174716418	0.1723090065	59
36	B368/S024678	0.0150004046	0.0381971307	78
37	B368/S01456	0.015339473	0.1365470068	122
38	B3678/S234678	0.0133595364	0.0195362846	46
39	B3678/S014678
40	B367/S34678	0.0144942872	0.1663931507	83.5
``````
Attachments
resolve_sumcov.jpg (101.32 KiB) Viewed 5150 times
Last edited by shouldsee on August 12th, 2016, 6:07 am, edited 2 times in total.

Bullet51
Posts: 536
Joined: July 21st, 2014, 4:35 am

### Re: Use Smoothiness to classify rules

shouldsee wrote:Not sure whether eigval provides enough resolution.
It does not even discriminate:
3.png (17.1 KiB) Viewed 5148 times
By the way, how do you determine whether a rule has a glider or not?
Still drifting.

shouldsee
Posts: 406
Joined: April 8th, 2016, 8:29 am

### Re: Use Smoothiness to classify rules

Bullet51 wrote:
shouldsee wrote:Not sure whether eigval provides enough resolution.
It does not even discriminate:
3.png
By the way, how do you determine whether a rule has a glider or not?
By manually inspecting it or sending it to apgsearch. I never really tried to use other scripts to search.

Would be glad if anyone has recommendation.

BTW, I think calculating eigenvalue is largely related to principal component analysis. We can check the largest PC's to confirm whether they are due to wave conversion or not.

A possible source for the observed large PCA/eigenvalue is the phase transition/wave conversion itself, which would cause a vectorial shift in the distribution of neighbor counts, which in turn is captured by the co-variation analysis. In this case, the largest PCA is simply a measure of time.

shouldsee
Posts: 406
Joined: April 8th, 2016, 8:29 am

### Re: Use Smoothiness to classify rules

Proof of concept:
PCA of neighborhood counts distribution can reflect the vectorial evolution of a universe. But more generally, it serves to visualise the phase space of a universe, for PCA's ultimate advantage is to capture variation.

Since PCA is sensitive to variation, I have smoothed the time series by a window of 6 to prevent strobing effect plagued the PC's.

A small collection of similar plots can be found here. (too big to attach)
Attachments
B012346S12347_soup12.jpg (229.66 KiB) Viewed 5021 times
B012346S12347_soup11.jpg (213.04 KiB) Viewed 5021 times
Last edited by shouldsee on August 12th, 2016, 5:02 pm, edited 1 time in total.

Bullet51
Posts: 536
Joined: July 21st, 2014, 4:35 am

### Re: Use Smoothiness to classify rules

shouldsee wrote:By manually inspecting it or sending it to apgsearch. I never really tried to use other scripts to search.

Would be glad if anyone has recommendation.
Gsearch may be useful:

Code: Select all

``````x = 3, y = 3, rule = B38/S2458
3o\$b2o\$2bo!

x = 4, y = 5, rule = B38/S126
bobo\$o2bo\$o\$o2bo\$bobo!

x = 4, y = 5, rule = B38/S1258
b3o\$ob2o\$bo\$b2o\$b2o!

x = 4, y = 5, rule = B38/S0137
o\$2o\$bobo\$b3o\$3bo!

x = 4, y = 5, rule = B37/S1258
2bo\$bo\$2o\$b3o\$2bo!

x = 5, y = 9, rule = B37/S03467
2b3o\$3b2o\$3bo\$bo\$o2bo\$bo\$3bo\$3b2o\$2b3o!

x = 4, y = 5, rule = B368/S1268
obo\$o2bo\$3bo\$o2bo\$obo!

x = 5, y = 4, rule = B368/S024678
o3bo\$2b3o\$2b3o\$o3bo!

x = 5, y = 5, rule = B367/S34678
3bo\$3b2o\$3b2o\$3obo\$b3o!

x = 4, y = 4, rule = B3678/S234678
bo\$ob2o\$2b2o\$2b2o!

x = 7, y = 5, rule = B3678/S014678
ob2o\$3obo\$obobobo\$3obo\$ob2o!

x = 9, y = 8, rule = B368/S01456
2bo3bo\$ob2ob2obo\$bob3obo\$4bo\$bo5bo\$3bobo\$3bobo\$3b3o!
``````
David Eppstein shows that most of the rules which is "essentially-not-glider-impossible" does have a glider.
Still drifting.

Bullet51
Posts: 536
Joined: July 21st, 2014, 4:35 am

### Re: Use Smoothiness to classify rules

shouldsee wrote: A possible source for the observed large PCA/eigenvalue is the phase transition/wave conversion itself, which would cause a vectorial shift in the distribution of neighbor counts, which in turn is captured by the co-variation analysis. In this case, the largest PCA is simply a measure of time.
I'm not sure what "wave conversion" means. Maybe global fluctuations of the dynamics? If the variation of neighbor counts is mostly caused by global fluctuations, all neighbor counts will correlate, thus leading a full-1 co-variation matrix.(This is exactly the case of class 1 rules.)
Still drifting.

shouldsee
Posts: 406
Joined: April 8th, 2016, 8:29 am

### Re: Use Smoothiness to classify rules

Bullet51 wrote:
David Eppstein shows that most of the rules which is "essentially-not-glider-impossible" does have a glider.
Thanks for recommending gsearch. Yes constructing gliders manually would be possible in many rules, with low spontaneous occurrences. This in turn implies that glider constitutes either a small attractor basin or simply an unstable basin. My older interest is mainly in rules where you get gliders emitted from random soups at an acceptable frequency. This aim is gradually being replaced by characterising the cooperative/larger-scale behaviour in the CA universe. While spontaneous glider does hallmark such behaviour, other non-glider behaviour should also be included.

Imagine we have a constructed non-spontaneous glider, if what it uses are all common transitions, then it should be spontaneously emerging to some extent. One reason why it's non-spontaneous is that this local configuration is somehow prohibitive, for example it might uses a rare transition. Other possibilities exist. This local configuration might be impossible around the edge of the chaos so that the glider cannot escape chaos. Or the chaos-order edge itself has a strange topology (where the CO edge is an exploding ring between two ordered area) that disallows any observation.

Anyway, merely existence of glider seems not to be too good a criteria for describing the emergence of a rule. We should seek some other definition.

shouldsee
Posts: 406
Joined: April 8th, 2016, 8:29 am

### Re: Use Smoothiness to classify rules

Bullet51 wrote:
shouldsee wrote: A possible source for the observed large PCA/eigenvalue is the phase transition/wave conversion itself, which would cause a vectorial shift in the distribution of neighbor counts, which in turn is captured by the co-variation analysis. In this case, the largest PCA is simply a measure of time.
I'm not sure what "wave conversion" means. Maybe global fluctuations of the dynamics? If the variation of neighbor counts is mostly caused by global fluctuations, all neighbor counts will correlate, thus leading a full-1 co-variation matrix.(This is exactly the case of class 1 rules.)
I had triphasic dynamics in mind when speaking of "converstion wave".
These are perfect examples where one group of neighborhoods taking territory from another group.
triphasic

Code: Select all

``````x = 22, y = 24, rule = B045678/S01568:T100,100
2o4b4o2b2obob2o2bo\$b3ob2o2b2ob3ob2obo\$ob3obobo2b2o3bob3o\$b2obo2b2o5b3o
3b2o\$5b2obo4b3obobo\$bo2bo3bo9bobo\$2obo2bob3obobob4obo\$b2o5b4o4b2ob2o\$b
2ob2o5bo3b3o2bo\$o2b8obo3b3ob2o\$o3b2o5bobo3bob2o\$5bo5b4obob3o\$2ob2obo3b
obobo4b2o\$3o2bobo2b5obobo2bo\$2obob2obobob2o4bo2bo\$3ob2ob3o3bobob2o\$7ob
o2bo5b5o\$ob2o3b6o2bobo\$b3o5b3ob6ob2o\$b3o2b3o2b3obo3b2o\$3b2o3bobo3b2obo
3bo\$bo2b2o3b5o3b2ob2o\$2o2bobo4bob2ob6o\$o2bobob2o2b2obo3bo2bo!
``````

Code: Select all

``````x = 32, y = 32, rule = B013/S1236:T100,100
2bo4bobo2bobo2bo3bob3o3b2o\$o3b5o5b2o2b2o2b2obob2obo\$4bobo2b2o2bo2b2o2b
4o3bo3bo\$b2ob3o2bob8obobob4o2bo\$4ob3obob2o4bob4o2bobob3o\$obo2b6o4bob2o
5b2o2b2o\$10b2o3bo4bo2bo3b2o\$5b2obo2bob3obob2ob2ob4o\$2b3o4b2o2b4obo2b5o
b3o\$b2obob3o2bo3b2ob6o3b3o\$2o2bo4bobobobo6b4o2b2o\$2o4b2obob3o3b4o3b5o
2bo\$o3bo2b2ob3o2b3o4b3o5bo\$bo2bobob3o2b3o3bo4b2ob2o2bo\$o2bo3bobo2b2obo
2b5o2bo2b2obo\$ob3ob2o3bobobo4bo2bob2o2b2o\$ob2o4bo4b2o4b2o6bo2bo\$obo3b
4o2b2ob7o2b2o2b2o\$ob2obobo4bo2b2o3b5ob2ob3o\$o2b4o7bobo3bo2b3o2b2obo\$4b
obobo5bob5o3bo2bo3bo\$b3o5b2o3b3o2b3o6bo\$bob6o4bobo2bo5bob2o2b2o\$o5b3o
5bobob2obob2o4bobo\$bo2bo2bobo3bobob3o3b4o2b2o\$2obobob2o4bobob3o2b2ob3o
b3o\$bo2bo5b3o5b2obo4b3o2bo\$obo2bo2b2o3bo2bo2b3ob2o5bo\$5b3obob2o3bo2b4o
b3obo\$2bo2b3obo3bob2obob2obob2o3b2o\$2o3b2ob2o4b3o2bobob3o3bo\$ob2obo2bo
2bo3b5o2bo2bo2bo!
``````

Bullet51
Posts: 536
Joined: July 21st, 2014, 4:35 am

### Re: Use Smoothiness to classify rules

It seems that we should use statistics not sensible to variations, maybe some kind of local statistics.
Still drifting.

shouldsee
Posts: 406
Joined: April 8th, 2016, 8:29 am

### Re: Use Smoothiness to classify rules

Bullet51 wrote:It seems that we should use statistics not sensible to variations, maybe some kind of local statistics.
I plan to try renormalisation at some point. CA is a perfect substrate for analysis based on different scales.

To start, we need to construct statistics at different scales. Then record their change as scale changes. Then we can get a feeling about how emergent is the rule. sum-cov is my first attempt here, and entropy of eigenvalues maybe an alternative. Once we have a statistics reliable enough, we can throw them onto different scales to characterise the emergence.

shouldsee
Posts: 406
Joined: April 8th, 2016, 8:29 am

### Re: Use Smoothiness to classify rules

HI guys,

I want to introduce "neighbourhood(NH) transition" based on the neighbourhood counts mentioned earlier. Say we have a cell (i,j). S(i,j) denotes the current state of (i,j), N(i,j) denotes the neighborhood of S(i,j). The updating rule can be viewed as S(t+1)=u[N(t)] where u is the updating function/mapping.

Now since we are not merely interested in updating the universe, we want to measure something out of it, especially about its temporal evolution. One way is to construct Poincare maps in the form of (A(t),B(t+1)), where A and B can be anything. Since (N(t),S(t+1)) is fixed under u, it will not be informative. But since (S(t),S(t+1)) and (N(t),N(t+1)) are not fixed, they can somewhat characterise its dynamics.

Under B/S notation, S(t) can only take two states,0/1, but N(t) can take 9*2=18 states. The resolution in N(t) return map thus allows further analysis.

Preliminary result is quite encouraging. The time-averaged return map is calculated for 20*20 torus over a maximum generation of 112. There are many hotspots/strips in the N(t) return map. I also symmetricised to make them fancy. More plots can be found here.

Kind regards
Feng

PS: As BlinkerSpawn has implied earlier,low resolution of co-variation between N(t) counts can be improved by splitting N(t) into smaller categories. The approach presented here, however, expand N(t) into temporal domain to be (N(t),N(t+1)) at a cost of O(N^t). We should manage to live through this. : )

PPS:I also remembered some other paper applying Markov model on (Sn(t),Sn(t+1)) where S is local configuration of size(n,n), which is similar to this approach here.

PPPS: The directed and undirected NHT are both mean(log2(counts)) transformed .

PPPPS: The very weird part about NHT plot is that, for a specific output NH, there exists a range of possible input NH. But not vice versa. This is very counter-intuitive, cause we would expect input-NH to put some constraint on the output-NH, not the opposite. I am still trying to reconcile this observation at the moment.
EDIT: This problem has been resolved by doing a left-right merge.
(!!)EDIT: That perception above was wrong. The NHT matrix was x-y flipped to cause the illusion mentioned above. The correct NHT matrix is NOT counter-intuitive!!
Attachments
B4678S2346_soup39.jpg (169.01 KiB) Viewed 5021 times
B4678S2346_soup38.jpg (177.89 KiB) Viewed 5021 times
Last edited by shouldsee on August 12th, 2016, 5:04 pm, edited 4 times in total.

Bullet51
Posts: 536
Joined: July 21st, 2014, 4:35 am

### Re: Use Smoothiness to classify rules

shouldsee wrote: I want to introduce "neighbourhood(NH) transition" based on the neighbourhood counts mentioned earlier.
That's a pretty good measure. Some more statistics can be extracted from it:
The diagonal count on S transitions shows how stable a rule is.
The diagonal count on B transitions may be an evidence of stable attractors.
What about the chaoticity of a rule?
Still drifting.

shouldsee
Posts: 406
Joined: April 8th, 2016, 8:29 am

### Re: Use Smoothiness to classify rules

Bullet51 wrote: That's a pretty good measure. Some more statistics can be extracted from it:
The diagonal count on S transitions shows how stable a rule is.
The diagonal count on B transitions may be an evidence of stable attractors.
What about the chaoticity of a rule?
Do you plan to average your stats over time?

Diagonal count could be due to a return period of 1, or a first order stationary point. But be cautious here, there might be 2nd or 3rd or higher order stationary points that are scattered on the NHT plot, that form a closed (or nearly closed) cycle over time.

Moreover, under the framework of NHT, it's possible to throw techniques from continuous non-linear dynamics to characterise.

Posts: 1905
Joined: November 8th, 2014, 8:48 pm
Location: Getting a snacker from R-Bee's

### Re: Use Smoothiness to classify rules

shouldsee wrote:
Bullet51 wrote: That's a pretty good measure. Some more statistics can be extracted from it:
The diagonal count on S transitions shows how stable a rule is.
The diagonal count on B transitions may be an evidence of stable attractors.
What about the chaoticity of a rule?
Diagonal count could be due to a return period of 1, or a first order stationary point. But be cautious here, there might be 2nd or 3rd or higher order stationary points that are scattered on the NHT plot, that form a closed (or nearly closed) cycle over time.
Do "n-th order stationary points" correspond (roughly) to cells inside common period-n patterns/subpatterns?
LifeWiki: Like Wikipedia but with more spaceships. [citation needed]

shouldsee
Posts: 406
Joined: April 8th, 2016, 8:29 am

### Re: Use Smoothiness to classify rules

Do "n-th order stationary points" correspond (roughly) to cells inside common period-n patterns/subpatterns?
I have absolute no idea at this stage.

The most striaghtforward test is take a NHT plot of an oscillator.

But more generally, we are interested in near-stationary. We want things to return, but not exactly to the same point, allowing for more diversity.

Bullet51
Posts: 536
Joined: July 21st, 2014, 4:35 am

### Re: Use Smoothiness to classify rules

BlinkerSpawn wrote:Do "n-th order stationary points" correspond (roughly) to cells inside common period-n patterns/subpatterns?
Yes.
A result of the blinker-rich rule B3S26:
1.png (5.86 KiB) Viewed 5072 times
EDIT：The B3->S3 transition should be S1->B3
Last edited by Bullet51 on August 12th, 2016, 9:56 am, edited 1 time in total.
Still drifting.

shouldsee
Posts: 406
Joined: April 8th, 2016, 8:29 am

### Re: Use Smoothiness to classify rules

Bullet51 wrote:
BlinkerSpawn wrote:Do "n-th order stationary points" correspond (roughly) to cells inside common period-n patterns/subpatterns?
Yes.
A result of the blinker-rich rule B3S26:
1.png
Let's do a comparison between this and chaos in B3/S26

Actually, would you mind post 1D-ised pattern along with the plot?

Bullet51
Posts: 536
Joined: July 21st, 2014, 4:35 am

### Re: Use Smoothiness to classify rules

shouldsee wrote:Let's do a comparison between this and chaos in B3/S26
What do you mean by chaos in B3/S26? I cannot get the idea.
shouldsee wrote: Actually, would you mind post 1D-ised pattern along with the plot?
I'm sorry about that, since I'm using a 1000x1000 grid.
Still drifting.

shouldsee
Posts: 406
Joined: April 8th, 2016, 8:29 am

### Re: Use Smoothiness to classify rules

Bullet51 wrote:
shouldsee wrote:Let's do a comparison between this and chaos in B3/S26
What do you mean by chaos in B3/S26? I cannot get the idea.
shouldsee wrote: Actually, would you mind post 1D-ised pattern along with the plot?
I'm sorry about that, since I'm using a 1000x1000 grid.
What a gigantic universe lolllll!! I am only doing 30*30.. You computer-rich guys :/..

I meant 'chaos' as the transient pattern in the dying soup.

BTW, I tried a left-right merge of the NHT graph, this get rid of the suspicious blanks. It's possible to do a further up-down merge. The NHT collection has been updated accordingly.
Last edited by shouldsee on August 12th, 2016, 5:05 pm, edited 1 time in total.

Bullet51
Posts: 536
Joined: July 21st, 2014, 4:35 am

### Re: Use Smoothiness to classify rules

shouldsee wrote: I meant 'chaos' as the transient pattern in the dying soup.
Sure.
1.png (6.57 KiB) Viewed 5053 times
Still drifting.

shouldsee
Posts: 406
Joined: April 8th, 2016, 8:29 am

### Re: Use Smoothiness to classify rules

Bullet51 wrote:
shouldsee wrote: I meant 'chaos' as the transient pattern in the dying soup.
Sure.
1.png
Did you not take the log of the counts? The colors are too faint here.

Bullet51
Posts: 536
Joined: July 21st, 2014, 4:35 am

### Re: Use Smoothiness to classify rules

shouldsee wrote:
Did you not take the log of the counts? The colors are too faint here.
It's not so convenient to compare the colors in a log scale.At least for me...
1.png (7.13 KiB) Viewed 5049 times
Still drifting.

shouldsee
Posts: 406
Joined: April 8th, 2016, 8:29 am

### Re: Use Smoothiness to classify rules

Bullet51 wrote:
shouldsee wrote:
Did you not take the log of the counts? The colors are too faint here.
It's not so convenient to compare the colors in a log scale.At least for me...
1.png
You can try to change the colormap if you don't like the current one. Maybe try 'colorcube' or 'prism'. Log-scaled is more informative.

Also, I am not sure LR merge is really a helpful idea. It appears easier to do cobweb plots on undirected NHT plot.

Bullet51
Posts: 536
Joined: July 21st, 2014, 4:35 am

### Re: Use Smoothiness to classify rules

A somewhat difficult question: How much information can we extract from the transition matrix?
Still drifting.

shouldsee
Posts: 406
Joined: April 8th, 2016, 8:29 am

### Re: Use Smoothiness to classify rules

Bullet51 wrote:A somewhat difficult question: How much information can we extract from the transition matrix?
Need to try measure the degree of symmetry of NHT. We need to find dynamic with symmetry over time