Compositions and Decompositions of morphoCAs

A collection of different provisional approaches to complexity reduction

Dr. phil Rudolf Kaehr

copyright © ThinkArt Lab Glasgow

ISSN 2041- 4358

( work in progress, vs. 0.1, Jan. 2015 )

Motivation

Reduction of the structural complexity of complex cellular automata.

Zheng

“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 configurations). It is impossible using today’s technology to process the n = 5 space due to the extreme growth of structural complexity x 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

http://www.tdx.cat/bitstream/handle/10803/9151/gpazienza_thesis.pdf

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.

Definition

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 ∈ is the neighborhood vector, and f : −→ 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.

https://www.ibisc.univ-evry.fr/~hutzler/Cours/IMBI_MPS/Kari05.pdf

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.

simple/complex,

partial/total,

distribution/mediation,

additivity/super-additivity,

composition/decomposition,

mono-/polycontextural,

contextures/morphograms.

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 MG, 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 is defined as a mediation of 3 basic morphograms: e.g.

= ( ) .

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

Additive compositions have the form:

, , ..., ], with for CAs.

While mediative compositions have the reflectional and interactional distribution form:

∐ ∐, ..., ∐ ].

Mediative de/composition examples for m=3:

⇒

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

rule110

additive composition of rule110

Additive compositions without super-additivity

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

ruleCl | 1 | 2 | 3 | 4 |

1 | [1] | □ | □ | □ |

2 | □ | [7] | □ | □ |

3 | □ | □ | [8] | □ |

4 | □ | □ | □ | [9] |

ruleCl | 1 | 2 | 3 | 4 |

1 | □ | □ | □ | |

2 | □ | □ | □ | |

3 | □ | □ | □ | |

4 | □ | □ | □ |

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 http://works.bepress.com/thinkartlab/17/

□ | S1.1=transjunction | S2.1 | S3.1 |

nil | nill | ||

□ | S3.2NIL | ||

□ | S3.2Nil |

Further example

Super-additivity of compositions

Excerpts from “Memristics : Dynamics of Crossbar Systems”

http : // www.thinkartlab.com/Memristics/Poly - Crossbars/Poly - Crossbars.pdf

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

mediation:

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 f and f, results in the super-additive compound

Matching conditions for equality based mediation

dom(f
dom(f
dom(f
cod() *≡* cod(f) *≡* cod(f) *≡** *cod(f)
cod() *≡* cod(f) *≡* cod(f)
cod() *≡* cod(f)
##

Interplay of polycontextural operators

Mediation of 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 ∈ ) is the neighborhood vector, and f : −→ S is the local update rule.”

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

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

Mediation of

Decomposition of

[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 : // memristors.memristics.com/Playing %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

Interpretation

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 and

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 , and partial functions as has to analyed more properly.

Concrete example

- | - | ||

- | |||

- |

http : // www.thinkartlab.com/Memristics/Poly - Crossbars/Poly - Crossbars.html

http://www.thinkartlab.com/pkl/lola/Abacus.pdf

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.

- | - | ||

- | |||

- |

Some variations of the super-additive part

Reductions

CA of Part - 1

Reduction of with state 2 reduced to state 1,

Decomposites

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 value distributions. Hence, a system with 3 variables and 3 values includes = 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)

http://cdn.intechweb.org/pdfs/15019.pdf

A composition of 3 two-valued functions , and representing the states at 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 .

The elementary cellular automaton function is defined by: ((t), (t), (t)) ⇒ (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)

http://www.thinkartlab.com/pkl/graphematik.htm#Zur Prozessualit%E4tkomplexerSysteme

http://www.vordenker.de/vgo/vgo_mehrzeitigkeit.pdf

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 time-structures are involved in the complexion of .

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

= (.

Framework for equality based mediation of functions

= {1,2,3} ∐ {1,2,3} ∐ {1,2,3}

Compositional

- | - | ||

- | - | ||

- | - |

- | - | ||

- | - | ||

- | - |

Different presentation

Interactional

- | - | ||

- | |||

- |

- | - | ||

- | |||

- |

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

http://memristors.memristics.com/MorphoProgramming/Morphogrammatic%20Programming.html

http://memristors.memristics.com/semi-Thue/Notes%20on%20semi-Thue%20systems.pdf

http://memristors.memristics.com/Polyverses/Polyverses.html

Transjunctional mediation

- | - | ||

- | |||

- |

- | - | ||

- | |||

- |

Reflectional mediation

- | |||

□ | - |

- | - | ||

- | - |