Reduction and Mediation of morphoCAs
                     Functional Analysis of morphoCAs

Dr. phil Rudolf Kaehr
© ThinkArt Lab Glasgow
ISSN 2041-4358
( work in progress, v. 0.3, October 2015 )


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 Reduction and Mediation_1.png ternary functions of a three-valued CA, morphoCAs are based on StirlingS2, Reduction and Mediation_2.png, hence Sum[StirlingS2[27,m],{m,3}]

The reduction is impressive:
Reduction and Mediation_3.png= 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 Reduction and Mediation_4.png = 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 Reduction and Mediation_5.png= 27 functions. And Sum[StirlingS2[4,m],{m,4}] = 15 for the number of morphograms.


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)?”

Again, Reduction and Mediation

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

Reduction and Mediation_7.png

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

Reduction and Mediation_8.png

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

Reduction and Mediation_9.png

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

Junctional part with transjunctions

Reduction and Mediation_10.png

mediating part

Reduction and Mediation_11.png

Cellular automaton of ruleDM[{1, 2, 12, 4, 5}] in Reduction and Mediation_12.png

Reduction and Mediation_13.png

Reduction and Mediation_14.gif

Functional reductions

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

Reduction and Mediation_15.png

Reduction and Mediation_16.gif

Random seeds

Reduction and Mediation_17.gif

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

Reduction and Mediation_18.gif

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

Reduction and Mediation_19.png

Reduction and Mediation_20.gif

Functional reduction of the morphic rules

Reduction and Mediation_21.png

Reduction and Mediation_22.gif

Reduction and Mediation_23.png

Reduction and Mediation_24.gif

Reduction and Mediation_25.png

Reduction and Mediation_26.gif

Mediation of Reduction and Mediation_27.png= (junctional) and Reduction and Mediation_28.png with functional reduction: final result is Reduction and Mediation_29.png= (Reduction and Mediation_30.png, Reduction and Mediation_31.png, mediating part). Additionally, the elimination of {0,1,0} of Reduction and Mediation_32.pngand {0,2,0}, {2,0,0} of Reduction and Mediation_33.png happens.

Is Reduction and Mediation_34.png a genuine CA like Reduction and Mediation_35.png?

(NKS page : 886 R)

Super-additivity of the mediation of Reduction and Mediation_36.pngand Reduction and Mediation_37.png

Reduction and Mediation_38.png

Reduction and Mediation_39.png

Reduction and Mediation_40.png

Reduction and Mediation_41.png

Reduction and mediation

Reduction and Mediation_42.gif

Reduction and Mediation_43.gif

Reduction and Mediation_44.png

Union of Reduction and Mediation_45.pngand Reduction and Mediation_46.png

Reduction and Mediation_47.gif

Reduction and Mediation_48.png

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)

Reduction and Mediation_49.png

http : // %20 as %20 Blending/Dissemination %20 as %20 Blending.html

http : // - 2005 - parallel_vs _sequential _threshold _cellular _automata.pdf

“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
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

Reduction and Mediation_50.gif

Minimization of morphoCA functions

Reduction and Mediation_51.gif

http : //

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

Reduction and Mediation_52.png

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}]

Reduction and Mediation_53.png

Reduction and Mediation_54.png

Reduction and Mediation_55.gif

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

Reduction and Mediation_56.png

Full rule scheme

Reduction and Mediation_57.png

      Frame scheme

Reduction and Mediation_58.png

      Transjunctional part                             mediative part

Reduction and Mediation_59.png

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

Reduction and Mediation_60.png

      Transjunctional part                                    mediative part

Reduction and Mediation_61.png

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

Reduction and Mediation_62.png

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

Reduction and Mediation_63.png

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

Reduction and Mediation_64.png

Reduction and Mediation_65.gif

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

Reduction and Mediation_66.png

Elimination of the reduced values (in blue)

Reduction and Mediation_67.png

Reduction and Mediation_68.png

Reduction and Mediation_69.gif

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}]

Reduction and Mediation_70.png

Reduction and Mediation_71.gif

Reduction and Mediation_72.png

Reducible and non-reducible functional representations

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

Reduction and Mediation_73.png

Reduction and Mediation_74.gif

Reduction and Mediation_75.png

Reduction and Mediation_76.png

Reduction and Mediation_77.png

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

Reduction and Mediation_78.gif

Reduction and Mediation_79.png

Reduction and Mediation_80.png

Reduction and Mediation_81.gif

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

Reduction and Mediation_82.png

Reduction and Mediation_83.png

Reduction and Mediation_84.gif

Reduction and Mediation_85.png

Reduction and Mediation_86.gif

Random seed

Reduction and Mediation_87.gif

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

Reduction and Mediation_88.png

Reduction and Mediation_89.gif

Reduction and Mediation_90.gif

Reduction and Mediation_91.gif

Reduction and Mediation_92.png

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

Reduction and Mediation_93.png

Reduction and Mediation_94.gif

Random seed

Reduction and Mediation_95.png

Reduction and Mediation_96.gif

Reduction and Mediation_97.gif

Reduction and Mediation_98.png

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

Reduction and Mediation_99.png

Reduction and Mediation_100.gif

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

Reduction and Mediation_101.png

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

Reduction and Mediation_102.png

Reduction and Mediation_103.gif

Reduction and Mediation_104.gif

Reduction and Mediation_105.png

Reduction and Mediation_106.png

Reduction and Mediation_107.png

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.”

http : // - 8/karnaugh - maps - truth - tables - boolean - expressions/

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

