Compositions and Decompositions of morphoCAs

       A collection of different provisional approaches to complexity reduction

Dr. phil Rudolf Kaehr
© ThinkArt Lab Glasgow
ISSN 2041- 4358
( work in progress, vs. 0.1, Jan. 2015 )


Reduction of the structural complexity of complex cellular automata.

“A disadvantages of the new framework lies in its extreme complexity. It is possible to use parallel computers to do analysis of the configurations contained by n = 3 (the space already includes more than Decomposition2_1.gif configurations). It is impossible using today’s technology to process the n = 5 space due to the extreme growth of structural complexity Decomposition2_2.gifx 32! configurations).”

This paper is certainly not offering the final solution of the question of a decomposition of complex cellular automata but at least a very first step towards an introduction of the question as such.

The question doesn’t get its proper attention in the academic research about the complexity of CAs.

Without a mechanism of a decomposition, the whole theory of CAs remains in the dark, unfinished and just hinting to quantities that are qualitatively denying any computational solution.

With that, the elaborations of composition/decomposition of classical automata in general including studies of cellular automata is not touched at all. Those results are not questioned at all with the introduction of the question of composition/decomposition of complex, i.e. polycontextural and morphic CAs.

Big numbers are still a dream and not a constructive advise. Nevertheless this dream is even obsolete if we accept a positional approach to complexity as we know it from the management of natural numbers.

The analogy of the problem of multi-valued logics is well recognized if not understood at all.

“It might be thought that CA with greater values of κ have also greater computational power, however this is not true. It is true that rules with κ = 1 can be easily characterized because they describe linearly separable CA, but even rules with κ = 2 can have extremely complex behaviors as in the case of rule 110, which is known to be equivalent to a Universal Turing Machine.
This phenomenon, already hypothesized by Wolfram, is called threshold of complexity. It is noteworthy to mention that not all rules with high complexity index have complex behaviors, [...].”

Giovanni E. Pazienza, Aspects of algorithms and dynamics of cellular paradigms

Do complex morphoCAs have a higher computational power than classical CAs?

This question is similar to the common questions about the computational power of other expanded concepts, like multiple-valued logics, multi-head, -tape etc. Turing Machines and so on.

The answer there is NO. This is proven by all kind of reduction principles and techniques.

Hence, the new question is: Are morphoCAs reducible to classical CAs?

An answer to such a question is possible only if there is an elaborated definition of morphoCAs.

Prior to such a definition some experiences with different approaches and developments of morphoCAs is necessary.

A direct answer simple would be a hint to the formal difference of CAs and mophoCAs:
CA = (S,N,f) ≠ morphoCA = (CA, ∐).
But to understand the operator “∐” as a distributor and mediator of genuine CAs some experiences have to be made.

What follows is a further contribution to expand the field of experiences with morphoCAs.


Each complex morphoCA can be decomposed into a complexion of simple total and partial CAs. The decomposition is a complexion of partial and total CAs distributed and mediated over a contextural or kenomic grid. Simple CAs are defined by total functions and are having the lowest degree of complexity. Simple CAs are based on total functions and are the well known classical elementary CAs.

Hence each decomposite of a complex CA is a classical CA with in principle two and only two states and one and only one general transition rule.

“In summary, CA are dynamical systems that are homogeneous and discrete in both time and space, and that are updated locally in space.
A d-dimensional CA is specified by a triple (S, N, f ) where S is the state set, N ∈ Decomposition2_3.gifDecomposition2_4.gif is the neighborhood vector, and f : Decomposition2_5.gif−→ S is the local update rule. We usually identify a CA with its global transition function G, and talk about CA function G, or simply CA G. In algorithmic questions G is, however, always specified using the three finite items S, N and f.

Following suggestions by S. Ulam, he [John von Neumann] envisioned a discrete universe consisting of a two-dimensional mesh of finite state machines, called cells, interconnected locally with each other.

On the other side, complex CAs are super-additive compositions of partial and total CAs distributed over a grid of a m-contextural polyverse.

Partial CAs are not genuinely definable in the framework of simple, i.e. elementary CAs.


Morphogrammatic decomposition

Again, it easily happens to confuse the morpgram-based approach to elementary CAs with the original function-based approach as we know it. That happens naturally because of the coincidence of the objectified results.

