Sketch of Memristic Cellular Automata

A concept of time-oriented morphic cellular automata

Rudolf Kaehr Dr.phil@

Copyright ThinkArt Lab ISSN 2041-4358



The concept of morphic cellular automata with time-orientation is proposed as a further explication of memristive interactions.

             ===SHORT VERSION ==

1.  Metaphor towards memristive CAs

1.1.  Motivation

Conflict-free endomorphisms
A mapping of elements on a grid of cells is well established if the mapping is restricted to some obvious rules. There should be only one element per cell. And the cells are well defined as identical places in a topologogy of a grid. Also the mapping should be restricted to one cell only, and not involving neighbor cells of the target constellation too. Each neighbor cell of a cell becomes in a next pplication a cell and therefore gets its occupation by one element. Such a mapping of all cells by elements is called a configuration. Configurations appears in time-steps. For each time-step there is a single configuration of cells and their elements. Time-steps are evolving along a numeric time line. Configurations of time-steps are disjunct.

This concept is well realized by 1-dimensional cellular automata, i.e. 1 D CAs.

This is a perfect working concept and nothing has to be changed or added.

The desire of normal CAs is to produce complexity on the base of simplicity is realized in the framework of elementaristic order and a presumed homogeneous concept of a universe in which such complexity happens.

The mechanism of transition from time t=0 to t=1 is depicted classically with the following diagram:

[Graphics:HTMLFiles/Sketch of Memristic Cellular Automata_1.gif]

Conflict with polysemy
Nevertheless, it might turn out to be quite annoying. And it could be of more fun to introduce a different concept.
Say, why should the transition function based on the local rules deliver one and only one result to the configuration?
What happens if we allow, say 2 elements?

Obviously they will produce a conflictive situation. There is no place for 2 elements per local rule and single cell because all neighbors of the cell are treated equally the same, they get occupied by one and only one element.

A compromise could resolve the conflict: only the identical elements are allowed to be re-occupied by an element. Hence a kind of an invisible overlapping could do the job. But this would not only restrict the mappings to the very same elements and produce the very same configuration, it is also quite superfluous.

Hence, there is still the desire to map different elements onto the same cell.

Fusion, glue and blend
[Graphics:HTMLFiles/Sketch of Memristic Cellular Automata_2.gif]

The basic obstacle towards a construction of visibly overlapping mappings are not the cells, neither the mapping procedure but the concept of identity of the involved elements (states, symbols).
Hence, we have to get rid of this inherited obstacle. But to get rid of the identity of the elements, symbols or states, mappings and systems would necessarily destroy the whole approach of cellular automata as such, and everything else too.

A simple diagram may depicture the difference between overlapping monomorphies and non-overlapping blocked elements.

The block diagram shows how blocks are treated by the transition function f. Blocking is reorganizing the blocks of elements without getting in trouble by any overlapping of elements at all.

Block rules without conflicts
[Graphics:HTMLFiles/Sketch of Memristic Cellular Automata_3.gif]   
Jörg R. Weimar

1.2.  Explication of memristive rules

1.2.1.  Mechanism of morphic elementary CA rules

The diagram for the morphic rules for dyads, i.e. 2-element monomorphies, shows how the transition mapping for monomorphies is producing an overlapping at the target configuration. Focused on the elements of the monomorphies there is a conflicting situation between the monomorphy of the mapping, [ab] and the monomorphy of the target constellation, [ba]. Because monomorphies are defined as patterns (morphograms) and not by their elements as such, a fusion between mapping and target monomorphy is applied which resolving the conflict without changing the structure of the pattern. Hence, the applied monomorphy of the rule, [aba] --> [ab], is properly mapped onto the target constellation, [ab], without changing its monomorphic definition as a dyad. Hence, [b] --> [ab] ≡typeset structure[ba] --> [bab].
Morphic rules are offering a right- and a left-oriented mapping of monomorphies onto the target constellations.