Reduction and Mediation_108.gif

http : // www.electronics - 1. html

Further example

Reduction and Mediation_109.gif

http : // - 8/karnaugh - maps - truth - tables - boolean - expressions/

http : // %5 CFormulation - and - Design - of - Useful - Logic - Gates - Using - Quaternary - Algebra.pdf

Towards Karnaugh maps

x/yz 00 01 11 10
0 0 1 0 1
1 0 0 1 1

Reduction and Mediation_110.gif

http : //

Examples for Reduction and Mediation_111.png

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

Reduction and Mediation_112.png

Reduction and Mediation_113.gif

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

Reduction and Mediation_114.png

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

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

Reduction and Mediation_115.gif

Reduction and Mediation_116.png

Reduction and Mediation_117.png

Reduction and Mediation_118.png

Reduction and Mediation_119.png

Reduction and Mediation_120.gif

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

Reduction and Mediation_121.png

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

Reduction and Mediation_122.png

Reduction and Mediation_123.png

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 Reduction and Mediation_124.png?

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. (?)

Reduction and Mediation_125.gif

Reduction and Mediation_126.png

Reduction and Mediation_127.gif

Reduction and Mediation_128.png

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

Reduction and Mediation_129.png

Reduction and Mediation_130.gif

Reduction and Mediation_131.png

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

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

Reduction and Mediation_132.gif

Reduction and Mediation_133.png

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

http : //

http : // %5 COptimization - of - Ternary - Combinational - System.pdf

Reduction and Mediation_134.png

Reduction and Mediation_135.png

Random seed

Reduction and Mediation_136.gif

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

Reduction and Mediation_137.png

Reduction and Mediation_138.gif

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

Reduction and Mediation_139.gif

Reduction and Mediation_140.png

Reduction and Mediation_141.png

Reducible examples

Reduction and Mediation_142.png

Reduction and Mediation_143.gif

Reduction and Mediation_144.png

Reduction and Mediation_145.png

Reduction and Mediation_146.gif

Reduction and Mediation_147.png

Mapping morphoCA rules onto computational diagrams

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

Reduction and Mediation_148.png

Reduction and Mediation_149.gif

Reduction and Mediation_150.png

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

Reduction and Mediation_151.png

Reduction and Mediation_152.png

Reduction and Mediation_153.gif

Reduction and Mediation_154.png

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

Reduction and Mediation_155.gif

construction: blue, yellow, red, yellow

Reduction and Mediation_156.gif

Reduction and Mediation_157.gif

iteration of construction

Reduction and Mediation_158.gif

Reduction and Mediation_159.gif

Polylogical interpretation of the reduction

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

Reduction and Mediation_160.png

Reduction and Mediation_161.png

Systems:   ruleDM[{1,11,3,9,15}]
Reduction and Mediation_162.png

Internal mappings:  ruleDM[{1,11,3,9,15}]
Reduction and Mediation_163.png

Reduction and Mediation_164.gif

Reduction and Mediation_165.gif

Again, another formal approach

Reduction and Mediation_166.png

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

Reduction and Mediation_167.gif

Reduction and Mediation_168.png

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.

Reduction and Mediation_169.png

Reduction and Mediation_170.png

Reduction and Mediation_171.png

Reduction and Mediation_172.png

Reduction and Mediation_173.png

Visualization of classical morphograms

Reduction and Mediation_174.png


Reduction and Mediation_175.png

Reduction and Mediation_176.png

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

Reduction and Mediation_177.png

Reduction and Mediation_178.gif

Reduction and Mediation_179.png

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

Reduction and Mediation_180.png

Reduction and Mediation_181.gif

Reduction and Mediation_182.png

Reduction and Mediation_183.png

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

Reduction and Mediation_184.gif

Reduction and Mediation_185.png

Gray code

Reduction and Mediation_186.png

Reduction and Mediation_187.gif

Reduction and Mediation_188.gif

Reduction of ECA rules via sub-rule elimination


Reduction and Mediation_189.png

Reduction and Mediation_190.png

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

Reduction and Mediation_191.gif

Reduction and Mediation_192.gif


Reduction and Mediation_193.png

Reduction and Mediation_194.png

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

Reduction and Mediation_195.png

Reduction and Mediation_196.gif

Reduction and Mediation_197.gif

Reduction and Mediation_198.png

Reduction and Mediation_199.png

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

Reduction and Mediation_200.png

Reduction and Mediation_201.gif

Reduction and Mediation_202.gif

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 Reduction and Mediation_203.png combinations of inputs are possible. Or, if all Reduction and Mediation_204.pngcombinations of inputs are possible, some combinations might be irrelevant.”

Reduction and Mediation_205.png

Reduction and Mediation_206.png

Non - reducible ECA example

Reduction and Mediation_207.png

Reduction and Mediation_208.png

Reduction and Mediation_209.gif

Reduction and Mediation_210.png

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.

Reduction and Mediation_211.png

Reduction and Mediation_212.png

Reduction and Mediation_213.gif

More complex examples: Reduction and Mediation_214.png

Reduction and Mediation_215.gif

Reduction and Mediation_216.png

Reduction and Mediation_217.gif

Reduction and Mediation_218.png

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.

Reduction and Mediation_219.png

Reduction and Mediation_220.gif

Result of reduction

Reduction and Mediation_221.png

Reduction and Mediation_222.gif

Output - oriented notation

Reduction and Mediation_223.png

Reduction and Mediation_224.gif

Created with the Wolfram Language