Reduction and Mediation of morphoCAs

Functional Analysis of morphoCAs

Dr. phil Rudolf Kaehr

copyright © ThinkArt Lab Glasgow

ISSN 2041-4358

( work in progress, v. 0.3, October 2015 )

Motivation

Despite the decision for a morphogrammatic foundation of morphic cellular automata, a more function-oriented analysis of morphoCAs is applied to give some new insights into the techniques of reduction and mediation of the complication/complexity of morphic CAs as they have been proposed in previous papers.

Well known features of polycontextural and morphogrammatic systems (structurations), like super-addivity of mediation and super-subtractivity of decomposition of morphoCAs will be sketched.

Stirling reductions

A very first reduction of the quantitative complexity of functions is given by the fact that morphoCAs are not based on exponential functions but on Stirling partitions. Hence, instead of having ternary functions of a three-valued CA, morphoCAs are based on StirlingS2, , hence Sum[StirlingS2[27,m],{m,3}]

The reduction is impressive:

From = 7 625 597 484 987 three-valued ternary functions to Sum[StirlingS2[27,m],{m,3}] = 1 270 932 914 165 three-valued ternary Stirling functions.

There are = 19 683 three-valued binary functions and just 3281 = Sum[StirlingS2[9,m],{m,3}] three-valued binary Stirling patterns. For the unary three-valued case there are = 27 functions. And Sum[StirlingS2[4,m],{m,4}] = 15 for the number of morphograms.

Redundancy-Reductions

Reduction of redundancy in the symbolic (numeric) interpretation of morphogrammatic CA rules. This kind of reduction is not changing the morphogrammatic structure of the morphoCAs but is minimizing the redundant elements of its interpretation. Only the relevant elements (symbols, numbers) of the interpretation of the morphogrammatic compounds necessary for the realization of morphoCAs are considered. Until now, this reduction didn’t play a significant role in the definition of the newly introduced morphoCAs and their claviatures.

To make morphograms visible, they have to interpreted. But the complexity of the interpretations is contextually depending on the whole configuration of the morphogrammatic compounds. There is not just one reduced interpretation available for all situations. For non-reducible morphoCAs the full range of the possible interpretations is necessary to fulfill the definition and realization of the morphoCA.

Single morphograms get different complex interpretations depending on their morphoCA environment.

The morphogram [1] in ruleDM[{1,11,8,4,15}] or ruleDM[{1,11,8,9,15}] demands for an interpretation with the set of all possible mappings in the system of complexity 4: {0,0,0}→0, {1,1,1}→1, {2,2,2}→2, {3,3,3}→3.

In contrast, a similar constellation like ruleDM[{1, 11, 3, 9, 15}] demands in the same system for the interpretion of morphogram [1] just one mapping with {0,0,0}→0.

Depending on the context, there are other interesting cases too.

Just 3 interpretetions needed: ruleDM[{1,2,12,13,14}] with the mapping {0,0,0}→0, {1,1,1}→1, {2,2,2}→2 for morphogram [1]. With a litle change by replacing the morphogram [14] by the morphogram [15], all interpretations accessible in the system are needed.

Because morphoCAs are dynamical systems, it might take a non-trivial amount of steps to observe the necessity of specific interpretations. The morphoCA may work without problems for some steps without a complementation of the interpretations. But it will show lacks of realizations some steps later.

It also turns out that the reductions are not necessarily fully working for arbitrary seeds, like Random seeds.

Nevertheless, not all morphoCAs need a full set of interpretations.

That shows nicely the context-dependence of the Interpretation of morphograms in morphoCAs.

Karnaugh reductions

A further functional reduction might be achieved with the help of Karnaugh maps. Pattern reductions are not the same as Karnough reductions. Pattern reductions are reducing the redundancy of the interpretations of the formulas without changing the formal structure of their definitions (literals, terms). In contrast, Karnaugh mappings are changing the definitions of the functions by reducing the numbers of variables of the original formula albeit without disturbing their functional purpose.

Equivalent to the Karnaugh maps, simplification of Boolean expressions are delivering the same result. For morphoCAs, Boolean expressions have to be adjusted to polycontextural logical formulas and their reduction techniques.

The sketched specifications of the structure of morphoCAs could be understood as a ‘blue print’ for a physical realization as a kind of new multi-layered chips for morphoCA machines (postToffoli).

UML process modelling