What differs is how the results are achieved (produced) and not so much what is reached (produced).

Functional representations of the morphoCAs are in fact simulations in the realm of functions, and not morphic realizations.

Again, there is no ‘natural’ method to extend the classical ECA concept to a ‘trans-classical’ theory on the base of set-theoretical functions.

An extension of the function-based approach is easily achieved with an extension of the value-set from 2 elements to n>2. But such a concept of extension is abstract and there are no systematic criteria to chose the elements. The value-set might be arbitrarily extended to any size.

The analogous situation happened and still happens with the transition from 2-valued to multiple-valued logics.

Hence, the morphogrammatic approach to ECAs is an interpretation of the basic morphograms of morphogrammatics.

In the case of complexity/complication of 4, i.e. for MGDecomposition2_6.gif, there are just 15 basic morphograms. To define the classical ECAs, not more than 8 morphograms are necessary as a base for interpretation.

This way to interpret morphograms by values and relabeling is not yet taking the genuine morphogrammatic level into account. Morphograms are introduced by differences and not by values of a function. The difference-oriented approach to morphogrammatic CAs is ruled by the ε/ν-structuration of the domain of computation.

The first presentation of morphogrammatic based CAs had been restricted on a combination of just 4 to 5 morphograms per automaton.

The morphogrammatic approach enables an easy method of combining basic cellular automata to compound structures of well defined complex morphic automata of arbitrary complexity.

The tool set for the construction of complex morphoCAs contains the 15 basic morphograms and the two rules of composition: ruleCl for ‘classical’ and ruleM for ‘trans-classical’ structurations.

The tool set allows to define morphogrammatic compounds of basic morphograms for more complex CAs.

In this sense, a morphogram Decomposition2_7.gif is defined as a mediation of 3 basic morphograms: e.g.

Decomposition2_8.gif = (Decomposition2_9.gif Decomposition2_10.gif) Decomposition2_11.gif.

Morphic CAs are therefore defined as interpretations of additive and mediative compositions of morphogrms.

Additive compositions have the form:

Decomposition2_12.gif, Decomposition2_13.gif, ..., Decomposition2_14.gif], with Decomposition2_15.gif for CAs.

While mediative compositions have the reflectional and interactional distribution form:
Decomposition2_16.gifDecomposition2_17.gif∐, ..., ∐ Decomposition2_18.gif].

Mediative de/composition examples for m=3:





http : // on Polycontextural Logics/Notes on Polycontextural Logics.html

Other definitions and derivations from the morphogrammatic approach are naturally possible as different and non-standard interpretations of morphograms.

The most obvious approach to decomposition is certainly given by decomposition of a morphoCA into its defining morphograms.

The main question is a mathematical and logical one: How to decompose lossles 9-ary functions/relations into ternary functions/relations? In other words: How to decompose without loss complex CAs into elementary CAs?

Descriptive example:







Functional representation of morphoCAs

For example, the morphoCA defined by the ruleM[{1,8,9,11,15}], which is a composition of the morphograms [1], [8], [9], [11] and [15] , is decomposed accordingly into its morphograms.

Each CA rule based on a morphogram has a well defined structure that is defining its behavior.

The composition of the morphic rules is generating a behavior of the composition that is not easily deduced from the behavior of its morphic parts.

Because the morphoCA ruleM[{1,8,9,11,15}] entails the morphogram [15], the automaton has to be defined symbolically for all its parts over the complexion of 4.
Therefore, the morphogram [1] is represented by the set of {0,0,0}→0, {1,1,1}→1, {2,2,2}→2, {3,3,3}→3 of representations and not just for the rules for the case of two states: {0,0,0}→0, {1,1,1}→1.







Order theoretic classification of the morphogrammatic system


Junctional compositions with frame super-additivity

Junctional compositions are super-additive compositions of elementary morphoCAs.



jjj 1 2 3
1 and - -
2 - and -
3 - - and





Additive composition of the distributed rules






additive composition of rule110



Additive compositions without super-additivity








Symbolic representation of the morphic ruleCl[{1,7,8,9}] in Decomposition2_56.gif







ruleCl 1 2 3 4
1 [1]
2 [7]
3 [8]
4 [9]


