Rudolf Kaehr Dr.phil^{@}

Copyright ThinkArt Lab ISSN 2041-4358

Abstract

The idea of a memrsitive STACK machine based on the retrograde recursivity of its data structure and on the construct of enaction for its operators shall be sketched in a descriptive and semi-formal manner.

Up to now, it seems, that there are five different approaches available to deal formally with aspects memristivity in a formal and operative manner.

The focus of this exercise shall be oriented on enactional approach with some kenogrammatic features only. *Enaction*, additionally to the *retrogradeness* of kenomic recursivity, is an interesting new property of memristive formalisms to be studied.

Because the discovery of memristivity in nano-electronics by Leon Chua 1971 and its realization by the team of Stanley Williams at HP in 2008 is very recent and not yet studied formally from a non-electronic and system-theoretic point of view, this study remains still in a very experimental and temporary status of reflection and elaboration.

The graphematic possibilities of studying memristivity in formal systems at hand for now are:

1. the mode of *semiotic* identity with recursivity,

2. the mode of *contextural* comlexity with proemiality,

3. the mode of *kenogrammatic* similarity with retrogradeness,

4. the *indicational* mode of “topology-free constellations of signs” with enaction, and

5. the mode of *monomorphic* bisimilarity of morphogrammatics with bisimulation.

Other modes are possible as further realizations of graphematic styles of inscriptions.

Every symbolization system entails its own paradigm of programming languages.

**Properties****Semiotics** a=a, a!=b, a(bc) = (ab)c

The semiotic or *symbolic* mode of thematization is ideal for atomistic binary physical systems as they occur as digital computers. **Polycontexturality (**ab) = ((ab)c), (ac)(bd) = (ab)(cd)

The *contextural* or interactional mode of thematization is ideal for ambigous complex physical systems as they occurs in distributed and interacting digital computer systems.**Kenogrammatics** a=b, (aa) != (ab), (ab) = (ab)|(ac)

The *kenogrammatical* mode of thematization is ideal for pre-semiotic complex behavioural systems as it occurs in memristive physical systems.**Calculus of Indication ** a=a, a!=b, ab = ba

The *indicational* mode of thematization is ideal for singular decision systems as they occur in simple action systems.**Morphogrammatics** a=b, (aa) != (aaa), (aba) = (abba)

The *monomorphic* mode of thematization is ideal for metamorphic systems as they occur in complex memristive actional systems.

Some properties might be collected temporarily in the table:

Recursive functions are memory intensive. It might be possible to re-design the mechanisms of recursivity in comutational systems with the help of a memristive thematization of the very basic properties of recursivity.

**Further characterizations**

In analogy to the operation LIST on objects:

LIST: a, b, c --> (abc)

LIST: (ab), a, b, c --> ((ab)abc))

we shall define a general thematization function or operation THEMATH which is interpreting a proposed ”set” or “agglomeration” of objects as *semiotical*, *contextural*, *kenogrammatical*, *indicational* or *monomorphical*:

Following Wolfram’s statement, according to M. Schreiber:

"A kind of form is all you need to compute. A system can emulate rule 110 if it can distinguish: *More than one is one but one inside one is none.* *Simple distinctions can be configured into forms which are able to perform universal computations.” *

Applied to one of the simplest models of computing, the STACK, we get a distinctional stack model. This observation corresponds properly with Wolfram/Schreiber’s statement.

What is still missing are the *memristive* properties. Memristivity enters the game with an *enactional* interpretation of the operation “Pop”. But this makes sense only in the framework of a disseminated, i.e. polycontextural stack model

Applied to the simplest model of computing, the STACK, we get a distinctional stack model.

What is still missing are the memristive properties.

Memristivity enters the game with an enactional interpretation of the operation “*pop*”.

But this makes sense only in the framework of a disseminated, i.e. polycontextural stack model.

‘Keller’ machines which are remembering their ‘kellert’ (cancelled) states. Or: Register machines which are registering their cancelled states.

**Connection with the Calculus of Indication (CI):**

With *pop* a memristic function shall be implemented with the application of the enaction operator:

pop ( a -- ø ) => pop( a_{1.1} --> ).

This *pop* operation is emptying the stack “q_{1.1}” from its symbol “a_{1.1}” and is pushing, at the same time, the symbol a_{1.1} onto another reflectional stack “q_{1.2}” as the symbol “a_{1.2}”.

Hence, enaction is a composition of an *elimination* step (popping, emptying, reading) and a transitional step of *pushing* (writing) the data onto another neighboring stack system.

With “” for “{ }" we get:

pop ( -- ø) = ( --> ø),

( -- ø) --> ( ) .

**Retrogradeness of “push"**