<br />              Morphic rule [ ... ;                

<br />            Symbolic rule (abb) ->  ... ;                

Now, we want to keep the mechanism of CAs. But not the conflict producing elements (data structure, states, symbols).
A good compromise could be to accept not the signs of a CA alphabet but the patterns of sign-configurations only. Hence, the objects of such an alphabet-less machine would be patterns abstracted from sign-configurations and the rules of the CA mechanism would be defined by patterns only.

This approach seems to offer a good chance to overlap other patterns without getting into conflict with the elements of the representation of the pattern. Again, the elements don’t count. What is in the game are the patterns, called morphograms. Nevertheless, to write and realize patterns we have to use signs for elements as forms of presentation of morphograms.

This concept of togetherness of elements demands to abandon the identity of signs in favor of morphograms.

Having introduced morphograms, morphic local rules are easily defined and overlapping configurations are becoming natural situations of morphic CA transitions.

As one of many consequences, our morphicCA gets some temporal orientation not only by the way an application of the morphic local rules happens but much more directly as a consequence of the asymmetric structure of the configurations of the local rules  themselves.

Kenomic CAs
Morphic rules are build on the base of monomorphies of morphograms. Monomorphies are parts of morphograms as sings are elements of sign sequences. Monomorphies are build up and realized realized by kenograms. Kenograms are elementary parts of a morphic patterns. This motivates the definition of kenomic CAs. KenoCAs are realized by kenomic endomorphisms, and are therefore still keeping the properties of non-overlaping in CAs alive.

Normal CAs
Despite the dynamical character of the behavior of classical CAs they nevertheless might be considered as “frozen” kenomic CAs  involving a reduction of the rule set and the mechanisms of building complexions of composed kenomic CAs.

What could be the purpose of the construction of time-oriented morphic CAs?

According to the studies into the memristivity of memristor-based crossbar systems, time- and history-dependence and the overlapping, fusion or blending, i.e. chiastic interplay of computation and memory functions are crucial for a new paradigm of nanotechnological computing.

Morphograms, invented 1962 by the cybernetician and philosopher Gotthard Gunther, and the theory of the interactivity of morphograms, morphogrammatics, are still a quite intriguing project to realize.
Morphic CAs are implementing time-dependence by their elementary rules directly into the automatism even before any information processing has to be involved.

To opt for a ‘machine'-interpretation of morphograms might be even more surprising. In fact, morphograms had always been reflected in the context of operational, machine- and program-related constructions. But a direct application of morphogrammatics in the very context of cellular automata constructions is indeed a brand new adventure.

1.2.2.  Procedure of morphic elementary CA rules

 Morphic NextGen procedure     <br /> <br />      &nbs ... [ba]^[bc] = [abc]    <br />           

The NextGen rule, or procedure, is not simply realized with an application of a local rule, the result of such an application has to be embedded and aligned with the states of the cells of the target configuration. Because of the non-atomic but morphic structure of the result there is a space conflict for the integration of the morphic result. Hence, a fusion of the rule result and the neighbor state of the configuration has to be established. This is naturally realized with the fusion-rules of monomorphies of morphogrammatics.

1.3.  Neighborhood rules for morphic CAs

1.3.1.  Mechanism of morphic CA rules

As a first step to the realization of monomorphic transitions a new neigborhood relationship has to be introduced.
Not only the transition rules, discrete or monomorphic, are defined with neighbors but the placement of their results has to be kenomically adjusted to the results in the grid of constellations of the application of previous rules.

Hence, at first their are two kinds of neighborhood relations to distinguish: the neighborhood cells of the primary generic rules and the neighborhood relations of the results of the rules for a new result of a configuration.

This is achieved with the rule scheme for monomorphic successors (NextGen, results) with at least dyadic successors (monomorphies) in contrast to the singular atomic successors of classical m-neighborhood rules and the monadic successors for kenomic CA rules.
The main rule is still composed by the set of local rules fulfilling the combinatorics with length 4 for 2 elements and 5 for 3 elements. Hence, the combination of rules for 1D kenoCA shall be applied for 1D morphCA.

Discrete : c312 - c4 => Overlapping : c312 - c45         ...                                                       -                    c4    c5   -

<br /> R1 •             •             •           R7 •              ...                                        r4            r7                                         MG

Coincidence and kenomic adjustment [O         •   O      ] = [aba] 1 ; 4, 5, 6 ; r8 : (a ... /> <br /> 2 ; 6, 7, 8 : r7 : (bb) ; (bba) --> (ab) : (bb)^(ab) = (bbba) => (bba) : 6, 7, 8.

O         • =   _ MG •   O       <br /> • => •   •^O         • = •    •   O

centre = [a]                         Overscript[-->,    transition   ]  ...                       constellation : [ba]  left       = [a] Correct notation

typeset structure

typeset structure

typeset structure
typeset structure

2; 4, 5, 6: R12: [aba] - [cb]
2; 5,6,7: R13: [abb] - [ca]      : [cb]^[ca] = [cba]; [ab]^[bc] = [abc]
2; 6,7,8: R1: [aaa] - [ab]: [cba]^[ab] = [cbab]
2;7,8,9: R1: [aaa] -[ab]: [cbab]^[ab] = [cbaba]
2;8,9,10: R12: [aba]-[cb]: [cbab]^[cb] = [cbabc]

typeset structure

typeset structure

typeset structure

The new value is determined by the applied local rule and the existing value of the constellation in the grid: if the left-value y and the new value x at y is different then value x changes to y, and z is building with y the new monomorphy.

The center-application is left- and/or right-oriented.

1.3.2.  Left-right-asymmetry  of the applications of local rules

The classical simultaneity of the application of rules, which is a 1-1-mapping has to be modified because of the asymmetry of the beginnings, center-, right- and left-applications.

For classical CAs we obviously have a non-oriented structure: “Notice that the order in which we calculated  the rows of squares did not matter, we could have done them right-to-left, or in an arbitrary order, instead of left-to-right.” (F.L. Thaulaw, 2010)

Hence, the beginning of the application and its direction is a determining property of the automaton. This formal property might be instrumentalized to introduce a kind of an observer-dependence of the construction. The understanding of the developed configurations are depending on the direction of its construction and re-construction, i.e. interpretation. Time- and history-dependence might be a reason too. Kenomic and symbolic CA rules are producing disjunct results. Morphic CAs are producing overlapping results.

Therefore symbolic and kenomic CAs are non-directed, while morphic CAs are time-oriented measured by the overlapping function. There is a difference in approaches which are introducing, say time-dependence secondary with the help of arbitrary techniques and an approach which is implementing time-dependence at the very beginning of the construction.

typeset structure

The results for left-, right- and centre-directions of the application of the sub-rules of the general rule are different.
Therefore, the axiom of simultaneity for classical CA has to be deconstructed towards an asymmetric double strategy.

Because there is a bijection between the chain of rule names and the new configuration, the chain of rule names gives the answer of the internal structure of the new configuration, i.e. the combination of rule application and fusion. The chain of local rules defines the global rule of the application. Hence the intricate combinations and fusions of the new configuration are reflected by the rule chain and can therefore be reconstructed from the global constellation with the application of the chain of the local rules.

The right configuration (2; 1-9) is characterized by the rule chain (typeset structure).
The left configuration (3; 9-1) is characterized by the rule chain (8, 8, 4, 1, 7, 8, 8, 4: right to left of 1; 1-9).

The classical arrangement for CAs “There's one cell at each node of the lattice.” (Thaulaw) holds in some sense for morphCAs too. But because of the overlapping of the morphograms the states might also be considered as double defined and derived from different rules albeit resulting in coincidence. Thus, the states in morphCAs are functionally doubled, polysemical and ambiguous but as results they might be considered by an external interpretation as mono-semical.

RuleChaintypeset structure([typeset structure]) = [typeset structure]

RuleChaintypeset structure([typeset structure]) = [typeset structure] .

<br />    <br />     1 - D morphCA <br /> <br />     R ... _ left ([c]) => e  _ left ( [ c ] )   != e  _ right ([c])    <br />

Classical CA
For classical 1 D CAs(0,1) the rule application is neutral to the distinction of right- and left-orientation. This corresponds with the principle of simulataneity of the rule application for CAs.

 <br />    1 - D CA <br /> <br />    RuleChain  _ left (c) ≡ RuleChain  _ right (c) = e (c)    <br /> <br />

1.3.3.  Left-right-asymmetry of local rules

Orientation implemented by the asymmetry of local rules
A further concretization of the implementation of orientedness might be achieved with the introduction of the difference of right- and left-oriented local cellular automata rules. Instead of the restricted orientation achieved by different applicative orientations of the local rules, the new approach is based on the structural asymmetry of the local rules which are defining directly a left- or right-orientation for their application.

The two schemes:
right: (c3,c1,c2) --> (c4,c5) and  left local rules: (c3,c1,c2) --> (c4,c6)
are inviting to study a new class of elementary cellular automata.
Those automata are time-oriented by the definition of their asymmetric rules, and not just by the external application of symmetric elementary local rules.

right local rules: (c3,c1,c2) --> [c4c5]:

typeset structure

left local rules: (c3,c1,c2) --> [c4c6]:

typeset structure

morpho-neutral local rules (c3,c1,c2) --> [c6c4c5]:

typeset structure


typeset structure

typeset structure

typeset structure

typeset structure

keno-neutral local rules (c3,c1,c2) --> [c4]:

typeset structure

typeset structure

   <br />    1 - D morphCA <br /> <br />     [c  _  ... ( [ c  _ 1 )]   != e  _ right ([c  _ 2])     <br />  <br />

2.  Formalism of CA

2.1.  Formal definition of CA after Kari

Cellular Automaton CA CA = finite items {d = dimension, S = state set, N = neighborhood, f = l ... lls at locations Overscript[x, ->] + Overscript[x, ->]  _ i, for i = 1, 2, ..., n .

<br /> The cells change their states synchronously at discrete time steps . <br /> The next st ... p;   :       Moore neighborhood . <br /> (Kari, IntroCA, p .42)

Kari gives a very useful intro to CAs. The full mathematical theory is to collect at the same address.

2.2.  Preliminary formal definitions for morphic CAs

2.2.1.  Sketch of basic definitions for morphCA

Some preliminary formalizations are sketched to precise the approach to morphic CAs with time  ... #969; = orientation of the local application f ϕ = fusion of local and global constellations

N : neighborhood Overscript[x, ->] ∈ N : right neighborhood Overscript[x, <-] W ... c : N -> { 0} morph  _ left : N -> (-1, 0) morph  _ right : N -> ( 0, 1)

<br /> c : configuration <br /> c  _ right (Overscript[x, ->] + Overscript[x, -> ... ;-]  _ 2), . . . , c (Overscript[x, <-] + Overscript[x, <-]  _ n))) . <br />

S :   finite   set   of   states (monomorphies) <br /> Overscript[x, ->] ∈  &nbs ... ; Stirling2 (Z, d) , class of trito - normal forms c (Overscript[x, ->]) : current tnf - state

<br /> f   : local   rule   (local transition map δ) <br /> f  _ morph : (a ó ... f  _ tnf : Sn2 (S, n  ) --> Sn2(S, l), n = neighborhood, l = length of result .

<br /> ϕ : fusion <br /> ϕ (c (Overscript[x, ->] + ( Overscript[x, ->]  ... #981;  ( x  _ (i  _ 2), x  _ (j  _ 2), -->])) ) •

ω : orientation The application of the fusion operation of the local rules are oriented b ...                        centre : left/right          

<br />     morphCA : <br />     G  _ morph : (Sn2 (S, Z, ... (S, Z, d ))    --> Sn2 (S, Z, d )  _ /fusion     <br /> <br />

Example for fusion <br /> f : ϕ : ( c (( Overscript[a  _ i  _  _  ... [ab], ϕ[ab])) = c (ϕ ([ab], [ba]) ) = c ([aba]) <br /> new current state : [aba] •

<br /> A global mapping on configurations is obtained by    uniform and synchr ... ; _ (  _ (Overscript[z, ->] + Overscript[ n  _ n, ->])) )    

2.2.2.  Classification of 1D morphic CA rule types

"The local dynamics, represented by the transition function of a cell, denoted by typeset structure, is a function which receives as inputs the state of a cell and its ‘neighbors’, and computes by the local rules the next state of the cell.” (Varum Bhatia)

Hence, the local dynamics of a 1-D CA, semiotic, indicational, kenomic and morphic can be defined by the following equations.
Depending on the kind of CA, the types of local rules are differenciated into 3 classes: the classical type of 1 D CAs, the kenomic rule type and the morphic rule types with left - and right-oriented rule types with tupels and one left-right-oriented rule type with a tripel generation.

   <br />    Classification   of local   dynamics <br />    <br  ...                                                         i1           i2           i3          c645

2.2.3.  Mediative compositions of CAs

Special   distinctions of 1 - D CA for    mediation of different 1 - D CAs : <br />  ... <br />                

Mediation   μ μ : (CA ^1, CA ^2)    --> (CA ^1  ...  _ 2 . <br /> <br /> Bifunctoriality of    μ (CA _ i^(3), o , ∐), i = 1, 2 :

     Bifunctoriality of compositions of mediated CAs <br /> <br />  & ...                                                                                                  2

2.3.   System of 2-morphic right CA rules

typeset structure
typeset structure   
typeset structure

typeset structure