ruleCl 1 2 3 4
1 Decomposition2_64.gif
2 Decomposition2_65.gif
3 Decomposition2_66.gif
4 Decomposition2_67.gif

Additive composition of ruleCl[{1, 7, 8, 9}]


Transjunctional compositions (with super-additivity)

It is well-known that complex configurations can be reduced with more or less no sacrifice to non-complex binary symbolic constellations. Therefore, an introduction of more than two states of a automaton seems to be redundant and obsolete.

Hence, complex automata, cellular and others, have to be defined differently.

One successfully method is the mediation of dichotomous automata by the mechanism of polycontextural bifunctoriality.

Without much decoration, the transjunctional ternary rules are just equally defined like the transjunctional binary functions of polycontextural logics.

Transjunctional functions are build on the base of mediated partial functions. The same applies for transjunctional rules of complex morphoCAs.

The overwhelming amount of morphoCAs are defined as transjunctional CAs.

Excerpts from The Abacus of Universal Logics

“How to explain this kind of distribution?What we learned in place - valued logics was that transjunctions are rejecting value - alternatives and marking this rejection with values not belonging to the sub - system from which the rejection happens.The frame values of the transjunction remain accepted. Thus, there is nothing mentioned which could justify this "wild" decomposition and distribution of parts of a transjunction over different sub - systems and being linked with a single core value to the guest sub - system.
Again, the more mathematical settings of transjunctions by universal algebras and category theory have failed to give any further information usable for implementation.

Transjunctions are understood in the proposed setting as compositions of partial functions.Thus, the parts have to be mediated to build the whole function.Hence, a frame element has to function as a mediation point, additional to the core elements as rejectional
elements. Without such a partial mediation of the rejectional parts the partial function would be free floating in a neighbor system without a systematic reason. Hence, with this frame -- element being mediated the partial function is fixed at it place in the neighbor system. On the other hand, if both frame - elements would be distributed there wouldn' t be a transjunction but a replication of a transjunctional morphogram as such without a rejectional behavior.

This argumentation gets some justification in the context of polycontextural logics.Without the "additional" distribution of a frame - element the tableaux - based proof systems wouldn' t work properly. This is based on experiences and not on proofs. There is still no general mathematical framework to produce reasonable proofs for transjunctional situations. [Today, the mathematization might be solved by the appliction of polycontextural bifunctoriality of poly-category theory.]

Such insights in the functioning of distributed transjunction becomes quite clear in the proposed notational order of the sub - systems by the tabular matrix of dissemination." R. Kaehr, The Abacus of Universal Logics, 2007, p. 30



The Abacus of Universal Logics



S1.1=transjunction S2.1 S3.1

Decomposition2_73.gif nil nill
Decomposition2_74.gif Decomposition2_75.gif S3.2NIL
Decomposition2_76.gif S3.2Nil Decomposition2_77.gif









Further example















Super-additivity of Decomposition2_100.gif compositions

Excerpts from  “Memristics : Dynamics of Crossbar Systems

http : // - Crossbars/Poly - Crossbars.pdf

“Mediation of two universes results super-additively in a compound of three universes.

mediation:Decomposition2_101.gifDecomposition2_102.gif Decomposition2_103.gif

mediation: Decomposition2_104.gif   Decomposition2_105.gif  Decomposition2_106.gif

Super-additivity is not the same as commutativity for categorical composition and yuxtaposition.

   f ◦ g : A → C  for f: A → B &  g : B → C   

   f ⊗ g : A ⊗C →  B ⊗ D  for  f : A → B &  g : C → D

Hence, the composition of the morphisms f and g, f ◦ g ,results in the morphism A → C.

But the mediation of the morphism  fDecomposition2_107.gif and fDecomposition2_108.gif, Decomposition2_109.gif results in the super-additive compound Decomposition2_110.gifDecomposition2_111.gif






Matching conditions for equality based mediation


cod(Decomposition2_122.gif) cod(fDecomposition2_123.gif) cod(fDecomposition2_124.gif) cod(fDecomposition2_125.gif)
cod(Decomposition2_126.gif) cod(fDecomposition2_127.gif) cod(fDecomposition2_128.gif)
cod(Decomposition2_129.gif) cod(fDecomposition2_130.gif) 