The case of a Morphic STACK with a retrograde definition of the push operation is not considered at this place. Retrogradeness is involved with additional operations, say ADD, but not yet for “push”. A system with enactional “pop” and retrograde “push” is defined for the mix of indicational and kenomic formalisms. The operation “push” belongs to the repeatability of events and is therefore involved with retrograde recursivity. Hence the concatenational “push” with “push (a - aa)" becomes “push: X = (a) --> Xa | Xb".

**Why stack machines?**

What happens with a tabular organization of a stack? The tabular matrix is supporting the distribution of contextural and morphogrammatic-based distributions of stack machines.*"In computer science, a stack machine is a model of computation in which the computer's memory takes the form of one or more stacks.” *(WiKi)

A similar exercise with LISP will be published soon.

**STACK as a category:**

Following Axel Poigné (LNCS 240, 1985, p. 107):

"Let T be the category of terms T_{STACK} generated by the signature

For **example**, the basic Forth stack operators are described as:

( before -- after )

dup ( a -- a a )

drop ( a -- )

swap ( a b -- b a )

over ( a b -- a b a )

rot ( a b c -- b c a )

The main operations of a stack machine are PUSH and POP, also called DUP and DROP for FORTH.

"The two operations applicable to all stacks are:

• a *push* operation, in which a data item is placed at the location pointed to by the stack pointer, and the address in the stack pointer is adjusted by the size of the data item;

• a *pop* or pull operation: a data item at the current location pointed to by the stack pointer is removed, and the stack pointer is adjusted by the size of the data item.”

http://www.ece.cmu.edu/~koopman/stack_computers/sec3_2.html

http://www.dcs.gla.ac.uk/~marks/thesis.pdf

**Morphogrammatic interpretation**

DATA/RETURN STACK:

The data of a memristive stack machines are in fact morphograms. A distinction-theoretic option with an application of the Calculus of Indication is preferable for reaons of introduction.

ALU: Morhogrammatics

The arithmetical and logical operations for a memristive stack are defined accoring the struture of memristive objects. Hence, retrograde recursivenes and enaction of morphograms has to become the guiding paradigm for a memristive stack machine.

CONTROL LOGIC: Polycontexturality

The control logic for polycontextural memristive stack machines is ruled, certainly, by a polycontextural logic which is surpassing the limits of non-distributed classical logics. Hence, any contextural place of a memrsitive stack gets its own logic, and arithmetics too.

Hence, because of its polycontextural definition, a memrsitive stack machine is not simply a kind of a multi-stack machine but a system of mediation of stack machines.

**Instructions**

Some typical stack *instructions* for the classical case of a stack machine (and Forth).**Instruction Data Stack Function**

**input -> output**

! N1 ADDR -> *Store* N1 at location ADDR in program memory

+ N1 N2 -> N3 *Add* N1 and N2, giving sum N3

- N1 N2 -> N3 *Subtract* N2 from N1, giving difference N3

>R N1 -> *Push* N1 onto the return stack

@ ADDR -> N1 *Fetch* the value at location ADDR in program memory, returning N1

AND N1 N2 -> N3 *Perform* a bitwise AND on N1 and N2, giving result N3

DROP N1 -> *Drop* N1 from the stack

DUP N1 -> N1 N1 *Duplicate* N1, returning a second copy of it on the stack

**Example****Input Operation Stack**

- stack ⊥

1 Push operand 1

2 Push operand 2, 1

4 Push operand 4, 2, 1

* Multiply 8, 1

+ Add 9

3 Push operand 3, 9

3 Pop operand 9

9 Pop operand ⊥ .

**Preconditions**

Retrograde recursivity of kenogrammatics and its laws of sameness of morphograms.

Enactional meristivity of reflectional and interactional operations in polycontextural configurations.**Strategy** for the design of a memristive stack concept:

POP: enactional memristics, i.e. the operation POP is at once destructive and conservative.

PUSH: concatenation memristics (retrograde recursivity), i.e. the concatenational aspect of PUSH is reflecting its morphogrammatic design which is not atomistic but holistic.

**Symmetry/asymmetry of pop and push**

In contrast to the destructive definition of POP for the classical STACK, we add a memristive definition for POP, which is cancelling the addressed state at his address but is simultaneously storing the value of the state at its enactional domain.

Hence, the memristive stack concept is *destructive* in its monocontextural function and at once *memristive* in its polycontextural behavior.

storing :: "to place or leave in a location (as a warehouse, library, or computer memory) for preservation or later use or disposal.” (Webster)

If a parcel drops out from a staple, its vanishing gets registered by the memory of that annihilation. Annihilation gets registered.*"After execution, the parameters have been erased and replaced with any return values.”*

**Memristive PUSH**

The classical definition of PUSH is atomistic, linear and abstract. In contrast, the memristive PUSH has to reflect the retrogradeness of any iterability, here, the character of the iteration of the morphogrammatic PUSH operation of the STACK.

**Input Operation Stack STACK**

a_{1.1} Push operand a PUSH(a_{1.1}) --> a_{1.1}

