Claviatures for morphic and indicational Sound and Graphic CAs
Applications of the sub-rules approach to cellular automata
Dr. phil Rudolf Kaehr
copyright © ThinkArt Lab Glasgow
ISSN 2041-4358
( work in progress, v. 0.5.5 July, May 2015 )
Complexity Reduction by Claviatures
Conceptual background
Claviatures gives a glimpse into the usefulness of the sub-rule approach for all kind of cellular automata. The merits of the sub-rule approach becomes evident for highly complex automata where it is practically not achievable to manipulate all single rules of the automaton explicitly.
With the sub-rule approach the single rule configuration that are defining an actual machine are constructed by the chosen keys of the claviature. Like for musical keyboards the melodies are composed by the chose of the keys and are not looked up from a list of stored melodies.
Even for a quite simple example of a CA based on the indicational rules indRCI, the complexity is not to handle by classical approaches. The sub-rule approach offers a claviature of the rule set so that all individual possibilities of the rule space of size 4^20=1’099’511’627’776 are manually accessible.
The complexity of claviatures remains in a finite range of small sets of rules measured by the sum of the Stirling Numbers of the Second Kind.
Hence the rule space of ruleDM of the first example of the Claviatures is defined by the 15 morphograms distributed over 15 places generating the combination of 2x3x3x3x4 = 216 single morphogrammatic compounds of ruleDM[{k,l,m,n,o}] with k={1,6}, l={2,7,11}, m={3,8,12}, n={4,9,13} and o={5,10,14,15}.
Therefore the claviature of ruleDM with its 15 keys defines all 216 different potential realizations of the automaton morphoDM. Because the number of functions for this morphoCA is small and manageable there is no barrier to define the functions explicitly.
But the rule space for ruleDCKV of is 2x3^7x4^6 x 5 = 89’579’520. There is certainly no realistic chance to define this amount of rules and to handle it explicitly.
The case for the indicational automaton indRCI with its ruleRCI[{a,b,c,d,e, f,g,h,i, j,k,l,m,n,o,p,q,r,s,t}], where all components have 4 mutually excluding different indicational rules, the rule space is intriguingly less accessible without the sub-rule approach proposed in this paper.
The 20 positions of the automaton indRCI are defining 4^20=1’099’511’627’776 different potential realizations of the indicational rule space of indRCI. In contrast, the rule space of ECA is 2^8 = 256.
Rule space table
The current presentation of Claviatures for 1D automata is not restricting its application to 1D CAs, all higher order cellular automata of arbitrary dimensions are incuded to the application of claviatures.
Epistemologically, there is a paradigm change involved which turns the definition of classical CAs from an ‘algebraic’ to a ‘co-algebraic’ understanding of generalized CAs.
The co-algebraic approach emphasizes the ‘stream’ of computational events, and configurations are selected out of the stream by selectors like the proposed claviatures. Therefore there is no need to construct all the possible constellations step by step by CA rules.
Instead of developing reduction techniques to reduce the complexity of CAs, the claviatures approach plays on a meta-level with CAs that are accessible by selection. This leads to the well known automata theoretic concept of experiments with automata.
Algebraic structures have to be constructed, co-algebraic structurations have to be selected by interaction.
There is not just a simple duality between algebras and co-algebras in respect of constructors and destructors but also a not well recognized asymmetry between the pair “constructors/destructors” and the new deconstructors. A chiastic system change happens from the selectors of the destruction to the observators of co-algebras under the interaction of experiments.
Duality of algebras and co-algebras
Asymmetric shift from internal to external descriptions of selectors and observators
The organon of the claviatures
The claviature approach is exemplified with the morphogrammatic CAs for ruleDM, ruleDMN, ruleDMNP and ruleDCKV. Also for the indicational CAs for ruleCI, ruleCIR and ruleRCI. All are applied to the categories of graphics, sound, transition graphs and fixedpoint determination. The case for ECA is exemplified for all categories too.
The method of sub-rules for CAs is an abstraction and parametrization of the components of the rule schemes that allows a micro-analysis of the CAs. The CA sub-rule manipulator manages explicitly all CA rules of a 1D CA. The sub-rule manipulators enables a micro-analysis of the behavior of all CA rules. Comparisons of the behavior of rules, especially of groups, families and clusters of sub-rules, are part of a new kind of micro-analysis based comparatistics.
“Perhaps the most exciting artefact to be included in the exhibition is Jevons' original logic machine, or 'Logic Piano'.”
http : // www.rutherfordjournal.org/images/jevons16.jpg
Further reading
Peter Wegner, Why Interaction is more Powerful than Algorithms, 1997
http://wit.tuwien.ac.at/events/wegner/cacm_may97_p80-wegner.pdf
Dina Goldin, Peter Wegner, The Interactive Nature of Computing: Refuting the Strong Church-Turing Thesis
http://cs.brown.edu/people/pw/strong-cct.pdf
Rudolf Kaehr, STRUKTURATIONEN DER INTERAKTIVITÄT,
Skizze eines Gewebes rechnender Räume in denkender Leere (2004)
http://www.thinkartlab.com/pkl/media/SKIZZE-0.9.5-medium.pdf
http://www.thinkartlab.com/pkl/lola/Interactivity.pdf
[[interactive view with .html and .cdv]]
Initialization
Rosemarie Swan, Degree Show Glasgow School of Art 2015
Morphograms
[1, 1, 1, 1, 1] [1, 2, 3, 4, 5]
Numeric representation : of 5, 4:1, 3:2, 3:1:1, 2:2:1
[1, 1, 1, 1, 1], [1, 1, 1, 1, 2],
[1, 1, 1, 2, 1], [1, 1, 1, 2, 2], [1, 1, 1, 2, 3],
[1, 1, 2, 2, 1], [1, 1, 2, 2, 2], [1, 1, 2, 2, 3],
[1, 1, 2, 3, 1], [1, 1, 2, 3, 2], [1, 1, 2, 3, 3],
[1, 1, 2, 1, 1], [1, 1, 2, 1, 2], [1, 1, 2, 1, 3],
[1, 2, 1, 2, 1], [1, 2, 1, 2, 2], [1, 2, 1, 2, 3],
[1, 2, 1, 3, 1], [1, 2, 1, 3, 2], [1, 2, 1, 3, 3],
[1, 2, 2, 1, 1], [1, 2, 2, 1, 2], [1, 2, 2, 1, 3],
[1, 2, 1, 1, 1], [1, 2, 1, 1, 2], [1, 2, 1, 1, 3],
[1, 2, 2, 3, 1], [1, 2, 2, 3, 2], [1, 2, 2, 3, 3],
[1, 2, 3, 1, 1], [1, 2, 3, 1, 2], [1, 2, 3, 1, 3],
[1, 2, 3, 2, 1], [1, 2, 3, 2, 2], [1, 2, 3, 2, 3],
[1, 2, 3, 3, 1], [1, 2, 3, 3, 2], [1, 2, 3, 3, 3],
[1, 2, 2, 2, 1], [1, 2, 2, 2, 2], [1, 2, 2, 2, 3]
Refinements
Second refinement: D(TM[5,5]): 1, (4+1, 6+4), (6+3+1, 12+2+1), 4+3+3, 1.
Morphogram: morpho-DCKV
Procedures morphoDCKV
Requisites
Procedures morphoDCKV
Rules
Graphics
Morphogram: ruleDM
Examples for ruleDM
Morphogram: Random ruleDM
Examples for ruleDM, Random
Morphogram: ruleDMN
Examples for ruleDMN
Morphogram: ruleDMN, Random
Examples for ruleDMN, Random
Morphogram: ruleDCKV
Morphogram: ruleMNP
Examples for ruleMNP
Morphogram: Random ruleDMNP
Examples for ruleDMNP, Random
Morphogram: Random ruleDMN
Examples for ruleDMN, Random
Morphogram: ruleDCKV
Examples for ruleDCKV
Some examples out of the rule space of ruleDCKV with 2x3^7x4^6 x 5 = 89’579’520 possible constellations.
symmetric
asymmetric
Morphogram: ruleDCKV, Random
Examples for ruleDCKV, Random
Orientedness: Properties of as parts of
Trivially, despite the content and internal structure of morphoCAs based on the set of the 15 basic morphograms is overwhelmingly asymmetric their architectonic structure is symmetric. This holds even more for the classical CAs, like ECAs.
Asymmetric feature are appearing for morphic and classical CAs only ‘external’ as the positioning of the CA’s developments that are internally strictly symmetric.
Because more complex morphoCAs are not based on the symmetrical morphograms, the architectonic structure of this kind of CAs is inherently asymmetric.
This leads to the property of orientedness with its distinctions of right-,left- and straight orientedness.
A further distinction appears, the internal asymmetry of symmetric morphoCAs might start just after some steps of development while the ‘head’ of the architectonically asymmetric morphoCA is still symmetric.
As a result of this considerations and constructions about the orientedness of morphoCAs it might be stated that classical CAs are inherently architectonically symmetric.
Certainly, the asymmetry of morphoCAs is based on the complexity of the underlying morphograms. For even length morphograms, symmetry is well supported, while odd length morphograms are supporting asymmetric morphoCAs.
In the terminology of orientedness it might be said that the concept of ECAs is straight-oriented.
ECAs are not just morphogrammatically incomplete but they are also restricted in their architectonics to symmetric fundaments.
Further informtion at:
http://memristors.memristics.com/ExtendedArchCA/ExtendedArchitecturesCA.html
Exemplification
Interpretations of the applications of morpho-rules of in respect of their orientedness.
RuleSchemeR:
, RuleSchemeL:
a
b
c
d
-
-
e
-
a
b
c
d
-
e
-
-
RulesR : RulesL :
Right: head 1122:R
Left: head 1121:L
Internal symmetry for the first 6 steps ruled by [2222]
Internal asymmetry after 2 steps
Internal asymmetry after 3 steps
Examples for right - oriented rules
Colored by [2113] : ruleDCKV[{1111, 1122, 1211, 1222, 2121, 2211, 2221, 2113}]
Colored by [2223] : ruleDCKV[{1111, 1122, 1211, 1222, 2121, 2211, 2223, 2112}]
Left - oriented CA
Comparison: Complementarity of right- and left-oriented
Right - oriented Left-oriented CA
Indication: ruleCI
Examples for ruleCI
Indication: ruleCI random
Examples for ruleCI, Random
Indication: ruleCI transitions
Indication: ruleCIR
Examples for ruleCIR
Indication: ruleCIR Random
Examples for ruleCIR, Random
Indication: ruleRCI
Examples for ruleRCI
Indication: Random ruleRCI
Examples for ruleRCI, Random
ECA
Examples for ECA
ECA Random
Examples for ECA, Random
Sound
ECA
Morphogram: ruleDM
Morphogram: ruleDMN
Morphogram: ruleMNP
Morphogram: ruleDCKV
Indication: ruleCIR
Indication: ruleRCI
Structures: Transition Graphs
ECA
Morphograms: ruleDM
Examples for transition ruleDM
Morphograms: ruleDMN
Examples for transition ruleDMN
Morphograms: ruleDCKV
Examples for transition ruleDCKV
Indication: ruleCIR
Indication: ruleRCI
Examples for transition ruleRCI
FixedPoints
FixedPoints: indCI
Structure of self - modification for the indicational calculus CI
FixedPoints: ECA
Number of events, rule number and sub - rules
FixedPoints: ruleM
Structure of self - modifications for the morphogrammatic calculus morphoCA DM
FixedPoints: ruleMN
Structure of self - modifications for the morphogrammatic calculus morphoCA DMN
FixedPoints: ruleCIR
FixedPoints: ruleRCI
FixedPoints: ruleDCKV
List ruleDM, Random
Transition table for ruleDM, w=4