Interplay of polycontextural operators







Mediation of Decomposition2_137.gif composites

In analogy to the proposed ‘abacus of logics’ an antagonistic approach to the idea of a ‘universal’ logic, an abacus of cellular automata might be proposed.

CA =(S, N, f )

A cellular automaton CA is defined as a triple (S,N,f) with the following properties.

“A d-dimensional CA is specified by a triple (S, N, f ) where S is the state set, N ∈ Decomposition2_138.gif)Decomposition2_139.gif is the neighborhood vector, and f : Decomposition2_140.gif−→ S is the local update rule.”

“At any given time, the configuration of the automaton is a mapping c : Decomposition2_141.gif −→ S that specifies the states of all cells.

“The set Decomposition2_142.gif is the set of all configurations.”  (Kari)

Hence, a mediation of a multitude of discontextural CAs has to consider the mediation of its constituents: states S, neigborhood N and update rule f.



Valuation of Decomposition2_145.gif


Mediation of Decomposition2_147.gif


Decomposition of Decomposition2_149.gif
Decomposition2_150.gif [trans, junct, junct].
The values of min, max are defining the frame values of the mediation. The core values are variable in the context of the frame values.


Superoperators over polyCAs

Given the framework of mediated CAs, there are not just the intracontextural transitions to define but als a managment of interactions between discontextural CAs to manage. In the literature to polycontextural systems they are called ‘super-operators’, short sops.

The main super-operators on complexions of CAs are:
1. interactional
2. reflectional, iterative and accretive
3. interventional.

Example for a interactional and compositional complexion of CAs

Excerpts from  "Playing Chiasms and  Bifunctoriality"

“The super-operators SOPS are the programming strategies, the distributed processor on the kenomic matrix are the programmed machines to be programmed firstly, contexturally, i.e. depending on the loci/places of the processors and secondly, by the types of operations involved. The involved operations then are the localized junctional, transpositional, replicational and reflectional logico-arithmetic operations.

The super-operators are activating or deactivating the disseminated processors according to their operational structure.

Because of the exchange mechanism of operator and operand on the level of the hardware processors, a feature that is not realizable within the possibilities of classical processors and architectures, it is proposed that by taking into account the new possibilities of memristive approaches to realize such mechanisms of interchangeability with a successive application of devices based on memristors and memristive systems, such limits of traditional computation might be, in principle, overcome.

It is understood that the main novelty of memristors is not in the domain of quantities, like speed and storage, but in the functionality of the exchangeability of “processor” and “memory” functions of the “same” computing device at the “same” place.

Hence, the dissemination, defined by distrubution and mediation, of the activity, i.e. inter- and trans-activity of the processors of the grid, is managed by the interchangeability of the main features of computability, computation and memorization, and realized by the application of memristors and their distribution in crossbar systems.

Logical and symbolic processes are distributed over the kenomic matrix. But this distribution is not a static architectonic fact but is involved in the process of interactions between different processors. In this sense, the relization of a transpositional distribution is seen as an interaction between different processors. The ‘main’ processor of a transjunctional operation is ‘sending’ an activation messige to the transpositioned processor to realize the transjunction addressed by the main processor. The main processors in the design are the ‘diagonal’ processors of the grid. This is not a restriction to a mxm-matrix. Other configurations are easily produced, and each processor might play the role of a ‘main’ processor.

The super-operators are activating or deactivating the disseminated processors according to their operational structure.”

http : // %20 Chiasms/Playing %20 Chiasms %20 and %20 Bifunctoriality.html

Those insights shall be directly applied to the special case of complex polyCAs.


Short notation







How are such complexities of cellular automata to understand?

Given 2 CAs, a mediation of both is producing a third contexture which offers the place for a third CA.

A possible interpretation of the activities of the 3 mediated CAs might be expressed as a ‘parallel’ computation of the first two and as a computation of the interaction of both mediated CAs at third place as the ‘product’ of the computations of the two CAs.

Therefore it has to be show that an activity of a complex CA of degree 3 is understandable as a mediated activity resulting in complexion as a result.

The following example of a complex CA might be seen as a parallel realization of Decomposition2_158.gif and

reflected in Decomposition2_162.gif.