A first step to a UML modelling of morphoCAs could encourage to get a glimpse into the complex mechanism of morphoCAs.

Mediation Question:

“Given two elementary CA (Boolean one - dimensional bi - infinite lattices of cells, the evolution of each cell being influenced by its direct neighbors) with known behaviors, what can be said on the behavior of the CA obtained by composing them (e.g., using a logic disjunction)?”

https://scs.carleton.ca/sites/default/files/tr/TR-96-31.pdf

Again, Reduction and Mediation

Functional interpretation of ruleDM[{1, 2, 12, 4, 5}] in .

transjunctional part of funct(ruleDM[{1, 2, 12, 4, 5}])

mediating part of funct(ruleDM[{1, 2, 12, 4, 5}])

Decomposition of ruleDM[{1, 2, 12, 4, 5}] into polylogical sub-systems

Junctional part with transjunctions

mediating part

Cellular automaton of ruleDM[{1, 2, 12, 4, 5}] in

Functional reductions

Example : ruleDM[{1, 2, 12, 4, 5}]

Random seeds

Without reduction, the random seeds are completely defining the morphoCA.

ruleDM[{1, 2, 8, 4, 5}] : parallel

Functional reduction of the morphic rules

Mediation of = (junctional) and with functional reduction: final result is = (, , mediating part). Additionally, the elimination of {0,1,0} of and {0,2,0}, {2,0,0} of happens.

Is a genuine CA like ?

(NKS page : 886 R)

Super-additivity of the mediation of and

Reduction and mediation

Union of and

Yellow represents the background system of both, the blue and the red sub-system.

In the terms ‘blending theory’ (Goguen), the yellow system is the ‘base ontology’, while the red and the blue systems are the ‘input ontologies’ of the process of blending, resulting in the mediation, i.e. the ‘blendoid’, as the interaction of the red and the blue system on the background of yellow system.

It shouldn’t be difficult to understand that the sketched method of separation and mediation works for more complex cases too.

Super-additivity and concept blending

One reason while blending is not an immanent feature of logic, semiotics and computation might be the fact that it happens only on the level of semantics. Like the term “houseboat” and “boathouse”, they are syntactically not produced by blending but by concatenation. The meaning of the composits is achieved by blending, and there is no simple concatenation of the meanings “boat” and “house” to “houseboat” and “boathouse” and super-additively to “amphibious vehicle". Both meaning of “boat” and “house” are per se autonomous.

"A classic example for this is the blending of the concepts house and boat, yielding as most straightforward blends the concepts of a houseboat and a boathouse, but also an amphibious vehicle.” (Kutz, Hois)

“We shall illustrate the concept of sequential interleaving semantics of concurrency with a simple exercise.

Let' s consider the following question from a sophomore parallel programming class :

Find an example of two instructions such that, when executed in parallel, they give a result not obtainable from any corresponding sequential execution sequence.

A possible answer : Assume x = 0 initially and consider the following two programs

x ← x + 1; x ← x + 1

vs.

x ← x + 1 || x ← x + 1

where " || " stands for the parallel, and ";" for the sequential composition of instructions or programs, respectively.

Sequentially, one always gets the same answer : x = 2.

In parallel (when the two assignment operations are executed synchronously), however, one gets x = 1. It appears, therefore, that no sequential ordering of operations can reproduce parallel computation - at least not at the granularity level of high - level instructions as above.

Indeed, if we informally define Φ(P) to be the set of possible behaviors of program P, then the example above only shows that, for S1 = S2 = (x←x+1),

Φ(S1||S2) !⊆ Φ(S1;S2) ∪ Φ(S2;S1) (1)

However, it turns out that, in this particular example, it indeed is the case that

Φ(S1||S2) ⊆ Φ(S1;S2) ∪ Φ(S2;S1) ∪ Φ(S1) ∪ Φ(S2) (2)

and no finer granularity is necessary to model Φ(S1||S2), assuming that, in some of the sequential interleavings, we allow certain instructions not to be executed at all.” (Tosić)

Φ(S1||S2) ::

Φ(S1;S2) ∪ Φ(S2;S1) ∪ Φ(S1) ∪ Φ(S2) :

Φ(S1;S2) ∪ Φ(S2;S1) : double serial composition,

Φ(S1) ∪ Φ(S2) : super-additivity

Minimization of morphoCA functions

http : // www.toves.org/books/logic/

