Extending Architectures of MorphoCellular Automata

A wee sketch on the complementarity of directed morphoCAs

Dr. phil Rudolf Kaehr

copyright © ThinkArt Lab Glasgow

ISSN 2041-4358

( work in progress, v. 0.2.5, Dec., Nov. 2014 )

Gotthard Gunther (1900 - 1984)

After 50 Years. What happend to Morphogrammatics?

Introducing* *directed* *morphoCAs

Motivations

What are cellular automata?

What is the meaning of morphoCAs?

Introduction

New morphoCA Rules

RulesSchemes

Junctional morphoRules

Junctional morphoRules

Transjunctional morphoRules

Transjunctional morphoRules

Morphogram tables

Junctional morphograms

Morphograms

Transjunctional morphograms

TabView of morphograms

Refinements of morphograms

ArrayPlot of Morphograms

ArrayPlot of MorphoRules

ArrayPlot of MorphoRules

CA-Examples, right-oriented

Examples

Examples

Examples

Examples

Decomposition

Introducing* *directed* *morphoCAs

Motivations

Strategies of complexity reductions

Chain of abstractions

CA -> Shape Grammar -> Morphogrammatics

SG -> CA, MG -> CA, morphoCA

Using Shape Grammar to Derive Cellular Automata Rule Patterns (Complex Systems, 17 (2007) 79–102)

Thomas H.Speller, Jr.a, Daniel Whitney, Edward Crawley

Frustration

“This paper shows how shape grammar can be used to derive cellular automata (CA) rules. Searching the potentially astronomical space of CA rules for relevance to a particular context has frustrated the wider application of CA as powerful computing systems.

“An approach is offered using shape grammar to visually depict the desired conditional rules of a behavior or system architecture (a form - function) under investigation, followed by a transcription of these rules as patterns into CA.

Visualization of the abstract

The combination of shape grammar for managing the input and CA for managing the output brings together the human intuitive approach (visualization of the abstract) with a computational system that can generate large design solution spaces in a tractable manner.

“The formula for calculating the rule size space in a one - dimensional system is , where k represents the color possibilities for each state and r is the range or radius of the neighborhood.

It is interesting to note that merely increasing r from 1 to 2 and maintaining the colors at two increases the rule space from 256 to 4.3 billion.

Shape grammar

“Shape grammar is a formal generative approach that has been applied to creating architectural forms.

Shape grammar is a precise and at the same time intuitive methodology in the visual medium for generating languages of design.

Shape grammars can be used analytically, as in reverse engineering, for characterizing and classifying designs and patterns of designs, referred to as styles in architecture. A shape grammar includes a vocabulary of shapes and a set of spatial relations to control the positioning of shapes in the vocabulary.

“Shape grammars are a geometrical design adaptation of Noam Chomsky’s formal (phrase structure or transformational) grammars and are recursively enumerable, having the capability of producing unrestricted languages.

Thus, shape grammars are systems of rules for characterizing the composition of designs in spatial languages.”

Motivations

What are cellular automata?

Cellular automata are well known, mathematically elaborated and documented.

Main features are described by Rudy Rucker and John Walker in Exploring Cellular Automata as:

(1) Parallelism means that the individual cell updates are performed independently of each other. That is, we think of all of the updates being done at once.

(2) Locality means that when a cell is updated, its new color value is based solely on the old color values of the cell and of its nearest neighbors.

(3) Homogeneity means that each cell is updated according to the same rules.

Typically the color values of the cell and of its nearest eight neighbors are combined according to some logico-algebraic formula, or are used to locate an entry in a preset lookup table.

Cellular automata can act as good models for physical, biological and sociological phenomena. The reason for this is that each person, or cell, or small region of space "updates" itself independently (parallelism), basing its new state on the appearance of its immediate surroundings (locality) and on some generally shared laws of change (homogeneity).

https://www.fourmilab.ch/cellab/manual/

After Alex Wuensche, CA rules are defining the geno-type of dynamic systems, while the graphic and sonic patterns of the dynamics are showing the pheno-structure of the dynamic system.

This distinction is of importance and helps to understand the epistemological status of morphoCAs as ‘second-order’ constructs: the geno-type of (the geno-type of the pheno-typ) of CAs. Morphograms are the inscription of the ‘geno-type’ of the rules of CAs.

Mathematically, CAs are quit simple constructs:

A CA is a special automaton defined as a quadruple:

CA = (Γ, Q, N, δ) with

Γ: interconnection graph,

Q: set of states,

N: neighborhood definition,

δ: local dynamics (rules).

= , ,) = '

(Γ,Q) : cell space,

configuration: C

global transitions: Γ: C - C

Combinatorics

For 1D CA: = 8,

rule space : = 256.

For 2D CA: neighborhood = 512,

rule space: = 2^512

What is the meaning of morphoCAs?

One reason to introduce morphic CAs had been the chance to test the recent thesis that morphograms are not just pre-semiotic patterns (form, Gestalt, morphé) of logical functions or patterns of dialogical operations but as much structural rules (dynamis) too. Hence morphoCAs are a tool to study the dynamics of morphograms.

