=Paper=
{{Paper
|id=Vol-2571/CSP2019_paper_8
|storemode=property
|title=Computing with Natural Numbers in Cause-Effect Structures
|pdfUrl=https://ceur-ws.org/Vol-2571/CSP2019_paper_8.pdf
|volume=Vol-2571
|authors=Ludwik Czaja
|dblpUrl=https://dblp.org/rec/conf/csp/Czaja19
}}
==Computing with Natural Numbers in Cause-Effect Structures==
https://ceur-ws.org/Vol-2571/CSP2019_paper_8.pdf
Computing with Natural Numbers in Cause-Effect
Structures
Ludwik Czaja
1
Vistula University, Warsaw
2
Institute of Informatics, The University of Warsaw
lczaja@mimuw.edu.pl
Abstract. Implementation of the standard model of natural numbers arithmetic
is constructed in terms of cause-effect (c-e) structures. The numbers are represented
by sets of (unstructured) tokens at nodes of the c-e structures, so the unary coding
of numbers is applied. Such modelling of arithmetic operations is possible due to the
inhibiting capability in the c-e structures. The exact cost of the typical operations
modelled by c-e structures constructed in this paper, is computed.
1. A summary of elementary cause-effect structures
A complete presentation of elementary and extended cause-effect (c-e) struc-
tures is in [Cza 2019]. Here, some notions needed for demonstration of their
capability of modelling computation with numbers are quoted.
Definition 1.1 (set F [X], quasi-semiring of formal polynomials)
Let X be a non-empty enumerable set. Their elements, called nodes, are
counterparts of places in Petri nets. θ ∈ / X is a symbol called neutral. It
plays role of neutral element for operations on terms, called formal polynomials
over X. The names of nodes, symbol θ, operators +, •, called addition and
multiplication, and parentheses are symbols out of which formal polynomials
are formed. A node’s name and θ is a formal polynomial; if K and L are
formal polynomials, then (K + L) and (K • L) are too. Their set is denoted by
F [X]. Assume stronger binding of • than +, which allows for dropping some
parentheses. Addition and multiplication of formal polynomials is defined as
follows: K ⊕ L = (K + L), K ⊙ L = (K • L). To simplify notation, let us use +
and • instead of ⊕ and ⊙. It is required that the system F [X], +, •, θ obeys
the following equality axioms for all K, L, M ∈ F [X], x ∈ X:
(+) θ+K =K +θ =K (•) θ•K =K •θ =K
(++) K +K =K (••) x•x=x
(+++) K + L = L + K (• • •) K • L = L • K
(++++) K + (L + M ) = (K + L) + M (• • ••) K • (L • M ) = (K • L) • M
(+•) If L = θ ⇔ M = θ then K • (L + M ) = K • L + K • M
Algebraic system which obeys these axioms will be referred to as a quasi-
semiring of formal polynomials.
Copyright Š 2019 for this paper by its author. Use permitted under Creative Com-
mons License Attribution 4.0 International (CC BY 4.0).
1
Definition 1.2 (cause-effect structure, carrier, set CE )
A cause-effect structure (c-e structure) over X is a pair U = C, E of total
functions:
C: X → F [X] (cause function; nodes occuring in C(x) are causes of x)
E: X → F [X] (effect function; nodes occuring in E(x) are effects of x)
such that x occurs in the formal polynomial C(y) iff y occurs in E(x). Carrier
of U is the set car(U ) = {x ∈ X : C(x) = θ ∨ E(x) = θ}. U is of finite carrier
iff |car(U )| < ∞ (|...| denotes cardinality). The set of all c-e structures over X
is denoted by CE [X]. Since X is fixed, we write just CE.
C and E are total, thus each c-e structure comprises all nodes from X, also the
isolated ones - those from outside of its carrier. In presenting c-e structures
graphically, only their carriers are drawn. A representation of a c-e structure
C(x)
U = C, E as a set of annotated nodes is {xE(x) : x ∈ car(U )}. U is
also presented as a directed graph with car(U ) as set of vertices labelled with
C(x)
objects of the form xE(x) (x ∈ car(U )); there is an edge from x to y iff y occurs
in the polynomial E(x). Fig.1.1 (a) and (b) depict two graphical presentations
of the same c-e structure with carrier {a, b, c, d, e, f, g, h}; in (a) the encircled
nodes comprise groups making products in formal polynomials in (b), where the
sums of the products create families of the groups. This c-e structure is the set
{aθe , bθe , cθe , dθe , efa+b·c+c·d
·g+h , fθe , gθe , heθ }.
Fig.1.1 (a) Predecessors and successors of the node e, grouped into families:
{{a}, {b, c}, {c, d}} and {{f, g}, {h}}. (b) Notation by means of polynomials;
the arrows are redundant: used only for graphic presentation of c-e structures
Definition 1.3 (addition and multiplication, monomial c-e structure)
For c-e structures U = CU , EU , V = CV , EV define:
U + V = CU +V , EU +V = CU + CV , EU + EV where
(CU + CV )(x) = CU (x) + CV (x) and similarly for E
U • V = (CU •V , EU •V ) = (CU • CV , EU • EV ) where
(CU • CV )(x) = CU (x) • CV (x) and similarly for E
2
(The same symbols "+" and "•" are used for operations on c-e structures and
formal polynomials). U is a monomial c-e structure iff each polynomial CU (x)
and EU (x) is a monomial, i.e. does not comprise non-reducible (relative to
equations in Definition 1.1) operation “+“.
Apart from the representation of c-e structures as a set
C(x)
{xE(x) : x ∈ car(U)}, their linear notation is used as the so-called "arrow-
expressions": {xθy , yθx } is an arrow, denoted as x → y and, consequently,
{xθy , yθx } • {yzθ , zθy }•{zuθ , uzθ }..... = {xθy , yzx , zuy , uz.... .....} is a chain, denoted as
x → y → z → u.... . Bidirectional arrow x ↔ y denotes x → y → x (equivalent
to y → x → y), that is, the close cycle {xyy , yxx }. Chains and arrows in particular,
may be combined into “arrow expressions” representing some c-e structures. For
instance c-e structure {aθx+y , bθx•y , xθa•b , yθa•b } may be written as (a → x + a →
y) • (b → x) • (b → y).
The set CE with addition, multiplication and a distinguished element de-
noted also by θ and understood as the empty c-e structure (θ, θ), where θ is a
constant function θ(x) = θ for all x ∈ X, makes an algebraic system similar
to that in Definition 1.1, the quasi-semiring of c-e structures. Therefore, the
system CE [X], +, •, θ obeys the following equations for all
U, V, W ∈ CE [X], x, y ∈ X:
(+) θ+U =U +θ =U (•) θ•U =U •θ =U
(++) U +U = U (••) (x → y)•(x → y) = x → y
(+++) U + V = U + V (• • •) U •V =V •U
(++++) U +(V + W ) = (U + V ) + W (• • ••) U • (V • W ) = (U • V )• W
(+•) If CV (x) = θ ⇔ CW (x) = θ and EV (x) = θ ⇔ EW (x) = θ then
U • (V + W ) = U • V + U • W
Definition 1.4 (partial order ≤; substructure, set SUB[V ], firing compo-
nent, set FC, pre-set and post-set)
For U, V ∈ CE let U ≤ V ⇔ V = U + V ; ≤ is a partial order in CE. If
U ≤ V then U is a substructure of V ; SUB[V ]= {U : U ≤ V } is the set
of all substructures of V . For A ⊆CE : V ∈ A is minimal (w.r.t. ≤) in A iff
∀W ∈ A: (W ≤ V ⇒ W = V ).
A minimal in CE \{θ} c-e structure Q = (CQ , EQ ) is a firing component iff Q
is a monomial c-e structure and CQ (x) = θ ⇔ EQ (x) = θ for any x ∈ car(Q).
The set of all firing components is denoted by FC, thus the set of all firing
components of U ∈CE is FC [U ] = SUB[U ] ∩ FC. Let for Q ∈ FC and
G ⊆ FC :
•
Q = {x ∈ car(Q) : CQ (x) = θ} (pre-set of Q)
Q• = {x∈ •car(Q) : EQ (x) = θ} (post-set of Q)
•
G= Q (pre-set of G)
Q∈G
3
G• = Q• (post-set of G)
Q∈G
Definition 1.5 (state of elementary c-e structures)
A state is a subset of the set of nodes: s ⊆ X. The set of all states: S = 2X .
A node x is active at the state s iff x ∈ s and passive otherwise. As in case
of Petri nets, we say ”x holds a token” when x is active. Obviously, the state
might be defined equivalently as a two-valued function s: X →{0, 1}.
Definition 1.6 (sequential and parallel semantics of elementary c-e struc-
tures)
Sequential. For Q ∈FC [U ] , s ∈ S, let [[Q]] ⊆ S × S be a binary relation
defined as:
(s, t) ∈ [[Q]] iff • Q ⊆ s ∧ Q• ∩ s = ∅ ∧ t = (s\• Q) ∪ Q• (Q transforms state
s into t). Semantics [[U ]] of U ∈CE is: [[U ]] = [[Q]]. [[U ]]∗ is
Q∈FC [U ]
its reflexive and transitive closure, that is, (s, t) ∈ [[U ]]∗ if and only if s = t
or there exists a sequence of states s0 , s1 , ..., sn with s = s0 , t = sn and
(sj , sj+1 ) ∈ [[U]] for j = 0, 1, ..., n − 1. State t is reachable from s in semantics
[[ ]] and the sequenece s0 , s1 , ..., sn is called a computation in U.
Parallel. Firing components Q and P are detached if and only if • Q• ∩ • P • =
∅. For G ⊆FC [U ], G = ∅, containing only pairwise detached (pwd) firing
components, let [[G]]par ⊆ S×S be a binary relation defined as: (s, t) ∈ [[G]]par
iff • G ⊆ s∧G• ∩s = ∅∧t = (s\• G)∪G• (G transforms state s into t). Semantics
[[U ]]par of U ∈CE is: [[U ]]par = [[G]]par . Closure [[U ]]∗par
G⊆ FC[U]∧G is pwd
and reachability and computation are defined as in the sequential case.
Note that [[U ]] = ∅ iff FC [U ] = ∅. Behaviour of elementary c-e structures may
be thought of as a token game: if each node in a firing component’s pre-set holds
a token and none in its post-set does, then remove tokens from the pre-set and
put them in the post-set. This is illustrated in Fig.1.2. A number of properties
inferred from above definitions are in [Cza 2019].
Fig.1.2. Example of activity (successive transformations) of a c-e structure.
4
2. A summary of extended cause-effect structures
The structural definition of extended c-e structures, their firing component
in particular, is the same as in Definitions 1.1 - 1.4. The extensions consist
in redefining the state, treating the pre and post sets of firing components as
multisets, and redefining semantics. It is assumed that with a given c-e struc-
ture U ∈CE [X] (i.e. already constructed by operations introduced in Definition
1.3) and the set of its firing components FC [U ] = SUB[U ]∩FC, some addi-
tional informations are associated. The following extensions of elementary c-e
structures endowed with such informations will be acquired: c-e structures with
multi-valued nodes thus their capacities, coefficients of monomials in polynomi-
als annotating nodes (counterparts of weight of arrows in place/transition Petri
nets) and with inhibitors. To this end, a notation for multisets is convenient:
let N be the set of natural numbers including 0 and Nω = N ∪ {ω}, where the
value ω means infinity, that is ω > n for each n ∈ N. A multiset over a set X
is a (total) function f : X → Nω . If the set {x: f (x) = 0} is finite then the
X a b c d e
linear-form notation is adopted for multisets , e.g.
f (X) 2 0 3 1 ω
is denoted as 2 ⊗ a + 3 ⊗ c + d + ω ⊗ e. A multiset is zero O, when O(x) = 0
for all x. Addition, subtraction and multiplication on multisets is defined:
(f + g)(x)g(x) = f(x) + g(x), (f − g)(x) = f (x) − g(x) for f (x) ≥ g(x),
(f · g)(x) = f (x) · g(x), comparison of multisets: f ≤ g iff f(x) ≤ g(x) for
all x. Assume the customary arithmetic of ω: ω + n = ω, ω − n = ω, ω + ω = ω
and additionally 0 − ω = 0.
Definition 2.1 (state)
_
A state of extended c-e structure U is a total function s : car(U ) → N, thus a
multiset over car(U ). The set of all states of U is denoted by S.
Definition 2.2. (weights of monomials and capacity of nodes)
For a c-e structure U = C, E and its firing component Q ∈FC [U ], let
with the pre-set • Q and post-set Q• of Q, some multisets • Q: • Q → Nω
and Q• : Q• → Nω be given as additional information. The value • Q(x)
is a weight (or multiplicity) of monomial EQ (x) and the value Q• (x) - a
weight (or multiplicity) of monomial CQ (x). Let • Q(x) = 0 for x ∈ / • Q and
Q (x) = 0 for x ∈
• / Q . Let cap be a total function cap : car(U ) → Nω \{0},
•
assigning a capacity to each node in the set car(U ). A c-e structure with such
enhanced firing components is called a c-e structure-with-weights of monomials
and capacity of nodes.
5
Definition 2.3. (enabled firing components and inhibitors)
For a firing component Q ∈FC [U ], let inh[Q] = {x ∈ • Q : • Q(x) = ω}, thus
a set of nodes in the pre-set of Q, whose effect monomials EQ (x) are of weight
ω. The nodes in inh[Q] will play
_
role of inhibiting nodes of firing component
_
Q,
as follows. For Q and state s let us define the formula: enabled[Q]( s) if and
only if:
∀x ∈ inh[Q] : s(x) = 0∧
∀x ∈ • Q\inh[Q] : • Q(x) ≤ s(x) ≤ cap(x)∧
∀x ∈ Q• : Q• (x) + s(x) ≤ cap(x)
_
So, Q is enabled in the state s iff none of inhibiting nodes x ∈ • Q contains
a token and each remaining node in • Q does, with no fewer tokens than is the
weight of its effect monomial EQ (x) and no more than capacity of each x ∈ • Q.
Moreover, none of x ∈ Q• holds more tokens than their number increased by
the weight of its cause monomial CQ (x), exceedes capacity of x. The inhibiting
nodes of a firing components will be called its inhibitors.
Definition 2.4. (Sequential and parallel semantics of extended c-e structures)
Sequential. For Q ∈FC [U ] , let [[Q]] ⊆ S × S be a binary relation defined as:
_ _
(s, t) ∈ [[Q]] iff enabled[Q]( s) ∧ t = ( s − • Q) + Q• ≤ cap (Q transforms state
s into t). Semantics [[U ]] of U ∈CE is [[U ]] = [[Q]]. Closure
Q∈FC [U ]
[[U ]]∗ and reachability and computation are defined as in Definition 1.6.
Parallel. For G ⊆FC [U ], G = ∅, containing only pairwise detached (pwd)
firing components, let [[G]]par ⊆ S × S_ be a_binary relation defined as: (s, t) ∈
[[G]]par iff ∀Q ∈ G : (enabled[Q]( s) ∧ ( s − • Q) + Q• ≤ cap) (say: G
transforms
state s into t). Semantics [[U ]]par of U ∈CE is: [[U ]]par =
[[G]]par . Closure [[U ]]∗par , reachability and computation are
G⊆ FC[U]∧G is pwd
defined as above.
An example of using inhibitor is in Fig.2.1. The weight of one effect (i.e.
subscript) monomial ω ⊗ z of the node T is ω, thus traversing arrow from T to z
would require infinite number of tokens at T , which is impossible. Thus, T is the
inhibiting node in firing component Q0 and ordinary - in firing component Q1 .
In accordance with aforesaid notation of multisets, the weighted monomials are
denoted by w⊗M (in grey font in figures - if w = ω), where w is the weight of M
- an unweighted monomial. The weight is skipped if w = 1. The corresponding
arrows are grey and dashed in the figures if w = ω.
6
Fig.2.1. Construction of c-e structure Q0 + Q1 implementing "test zero", in
accordance with Definition 1.3. A token at the node i starts testing contents
of T ; on termination, the token appears at z (zero) if T is empty and at n
(not zero) otherwise. The tested node T plays two roles: inhibiting in Q0 and
ordinary in Q1 . Capacity of T is infinite, whereas of remaining nodes is 1.
The empty subscript/superscript is skipped. In the Petri net counterpart, the
inhibiting arrow enters the left transition.
3. Modelling of arithmetic operations in c-e structures
A natural number "n" is represented by a collection of n tokens placed at a
node. Thus, the unary coding of numbers is adopted, being their basic repre-
sentation in the Peano standard model of arithmetic. Although such coding is
cumbersome in practical computing in comparison with codings in base greater
than 1, it is used in some theoretical problems of complexity, e.g. [Gar 1978] and
in data compression, e.g. [Gol 1966]. Also, such coding is used in the Church’s
lambda calculus [Chu 1941]. Notice that algorithms for arithmetic operations on
numbers coded in base greater than 1 require referring to tables (in fact to some
algorithms performed on the lower level, e.g. by computer hardware) of these
operations on single digits. This is not the case with the unary coding. Such
algoritms only rewrite one digit, a token, in our case, from one place to another.
In this section, modelling of arithmetic operations exemplifies some capability
of c-e structures and shows exact number of token moves in seven exemplary c-e
structures, in order to get results of typical arithmetic operations. The mod-
elling is presented in the form of c-e structures as graphs with nodes labelled
by the identifiers, with polynomials in their superscript (causes) and subscript
(effects), as exemplified in Figs 1.2 and 2.1. Nodes for input and output data
of unbounded capacity ω, will be drawn as bigger circles with double edge. Re-
maining nodes, the "control", are of capacity 1 and drawn as smaller circles.
The grey dashed arrows represent inhibiting. To distinguish multiplication of
numbers from multiplication of polynomials in c-e structures, the symbol "×"
is used in case of numbers. Each c-e structure has initial node "start" and final
"stop", that hold a token only at the beginning and termination of its activity,
respectively.
3.1. The addition (iterated adding of unity)
The sum n + m is obtained by m-times adding 1 to n or n-times adding 1 to m.
7
Fig.3.1 Implementation of n + m. Placing n tokens at x and m tokens at y
and one token at start, makes the c-e structure terminate with n + m tokens
at z and one token at stop. The result requires 2 × (n + m) + 1 moves (the
moves a → z and a → start take place simultaneously, so, are counted as one
move)
3.2. The subtraction (iterated subtracting of unity)
The difference n − m is obtained by m-times subtracting 1 simultaneously from
n and m, until n becomes 0, provided that m ≤ n.
•
Fig.3.2 Implementation of n − m. Placing n tokens at x and m tokens at y
and one token at start, makes the c-e structure terminate with n − m tokens
at z if m ≤ n and no token at z if m > n and one token at stop. The result
requires 2 × m + (n − m) + 1 = n + m + 1 moves (x → a and y → a occur
• n − m if m ≤ n
simultaneously, so, are counted as one move; n − m = )
0 if m > n
8
3.3. The multipliction (iterated adding of the same number)
Fig.3.3 Implementation of n × m. Placing n tokens at x and m tokens at y
and one token at start, makes the c-e structure terminate with n × m tokens
at z and and one token at stop. The result requires 2 × (n × m + n + 1) moves.
Remark. The number p = 2 × (n × m + n + 1) of moves can be
easily calculated inductively. The progress of result with growing n and m
is depicted in Table 3.1, where rows correspond to n and columns correspond to
m. The (n, m) entry contains the pair n × m; p. Notice that multiplication is
commutative with respect to the value of the product but not with respect to
the number of moves needed to obtain the product.
Table 3.1
1 2 3 4 5 6 7 8 9 10
1 1;6 2;8 3;10 4;12 5;14 6;16 7;18 8;20 9;22 10;24
2 2;10 4;14 6;18 8;22 10;26 12;30 14;34 16;38 18;42 20;46
3 3;14 6;20 9;26 12;32 15;38 18;44 21;50 24;56 27;62 30;68
4 4;18 8;26 12;34 16;42 20;50 24;58 28;66 32;74 36;82 40;90
5 5;22 10;32 15;42 20;52 25;62 30;72 35;82 40;92 45;102 50;112
6 6;26 12;38 18;50 24;62 30;74 36;86 42;98 48;110 54;122 60;134
7 7;30 14;44 21;58 28;72 35;86 42;100 49;114 56;128 63;142 70;156
8 8;34 16;50 24;66 32;82 40;98 48;114 56;130 64;146 72;162 80;178
9 9;38 18;56 27;74 36;92 45;110 54;128 63;146 72;164 81;182 90;200
10 10;42 20;62 30;82 40;102 50;122 60;142 70;162 80;182 90;202 100;222
3.4. The division with neglected remainder (iterated subtracting
of divisor from divident)
9
Fig.3.4 Implemntation of ⌊ mn
⌋. Placing n tokens at x and m > 0 tokens at y
and one token at start, makes the c-e structure terminate with ⌊ m
n
⌋ tokens at
z and one token at stop. The result requires p = f (n, m) moves and this value
is computed from equation f (n, m) = n + m + 2 + f(n − m, m), for m ≤ n
and p = 2 × (n + 1) for m > n
Remark. The number p = f (n, m) of moves is obtained as solution to
the recursive equation f(n, m) = n + m + 2 + f (n − m, m) for m ≤ n and
p = 2 × (n + 1) for n < m. Notice that if we admit m = 0 then the c-e
structure in Fig.3.4 might run into the "livelock": the two-way relocation of
tokens between nodes x and x′ might never end, with permanently empty z if
n > 0, and with unboundedly growing number of tokens at z if n = 0. The
equation results from observation of the c-e structure’s activity, exploiting its
symmetric (with respect to the vertical line between start and stop) shape. The
progress of p with growing n (dividend) and m (divisor) is depicted in Table 3.2,
where rows correspond to n and columns correspond to m. The (n, m) entry
contains the pair ⌊ mn
⌋; p.
10
Table 3.2
1 2 3 4 5 6 7 8 9 10
0 0;2 0;2 0;2 0;2 0;2 0;2 0;2 0;2 0;2 0;2
1 1;6 0;4 0;4 0;4 0;4 0;4 0;4 0;4 0;4 0:4
2 2;11 1;8 0;6 0;6 0;6 0;6 0;6 0;6 0;6 0:6
3 3;17 1;11 1;10 0;8 0;8 0;8 0;8 0;8 0;8 0:8
4 4;24 2;16 1;13 1;12 0;10 0;10 0;10 0;10 0;10 0;10
5 5;32 2;20 1;16 1;15 1;14 0;12 0;12 0;12 0;12 0;12
6 6;41 3;26 2;21 1;18 1;17 1;16 0;14 0;14 0;14 0;14
7 7;51 3;31 2;25 1;21 1;20 1;19 1;18 0;16 0;16 0;16
8 8;62 4;38 2;29 2;26 1;23 1;22 1;21 1;20 0;18 0;18
9 9;74 4;44 3;35 2;30 1;26 1;25 1;24 1;23 1;22 0;20
10 10;87 5;52 3;40 2;34 2;31 1;28 1;27 1;26 1;25 1;24
3.5. The division with remainder
Fig.3.5 Implemntation of (⌊ m n
⌋, mod(n, m)). Placing n tokens at x and m > 0
tokens at y and one token at start, makes the c-e structure terminate with ⌊ m
n
⌋
tokens at z and with mod(n, m) tokens (i.e. remainder of dividing n by m) at
r and one token at stop. The result requires p + 2 × mod(n, m) + 1 moves,
where p is such as in division with neglected remainder.
Remark. The bidirectional moves s ↔ t and s′ ↔ t′ ("pumping of
tokens") involve auxiliary nodes, because the close loops, like s ↔ s, in the
c-e structures, do not contain firing components, thus do not yield any activity.
Notice also the Remark on division with neglected remainder.
11
3.6. The exponentiation (iterated multiplication of the number
by itself )
Fig.3.6 Implementation of exponentiation nk for k > 1. Placing n tokens at x
as well as at y, and k − 2 tokens at c (the counter of multiplication iterations)
and one token at start, makes the c-e structure terminate with nk tokens at z,
and with one token at stop.
Remark. 0k = 0 and 1k = 1 is obtained by placing k tokens at c. The
number of moves required to obtain the result nk is straightforwardly calculated
applying number p, for multiplication (Fig.3.3) with m = n. Notice that the
value of 0k and of 1k does not depend of k, but the number of moves - does.
12
3.7. The factorial (iterated multiplication with successively de-
creased argument)
Fig.3.7 Implementation of factorial n! for n > 1. Placing n tokens at x as well
as at y, and n − 2 tokens at c, and one token at start, makes the c-e structure
terminate with n! tokens at z, and with one token at stop.
Remark. The number of moves required to obtain the result n! is calculated
as in case of exponentiation, but with removing one token from y and y ′ at any
step of iteration. Notice that the following moves (i.e. firing components):
(y → h′ ) • (start → h′ ) and (y ′ → h) • (start → h) remove tokens from y
and from y ′ . Thus, they make decrease by 1 contents of y and y′ at any step of
iteration.
4. Computing of some arithmetic functions - examples
4.1. Summation of sequence of numbers, sequential computation
y := x1 + x2 + x3 + x4 + x5 + x6 + x7,
initial state: s(start) = 1, s(a) = 0, s(y) = 0, s(x1) = 3, s(x2) = 1,
s(x3) = 2, s(x4) = 0, s(x5) = 4, s(x6) = 0, s(x7) = 1
13
Fig.4.1 On termination, the variable y contains 11 tokens
4.2 Inner product ⊠ of two vectors, sequential computaion
x1, x2, x3, x4, x5 ⊠ y1, y2, y3, y4, y5
z1 := x1 × y1; z2 := x2 × y2; z3 := x3 × y3; z4 := x4 × y4; z5 := x5 × y5
z1 := z1 + z2 + z3 + z4 + z5. Here, as in previous sections, "×" denotes
multiplication of numbers.
Fig.4.2 Inner roduct of vectors x1, x2, x3, x4, x5 and y1, y2, y3, y4, y5.
Sequential computation. On termination, result is in the variable z1. In this fig-
ure, nodes with not shown superscript and subscript polynomials, are annotated
yk•ik yk’•(ik’+t[i−1])
as follows: akzk•ik , ak’yk’•ik’ yk•ik start+y1’•i1’
zk•ik’ , hkik’+tk , h1’i1+t1 , hk’ik+tk if
ak+hk’•xk ak’+hk•xk yk’ yk
k > 1, ikak+hk , ik’ak’+hk’ , xkik+ω⊗tk , ykω⊗hk+ak•yk’ , yk’ω⊗hk’+ak’•yk ,
θ
where k = 1, 2, 3, 4, 5. Superscripts and subscripts of node names are readily
seen from the arrows entering and exiting these nodes
14
4.3 Inner product ⊠ of two vectors, parallel computaion
The same vectors as in 4.2.
Fig.4.3 Inner roduct of vectors x1, x2, x3, x4, x5 and y1, y2, y3, y4, y5.
Parallel computation. On termination, result is in the variable z1. In this
figure, nodes with not shown superscript and subscript polynomials, are anno-
yk•ik
tated as follows: akzk•ik , ak’yk’•ik’ yk•ik start+yk’•ik’
zk•ik’ , hkik’+tk , hk’ik+tk
ak+hk’•xk
, ikak+hk ,
ak’+hk•xk yk’ yk
ik’ak’+hk’ , xkik+ik’+ω⊗tk
θ
, ykω⊗hk+ak•yk’ , yk’ω⊗hk’+ak’•yk , where k =
1, 2, 3, 4, 5.
Final note
It is shown in [Cza 2019] the behavioural equivalence of the c-e structures
and place/transition Petri nets with inhibitors. Such systems enjoy the full Tur-
ing expressive power, thus are capable of arithmetic computations. This draft
is intended to explicitly show, how the abovementioned seven typical arith-
metic operations can be performed by c-e structures. Since every arithmetic
function may be composed of such operations, with possible usage of recursion
and the minimum combinator, the c-e structures for these operations, suitably
combined, are expected to expose some details of computing such functions, in
particular their exact, not only asymptotic, computational cost. In the mod-
elling of the seven arithmetic operations, the ordinary (sequential, not parallel
- cf. [Cza 2019]) semantics of c-e structures has been applied. This follows the
classic standard modelling of arithmetic. Application of the parallel semantics
may influence, at most, the number of simultaneous token relocations, not com-
puting power of the modelling, i.e. the class of computed functions. Finally,
notice that the iteration of actions in above c-e structures, is accomplished by
oscillation of work between their symmetric parts. This corresponds to usage
15
of the combinator of recursion in the classic definition of computable functions,
whereas the "test zero" (Fig.2.1) makes possible to accomplish the combinator
of minimum.
References
[Chu 1941] Church A. The calculi of lambda conversion, Annals of Mathematics
Studies, nr 6, Princeton University Press, 1941
[Cza 2019] Czaja L. Cause-Effect Structures. An Algebra of Nets with Examples
of Application, Lecture Notes in Networks and Systems 45, Springer 2019
[Gar 1978] Garey M. R.; Johnson, D. S., ’Strong’ NP-completeness results: Mo-
tivation, examples, and implications, Journal of the ACM, 25 (3), 1978, pp.
499—508,
[Gol 1966] Golomb S.W., Run-length encodings, IEEE Transactions on Infor-
mation Theory, IT-12 (3), 1966, pp. 399—401
16