MG - composition -> value-interpretation -> functional reduction -> MG-interpretation, with such formal reductions of morphoCAs a context of technical realizations seems to be sketched.

The proposed functional reduction of morphoCA is not changing its morphogrammatic base, i.e. its morphograms, but the symbolic interpretation of the morphograms only. Therefore, functionally reduced morphoCAs are still morphoCAs, and nothing else.

ruleDM[{1, 2, 12, 4, 5}]

The decomposition of ruleDM[{1, 2, 12, 4, 5}] into polylogical sub-systems might be generalized towards the following scheme.

Full rule scheme

Frame scheme

Transjunctional part mediative part

As an example ruleDM[{1, 2, 12, 4, 5}] might be decomposed:

Transjunctional part mediative part

The decomposed scheme for ruleDM[{1, 2, 12, 4, 5}] resumed

Reduced example of ruleDM[{1, 2, 12, 4, 5}]

Application of the reduced ruleDM[{1, 2, 12, 4, 5}]

Table notation of the reduced ruleDM[{1, 2, 12, 4, 5}]

Elimination of the reduced values (in blue)

A different notation

A/B | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 |

0 | 0 | 2 | 1 | 1 | 1 | 0 | 2 | 0 | 0 |

1 | 1 | 1 | 0 | 2 | 1 | 0 | 1 | 1 | 1 |

2 | 1 | 0 | 2 | 2 | 1 | 2 | 2 | 0 | 2 |

C | 0 | - | - | 1 | - | - | 2 | - | - |

val (ruleDM[{1, 2, 12, 4, 5}]) = 1 :

A/B | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 |

0 | □ | □ | 1 | 1 | 1 | □ | □ | □ | □ |

1 | 1 | 1 | □ | □ | 1 | □ | 1 | 1 | 1 |

2 | 1 | □ | □ | □ | 1 | □ | □ | □ | □ |

C | 0 | - | - | 1 | - | - | 2 | - | - |

val(ruleDM[{1,2,12,4,5}]) = 1 iff

A0B2C0 + A0B0C1 + A0B1C1 +

A1B0C0 + A1B1C0 + A1B1C1+ A1B0C2 + A1B1C2 + A1B2C2 +

A2B0C0 + A2B1C1

ruleDCl[{1, 2, 8, 4}]

Reducible and non-reducible functional representations

Example : ruleDM[{1, 7, 3, 13, 10}]

Functional reduction of ruleDM[{1,7,3,13,10}]

Functional reduction of ruleDM[{1,11,3,4,15}]

Random seed

Functional reduction of ruleDM[{1,11,3,13,15}]

Functional reduction of ruleDM[{1,11,3,4,15}]

Random seed

Reduction : ruleDM[{1, 11, 3, 4, 15}]

ruleDM[{1, 11, 3, 4, 15}] is reducible to table:

Example ruleDCl[{1, 2, 3, 4}]

Reductions by Karnaugh maps

“Karnaugh maps reduce logic functions more quickly and easily compared to Boolean algebra. By reduce we mean simplify, reducing the number of gates and inputs. We like to simplify logic to a lowest cost form to save costs by elimination of components. We define lowest cost as being the lowest number of gates with the lowest number of inputs per gate.”

x' y' z + y z' + x y

http : // www.electronics - tutorials.ws/combination/comb_ 1. html

Further example

Towards Karnaugh maps

x/yz | 00 | 01 | 11 | 10 |

0 | 0 | 1 | 0 | 1 |

1 | 0 | 0 | 1 | 1 |

http : // www.toves.org/books/logic/

Examples for

Example1: ruleDM[{1, 11, 3, 13, 15}]

ruleDM[{1, 11, 3, 13, 15}] is minimized manually to the table :

Example2: ruleDM[{1, 11, 3, 4, 15}]

Equality test: ruleDM[{1,11,3,4,15}] equal reduct(ruleDM[{1,11,3,4,15}])