a_{1.1} Pop operand [⊥_{1.1}, a_{1.2}] POP( ) --> [⊥_{1.1}, a_{1.2}]

A classical STACK maschine is neutral to its data, i.e. any data accepted might be dublicated, i.e. droped. This is expressed with 2 sorts of terms for the category of a STACK: *nat* and *stack.*

How are memristive STACK machines defined in respect to PUSH?

Also the data type (nat, indicational,kenomic, morphogrammatic) are not crucial to demonstrate the mechanism of the enactional stack, it might be interesting as a next step towards a enactional stack machine to know how the operation ADD is working in the different settings.

**Sign repertoire**

sign = { ”;” , "|", ”, “, "(", ")"},

operators ={ Pop, Add, Push},

terms ={ t, }

Superoperator had been introduced to deal with polycontextural formalisms for logics and programming languages.

In this light, enaction is connected with the superoperation of *replication *and *bifurcation*. Reflectional enaction is replication with cancelling and interactional enaction is bifurcation with cancelling. **Superoperators ****sops: **{** **ID, PERM, RED, REPL, BIF}

**STACK Identity**

ID(a_{1.1}) --> (a_{1.1})**STACK Replication**

Rep(a_{1.1};⊥_{1.2}) --> ( a_{1.1}; a_{1.2})**Reflectional enaction**

Rep_{EN}(a_{1.1}) --> (⊥_{1.1}; a_{1.2})**STACK Permutation**

Perm(a_{1.1}; a_{2.2}) --> ( a_{2.2}; a_{1.1})**STACK Reduction**

Red_{1.1}(a) --> ( a_{1.1}; a_{1.1})**STACK Bifurcation**

Bif(a_{1.1}; ⊥_{2.1}; ⊥_{3.1}) --> ( a_{1.1}; a_{2.1}; a_{3.1})**Interactional enaction**

Bif_{EN}(a_{1.1}; ⊥_{2.1}; ⊥_{3.1}) --> ( ⊥_{1.1}; a_{2.1}; a_{3.1})

Operators with memristive properties are: enaction and retrograde recursivity. This paper is focused on the memristivity of enaction. Other aspects are studied elsewhere.

*"Memristance is a property of an electronic component. If charge flows in one direction through a circuit, the resistance of that component of the circuit will increase and if charge flows in the opposite direction in the circuit, the resistance will decrease. If the flow of charge is stopped by turning off the applied voltage, the component will ‘remember’ the last resistance that it had, and when the flow of charge starts again the resistance of the circutwill be what it was last active.”"In other words, a memristor is ‘a device which *bookkeeps

A new operator, inverse to DROP shall be GET. This operator is defined to restore the cancelled state out of the cancellation by a reverse reconstruction of the result of enaction.

DROP or Push, in its memristive definition, is representing the action of ‘stopping’ the flow and keeping the state in a different mode, while GET is “remembering’ the last resistance” by getting the restored state from POP back into its domain. This is not any kind of *creatio ex nihilo, *or a crude double bookkeeping, but an interplay on different levels of realization of states; states as produced and states as remembered.

Both together, DROP and GET, are managing the “bookkeeping” of the memristive device.

Cancelling, while keeping (with POP), and keeping, while cancelling (with GET). There is obviously a nice chiasm in the game.**Interplay of erasing and restoring**

One amazing property of memristive enaction is its 'stability' or 'pemanence’, i.e. its *persistence* .

**Persistence**:

To all enactional cancellation of a complexion there always remains at least one last enacted state. There might be an interpretation of the abstract *persistence* and the *endurance* of a state in a physical memristive system.

To understand the new concept of a memristive stack we have to consider its polycontexturality and, at least, is properties of reflectional and interactional operations.

These two features are enabling the stack-theoretic distinction of reflectional and interactional enaction for stack operations. Especially the POP-operation has 3 stack-specific modi of action:

1) classical *cancelling* (annihilation) of a state,

2) *reflectional* and

3) *interactional* enaction.

Enaction is the double operation of cancelling (eliminating) and storing the eliminated state *as* a memorized state, or as a recorded/archived state in another domain.

These enactional operations are enabling the stack to behave as a memristive system.

Enactional stacks are based on a special poly-stack construction, i.e. data type.

Hence, memristive stacks are defining memristive data structures or even data paradigms, which are demanding for corresponding programming paradigms, logics and arithmetics.

A tabular stack is the data structure for a memristive enactional stack machine.

Hence, the core model for memristive stacks is the well known “*kenomic matrix” *of polycontextural logic.

The basic structure of a enactional matrix is its bifunctorial interchangeability of its properties and features.

From a distinction-theoretical point of view, the single-distinction approach is not even half the option. Thematization, as an explication of “understanding and acting” gets a first formalization and operationalization with the paradigm of a quadralectic stack.