This is certainly not yet obvious at a first glance and more elaborated examples have to be studied. Without doubt there has also modifications of the simple and ‘introductionary’ model to elaborted.

The functionality of proper parts like Decomposition2_163.gif, Decomposition2_164.gif and partial functions as Decomposition2_165.gifhas to analyed more properly.

Concrete example


Decomposition2_167.gif Decomposition2_168.gif Decomposition2_169.gif Decomposition2_170.gif
Decomposition2_171.gif Decomposition2_172.gif - -
Decomposition2_173.gif Decomposition2_174.gif Decomposition2_175.gif -
Decomposition2_176.gif Decomposition2_177.gif - Decomposition2_178.gif

http : // - Crossbars/Poly - Crossbars.html

Super-additive parts are morphogrammatically realized by ‘transjunctional’ morphograms. Super-additivity of composed morphoCAs is a measure of the degree of interactivity between the CA parts of a complex morphoCA.

Decomposition2_179.gif Decomposition2_180.gif Decomposition2_181.gif Decomposition2_182.gif
Decomposition2_183.gif Decomposition2_184.gif - -
Decomposition2_185.gif Decomposition2_186.gif Decomposition2_187.gif -
Decomposition2_188.gif Decomposition2_189.gif - Decomposition2_190.gif



Some variations of the super-additive part



















CA of Part - 1



Reduction of Decomposition2_212.gif with state 2 reduced to state 1, Decomposition2_213.gif













ruleM[{6, 3, 9, 11, 15}], dynamic






ruleM[{6, 3, 9, 11, 15}], dynamic





Decomposition within the positionality frame of morphograms

Reduction and decomposition of CA constructs are of equal importance.

Reductions are mainly based on an application of the Stirling numbers of the second kind instead of the application of the Klenee product  (star) on an alphebet of atomic signs.


A functional approach demands a combinatorics of Decomposition2_235.gif value distributions. Hence, a system with 3 variables and 3 values includes Decomposition2_236.gif= 27 value constellations between {1,1,1} and {3,3,3}. But this approach gets into conflicts with the principle of positionality that demands a distribution of morphic and functional parts.

With the positional approach, just 21 ternary value constellations are necessary. According to the mediation principle they coincide with the constellations {1,1,1} ∈ S1 and S2, {2,2,2} ∈ S1 and S2 and  {3,3,3} ∈ S2 and S3.

But with a strict disjunctivity of the core values of S1, S2 and S3, just 21, instead of 27 value constellations are realized.

This approach works fine for junctional and transunctional funtions and morphograms. Transjunctional constellations are defined as interactional core values and are not in conflict with the mediating values of the frame.

The set of 21 possibilities of value constellations is in itself not involved with transjunctional or interactional features. But the functions on the base of this set constellations is not restricted to ‘junctional’ functions only. The whole set of possible of trnasjunctional constellations is avaible too.

Framework for decomposed ternay functions

“Time direction is a significant property to distinguish a Cellular Automata logic function from a traditional logic function.” (Zheng)

A composition of 3 two-valued functions Decomposition2_237.gif, Decomposition2_238.gifand Decomposition2_239.gifrepresenting the states Decomposition2_240.gifat a time t, consists of a mediation of the value-sets of the two-valued functions and the mediation of the disjunct time function of each function Decomposition2_241.gif.

The elementary cellular automaton function is defined by:  (Decomposition2_242.gif(t), Decomposition2_243.gif(t), Decomposition2_244.gif(t)) ⇒ Decomposition2_245.gif(t+1).

“A cellular automaton is a model consisting of a discrete number of states in a regular grid. Time is also discrete, and the state of a cell at time t is a function of the states of its neighbors at time t - 1.”


A polycontextural approach to computation has not to be restricted by a homogeneous linear discrete structure of time.

Skizze einer graphematischen Systemtheorie
“Damit ist die Grundlage für eine irreduzible POLY–PROZESSUALIT…T angeben. Die komplexen Phänomene der Mehrzeitigkeit, der Gegenzeitigkeit und der Polyrhythmie wie auch die Dynamisierung von Entscheidbarkeit und Unentscheidbarkeit in formalen Systemen lassen sich hierdurch explizieren. Die allgemeine Konzeption der Prozessualität in komplexen bzw. heterarchischen Systemen transformiert grundlegend Apparat und Konzeption der Operativität und der Entscheidung.” (1985) Prozessualit%E4tkomplexerSysteme

