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:

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