There are some implications and presumptions in the classical definition of CAs that are not been explicitly mentioned in the literature and that are, from the viewpoint of a general thery of writing (graphematics), not as mandatory as it is believed to be.

General features of morphoCAs

a) morphoCAs are based on morphograms, and morphograms are defined retro-recursively as pre-semiotic patterns (morphé) and simultaneously as dynamic rules,

b) morphoCAs are topologically oriented,

c) morphoCAs are complex and heterogenic structurations (systems),

d) morphoCAs have a heterarchical form of organization.

The orientedness of classical CAs is not mentioned in the theory of CA because it is single and therefore trivial.

Retro-recursivity, i.e.memristivity is not known for classical CAs. Retro-grade recursivity is reduced to memory-free and context-independent succession of the calculation, i.e. the applications of the elementary CA rules. Memory in classical CAs is a supplementary and therefore a secundary construct.

Parallelism is extended and replaced by interactivity, homogeneity by heterogeneity (discontexturality) and locallity by polycontexturality.

Mimickry of the rule schemes

Combinatorics for morphoCAs

Introduction

General morphoCA schemes

How does is work? Relabeling and separation.

System of elementary morphic cellular automata rules

There might be a difference between the pheno - and the geno - type of CAs. In other words, the surface - structure as an interpretation of morphograms, i.e. as a function- and set - oriented approach has to be distinguished from a morphogrammatic understanding of CAs that is pre - ordered as a pattern-oriented deep-structure of mappings and sets.

Structurally, the system of with its 256 elements or mappings is inherently symmetric. That is not excluding that the behavior of some functions are asymmetric.

In sharp contrast, the morphogrammatic system with its 15 basic morphograms for is inherently asymmetric. That obviously includes the symmetric subsystem of too.

Example

Step 1

[0, 1, 0] corresponds to [1, 0, 1], hence the next morphic possible step is

[1, 0, 1] -> 0 , [1, 0, 1] -> 1 or [1, 0, 1] -> 2.

Because rule 3 is involved and not rule 8 or 12, the next step is 1 and not 0 or 2.

Step 2

0 | 0 | 1 | 0 | 0 |

□ | 2 | 1 | 0 | □ |

□ | □ | 3 | □ | □ |

[2,1,0] corresponds by relabeling to [1,2,0], hence the next step is: [1,2,0] -> 0 or [1,2,0] -> 1 or [1,2,0] -> 2 or [1,2,0] -> 3.

In contrast to a set-based approach, there are no other possibilities involved on the level of morphogrammatics.

Because rule 15 is involved and not rule 5 or rule 10 or rule 14, the next step is 3 and not 0, 1 or 2.

The head of the morphogram

The morphogram 15

Extensions

The mechanism for is naturally extended to other architectures.

An example with an asymmetric rule scheme for is given by the following scheme.

RuleSchemeR:

a | b | c | d |

- | - | e | - |

The dual scheme is naturally given by:

RuleSchemeL:

a | b | c | d |

- | e | - | - |

And there is a double scheme too:

RuleSchemeRL:

a | b | c | d |

- | e | f | - |

Decomposition of RuleSchemRL

Two-dimensional CA Neigborhood Architecture

Architectonic complementarity

Additionally to the well known duality of classical CA rules, a new and more architectural duality or complementarity is introduced with the right- and left-definition of morphoCA rules.

This architectonic complementarity is a basic feature of general morphic CAs.

Examples for Architectonic Complementarity

Right - oriented CA

Left - oriented CA

The subset of the rule specification, {11112, 12121,12121,11212 }, is defined by the application of the left-rules scheme and marks the difference between the previous right - oriented CA. Without the information produced by the application, both are trivially equal. Until now, the rules are not yet defined accordingly.

The rules depend on an interpretation of the morphograms. A single morphogram might support different interpretations for the definition of the applied rules.

left - oriented

Right&Left - oriented CA

The single-rules of right and left-orientation might be interpreted as reduced cases of the double-left&right-rules.

Comparison: Complementarity of right- and left-oriented CAs

Right-oriented CA Left - oriented CA

New morphoCA Rules

RulesSchemes

Junctional morphoRules

Transjunctional morphoRules

Transjunctional morphoRules

Junctional morphoRules

Morphogram tables

Junctional morphograms

Morphograms

TabView of morphograms

Refinements of morphograms

ArrayPlot of Morphograms

ArrayPlot of MorphoRules

ArrayPlot of MorphoRules

Graphics and Sound examples of morpho

ArrayPlot of MorphoRules

Graphics and Sound examples of morpho

CA-Examples, right-oriented

Examples

Morphogram sequences for

DCKV12 - 3

DCKV12 - 8

DCKV12 - 4

right - oriented

Dynamic representation of ruleDCKV12/14

ruleDCKV12

ruleDCKV14

Catalog of Examples

static rules

dynamic rules

Static rules

static rules

static rules

Catalog of Examples

Catalog of Examples

Decomposition

Tables

Dekomposits