Use Smoothiness to classify rules
Posted: July 30th, 2016, 11:06 am
Links:Lifespan on a torus another photo
UPDATE: The method used to classify rules is being continually updating. Many entropy-related statistics have been tried out to describe the behaviour of a rule.
It's been noticed that a neighborhood transition map based on input-configuration(neighborhood,NH) of the cell rather than input state (0 or 1) is useful in revealing the dynamics of the space. Furthermore, forward entropy and backward entropy can be measured for individual NH, ascribing a point to each NH in a 2 dimensional entropy space, where a transition is represented by a directed vector starting and ending on these points.
The asymmetry between forward entropy and backward entropy is noticed in entropy space for complex rules, and it's been suggested this discrepancy reflects vectorial/directional propagation of localisation in the universe. Later it was shown some extreme asymmetry actually comes from strobing effects common in B0/S8 rules, irrelevant to the complexity of the dynamics itself. To correct this effect, NH is taken between snapshots separated by 6 steps (thus correcting for both p2 and p3).
To further quantify this asymmetry between FE and BE, flux is measured on the aforementioned 2-D entropy space, along FE+BE axis and FE-BE axis. Transition vectors are projected onto axes and the absolute length of their projection summed for each axis, weighted by the propensity of corresponding transition. Complex rules is expected to show a strong flux along the FE-BE axis for frequent transitions between forward-uncertain NH and backward-uncertain NH. The result came out, in contrary, to support the opposite.
Random soups are tested for each rule and their mf(FE-BE),mf(FE+BE),m(input entropy) are measured to ascribe a 3-D point. Complex rules are actually associated with a large mean flux along FE+BE axis (large mf(FE+BE)), forming a piece of boundary of the rulespace. A cluster of chaotic/random rules is located in mf(FE+BE)=1~1.5, mf(FE-BE)=0.6~0.8, mean(input entropy)=3~4. It is worth noting, that another cluster lies near the origin viewed in 2d, which in 3d scattered along the m(input entropy) axis. These rules have relatively small mf(FE+BE) and mf(FE-BE) thus are not effectively classified by this method.
In addition, synchronisation of replicator stream is also noticed to show interesting dynamics, in both B0123458/S02356 and in B02345/S034
Archive:
Hi mates,
It has long been desirable to quantitatively describe the complexity of a cellular automata. Building on the 'input entropy' idea [1], the concept of smoothness emerges from the time-evolution of entropy.
Here I define smoothness as the frequency spectrum (fourier transform) of the autocorrelation profile(ACP) of the input entropy. The idea is that change in entropy can be decomposed into different frequencies, with the lowest frequency corresponding to smooth behaviour, and period 2 behaviour corresponding to frequency of 0.5. etc.
EDIT: Actually the Fourier transfrom of ACT has its own name: Spectral power distribution (SPT)
EDIT: Later I found the aforementioned way isn't consistent/robust enough. Instead I now apply a entorpy-recurrence-based method to measure the smoothness of the rule.
The general idea is
1. acquire input entropy
2. construct return map by convolution with FIR1 and then thresholding (absolute value >0.001)
3. calculate return rate (this is a fairly standard statistics for return map).
4. combined with max-min entropy, mean population to identify interesting rules.
FIR1=
1 -1
-1 1
I have undertaken a scan of the v2k9 B/S rulespace (it's actually an subspace of v2k8 outer-totalistic rulespace) to obtain some preliminary results on a 30*30 torus for 102 effective steps/
maxamplist='max amplitude'
mmlist=' (max - min)entropy'
EDIT:
Below is a clip of statistics
AVG stdev's
1entropy 2entropy 3entropy 4entropy
0.2833 0.0569 0.4352 0.0643 0.1077 0.0439 0.1576 0.0599 B012/S025
0.0544 0.0623 0.0766 0.0551 0.1889 0.2247 0.2383 0.1528 B01347/S0134
0.0478 0.0586 0.0642 0.0445 0.1006 0.1712 0.1643 0.1450 B0123457/S0346
0.0233 0.0000 0.0125 0.0010 0.0000 0.0000 0.0000 0.0000 B0124567/S12345
0.0233 0.0000 0.0125 0.0010 0.0000 0.0000 0.0000 0.0000 B0124567/S12345
0.0011 0.0012 0.0013 0.0024 0.0036 0.0028 0.0023 0.0056 B36/S0124567
Please do post any rules you want smoothness to be tested so that we build a comprehensive spectrum.
The next question, naturally , is then how comes that some rules transmits at specific frequencies and other rules have a distributed frequency.
Kind regards
Feng Geng
Reference:
[1]Wuensche, A., 2011. The DDLab Manual (Preview) 2nd ed.,p478,s.33.1
PS: The current version of matlab script can be found here. (updated 08/22/2016 @ 9:32am (UTC))
UPDATE: The method used to classify rules is being continually updating. Many entropy-related statistics have been tried out to describe the behaviour of a rule.
It's been noticed that a neighborhood transition map based on input-configuration(neighborhood,NH) of the cell rather than input state (0 or 1) is useful in revealing the dynamics of the space. Furthermore, forward entropy and backward entropy can be measured for individual NH, ascribing a point to each NH in a 2 dimensional entropy space, where a transition is represented by a directed vector starting and ending on these points.
The asymmetry between forward entropy and backward entropy is noticed in entropy space for complex rules, and it's been suggested this discrepancy reflects vectorial/directional propagation of localisation in the universe. Later it was shown some extreme asymmetry actually comes from strobing effects common in B0/S8 rules, irrelevant to the complexity of the dynamics itself. To correct this effect, NH is taken between snapshots separated by 6 steps (thus correcting for both p2 and p3).
To further quantify this asymmetry between FE and BE, flux is measured on the aforementioned 2-D entropy space, along FE+BE axis and FE-BE axis. Transition vectors are projected onto axes and the absolute length of their projection summed for each axis, weighted by the propensity of corresponding transition. Complex rules is expected to show a strong flux along the FE-BE axis for frequent transitions between forward-uncertain NH and backward-uncertain NH. The result came out, in contrary, to support the opposite.
Random soups are tested for each rule and their mf(FE-BE),mf(FE+BE),m(input entropy) are measured to ascribe a 3-D point. Complex rules are actually associated with a large mean flux along FE+BE axis (large mf(FE+BE)), forming a piece of boundary of the rulespace. A cluster of chaotic/random rules is located in mf(FE+BE)=1~1.5, mf(FE-BE)=0.6~0.8, mean(input entropy)=3~4. It is worth noting, that another cluster lies near the origin viewed in 2d, which in 3d scattered along the m(input entropy) axis. These rules have relatively small mf(FE+BE) and mf(FE-BE) thus are not effectively classified by this method.
In addition, synchronisation of replicator stream is also noticed to show interesting dynamics, in both B0123458/S02356 and in B02345/S034
Archive:
Hi mates,
It has long been desirable to quantitatively describe the complexity of a cellular automata. Building on the 'input entropy' idea [1], the concept of smoothness emerges from the time-evolution of entropy.
Here I define smoothness as the frequency spectrum (fourier transform) of the autocorrelation profile(ACP) of the input entropy. The idea is that change in entropy can be decomposed into different frequencies, with the lowest frequency corresponding to smooth behaviour, and period 2 behaviour corresponding to frequency of 0.5. etc.
EDIT: Actually the Fourier transfrom of ACT has its own name: Spectral power distribution (SPT)
EDIT: Later I found the aforementioned way isn't consistent/robust enough. Instead I now apply a entorpy-recurrence-based method to measure the smoothness of the rule.
The general idea is
1. acquire input entropy
2. construct return map by convolution with FIR1 and then thresholding (absolute value >0.001)
3. calculate return rate (this is a fairly standard statistics for return map).
4. combined with max-min entropy, mean population to identify interesting rules.
FIR1=
1 -1
-1 1
I have undertaken a scan of the v2k9 B/S rulespace (it's actually an subspace of v2k8 outer-totalistic rulespace) to obtain some preliminary results on a 30*30 torus for 102 effective steps/
maxamplist='max amplitude'
mmlist=' (max - min)entropy'
EDIT:
Below is a clip of statistics
AVG stdev's
1entropy 2entropy 3entropy 4entropy
0.2833 0.0569 0.4352 0.0643 0.1077 0.0439 0.1576 0.0599 B012/S025
0.0544 0.0623 0.0766 0.0551 0.1889 0.2247 0.2383 0.1528 B01347/S0134
0.0478 0.0586 0.0642 0.0445 0.1006 0.1712 0.1643 0.1450 B0123457/S0346
0.0233 0.0000 0.0125 0.0010 0.0000 0.0000 0.0000 0.0000 B0124567/S12345
0.0233 0.0000 0.0125 0.0010 0.0000 0.0000 0.0000 0.0000 B0124567/S12345
0.0011 0.0012 0.0013 0.0024 0.0036 0.0028 0.0023 0.0056 B36/S0124567
Please do post any rules you want smoothness to be tested so that we build a comprehensive spectrum.
The next question, naturally , is then how comes that some rules transmits at specific frequencies and other rules have a distributed frequency.
Kind regards
Feng Geng
Reference:
[1]Wuensche, A., 2011. The DDLab Manual (Preview) 2nd ed.,p478,s.33.1
PS: The current version of matlab script can be found here. (updated 08/22/2016 @ 9:32am (UTC))