ruleDM[[{1, 11, 3, 4, 15}] is minimized manually to the table :

Not reduced table for ruleDM[{1, 11, 3, 4, 15}].

Irreducible rules

Irreducible rules are playing the same role for morphoCAs as the irreducible binary functions like NAND, XOR for binary reductions. With NAND or NOR, all other two-valued binary function are defined. Because they are not reducible they are used as elementary devies in electronic circuit consturctions.

The question for morphic patterns arises: How many irreducible patterns exist for ?

Do they have the same property to define all other functions?

With ruleDM[{1, 11, 8, 4, 15}] non-reducible, its dual function might be irreducible too. (?)

Example3 : ruleDM[{1, 11, 8, 4, 15}]

ruleDM[{1, 11, 8, 4, 15}] can not be minimized without damaging the original result.

Example4 : ruleDM[{1, 11, 12, 4, 15}]

ruleDM[{1, 11, 12, 4, 15}] can not be minimized without damaging the original result.

http : // www.isaet.org/images/extraimages/S1213024.pdf

http : // www.ijser.org/researchpaper %5 COptimization - of - Ternary - Combinational - System.pdf

Random seed

Example: ruleDM[{1, 11, 12, 9, 15}] : irreducible

Without {1, 2, 3} -> 0:

Reducible examples

Mapping morphoCA rules onto computational diagrams

ruleDCl[{1, 2,3,4}]

ruleDM[{1, 11, 3, 9, 15}]

A0B0C0 + A1B0C0 + A2B0C0 + A0B0C1 + A0B0C2 + A0B1C0 + A0B2C0

A0B0C0 + A0B0C2 + A0B1C0 + A0B2C0 + A1B0C0 + A2B0C0 + A0B0C1

A0 (B0C0 + B0C2 + B1C0 + B2C0) + A1B0C0 + A2B0C0 + A0B0C1

A0B0C0 + A1B0C0 + A2B0C0 + A0B0C1 + A0B0C2 + A0B1C0 + A0B2C0

A0B0C0 + A0B0C2 + A0B1C0 + A0B2C0 + A1B0C0 + A2B0C0 + A0B0C1

A0 (B0C0 + B0C2 + B1C0 + B2C0) +(A1+A2+A0(C0 + C1))

Multi-layer structure of morphoCAs

Example: ruleDM[{1, 11, 3, 9, 15}] step-wise realization

start (init) : yellow, red

construction: blue, yellow, red, yellow

iteration of construction

Polylogical interpretation of the reduction

S1 = {0, 1}, S2 = {1, 2}, S3 = {0, 2}

Systems: ruleDM[{1,11,3,9,15}]

Internal mappings: ruleDM[{1,11,3,9,15}]

Again, another formal approach

ruleDM[{1, 11, 3, 9, 15}]

The automaton at the level of a single layer of the multilayer morphoCAs is not necessarily running on its own without the inclusion of its neighbor components. Multi-layer moprhocAs are defined by their interaction with the partial automata of their neighbor layers and are therefore depending on the definitions of those partial CAs of the complementing layers of the whole morphoCA.

In this case it is supposed that the clocks of the different automata of different layers are synchronized.

Visualization of classical morphograms

Example

The morphoCA of ruleDM[{1, 11, 12, 4, 15}] needs, to work as a CA, additionally to the morphic skeleton values of the morphograms [{1, 11, 12, 4, 15}], some embeddings as semiotic or symbolic interpretations of the rules. That doesn't come as a surprise. The skeleton ‘values’ of the morphograms are also just interpretations of the morphograms and not their direct representations.

Further simple examples for parallelism

ruleDCM[{1, 2, 12, 13, 5}]

ruleDM[{1, 2, 12, 13, 5}]

Gray code

Reduction of ECA rules via sub-rule elimination

Example1

Reducts = {{1, 0, 1} -> 1, {1, 1, 1} -> 1}: sub-rules 11 and 16.

Example2

Reduct = {{1, 0, 1} -> 1}: sub-rule 12.

Reducts : {0, 1, 1} -> 1, {1, 1, 0} -> 1, {1, 1, 1} -> 0

x/yz | 00 | 01 | 11 | 10 |

0 | 0 | 1 | - | 0 |

1 | 1 | 0 | - | - |

“Situations can arise where a circuit has N input signals, but not all combinations of inputs are possible. Or, if all combinations of inputs are possible, some combinations might be irrelevant.”

Non - reducible ECA example

x/yz | 00 | 01 | 11 | 10 |

0 | 1 | 1 | 0 | 0 |

1 | 0 | 1 | 0 | 1 |

The ECA rule 110 belongs to the balanced non-reducible rules.

More complex examples:

Manual reduction of ruleDCKV[{1111,1123,1211,1221,2121,2211,2221,2112,2132,1231,2231,2311,2321,2331,2301}]

Some sub - rules are redundant, the rest gets a significant reduction.

Result of reduction

Output - oriented notation