Nevertheless it is not the place to go into such intriguing philosophical and time-theoretical considerations. It is enough to see that the classical approach is based on a maximal reduction of complexity to be able to function. The time of this decison is over.

Back to normal:

The global time of a 3-contextural CA is composed by 3 time-structures of each contexture, hence the 3 involved CAs get each its own time-structure. In general, for n contextural CAs exactly Decomposition2_247.gif time-structures are involved in the complexion of Decomposition2_248.gif.

With that features, poly-rhythms, antidromic and complex events in different time domains are formally accessible.

Decomposition2_249.gif =  (Decomposition2_250.gifDecomposition2_251.gifDecomposition2_252.gif.


Framework for equality based mediation of functions



Decomposition2_256.gif = {1,2,3} ∐ {1,2,3} ∐ {1,2,3}



Decomposition2_258.gif Decomposition2_259.gif Decomposition2_260.gif Decomposition2_261.gif
Decomposition2_262.gif Decomposition2_263.gif - -
Decomposition2_264.gif - Decomposition2_265.gif -
Decomposition2_266.gif - - Decomposition2_267.gif
Decomposition2_268.gif Decomposition2_269.gif Decomposition2_270.gif Decomposition2_271.gif
Decomposition2_272.gif Decomposition2_273.gif - -
Decomposition2_274.gif - Decomposition2_275.gif -
Decomposition2_276.gif - - Decomposition2_277.gif

Different presentation



Decomposition2_279.gif Decomposition2_280.gif Decomposition2_281.gif Decomposition2_282.gif
Decomposition2_283.gif Decomposition2_284.gif - -
Decomposition2_285.gif Decomposition2_286.gif Decomposition2_287.gif -
Decomposition2_288.gif Decomposition2_289.gif - Decomposition2_290.gif
Decomposition2_291.gif Decomposition2_292.gif Decomposition2_293.gif Decomposition2_294.gif
Decomposition2_295.gif Decomposition2_296.gif - -
Decomposition2_297.gif Decomposition2_298.gif Decomposition2_299.gif -
Decomposition2_300.gif Decomposition2_301.gif - Decomposition2_302.gif


Some bifunctorial frameworks for a general mediation of CAs

Compositional mediation

The examples in this paper are mainly based on a mediation in the mode of equality (identity). This is just a convenient way to introduce the conceptas such.

The modi of mediation to be studied are:

mediation in the mode of equality,
mediation in the mode of equivalence,
mediation in the mode of similarity,
mediation in the mode of bisimilarity,
mediation in the mode of metamorphosis.

Types of compositions


Some summary








Transjunctional mediation


Decomposition2_313.gif Decomposition2_314.gif Decomposition2_315.gif Decomposition2_316.gif
Decomposition2_317.gif Decomposition2_318.gif - -
Decomposition2_319.gif Decomposition2_320.gif Decomposition2_321.gif -
Decomposition2_322.gif Decomposition2_323.gif - Decomposition2_324.gif
Decomposition2_325.gif Decomposition2_326.gif Decomposition2_327.gif Decomposition2_328.gif
Decomposition2_329.gif Decomposition2_330.gif - -
Decomposition2_331.gif Decomposition2_332.gif Decomposition2_333.gif -
Decomposition2_334.gif Decomposition2_335.gif - Decomposition2_336.gif

Reflectional mediation


Decomposition2_338.gif Decomposition2_339.gif Decomposition2_340.gif Decomposition2_341.gif
Decomposition2_342.gif Decomposition2_343.gif Decomposition2_344.gif Decomposition2_345.gif
Decomposition2_346.gif Decomposition2_347.gif -
Decomposition2_348.gif - Decomposition2_349.gif
Decomposition2_350.gif Decomposition2_351.gif Decomposition2_352.gif Decomposition2_353.gif
Decomposition2_354.gif Decomposition2_355.gif Decomposition2_356.gif Decomposition2_357.gif
Decomposition2_358.gif - Decomposition2_359.gif -
Decomposition2_360.gif - - Decomposition2_361.gif
Spikey Created with Wolfram Mathematica 9.0