## You are here

Home3. Distributed dynamical systems

## Primary tabs

# 3. Distributed dynamical systems

Probabilistic cellular automata provide useful toy models of a wide range of physical and biological systems. A cellular automaton consists of a collection of cells, each equipped with neighbors. Two important important examples are

###### Example 2 (Conway’s game of life).

The cellular automaton is a grid of deterministic cells with outputs $\{0,1\}$. A cell outputs 1 at time $t$ iff: (i) three of its neighbors outputted 1s at time $t-1$ or (ii) it and two neighbors outputted 1s at $t-1$. Remarkably, a sufficiently large game of life grid can implement any deterministic computation [3].

###### Example 3 (Hopfield networks).

These are probabilistic cellular automata [4, 1], again with outputs $\{0,1\}$. Cell $n_{k}$ fires with probability proportional to

$p(n_{{k,t}}=1|n_{{\bullet,t-1}})\propto\exp\left[\frac{1}{T}\sum_{{j% \rightarrow k}}\alpha_{{jk}}\cdot n_{{j,{t-1}}}\right].$ |

Temperature $T$ controls network stochasticity. Attractors $\{\xi^{1},\ldots,\xi^{N}\}$ are embedded into a network by setting the connectivity matrix as $\alpha_{{jk}}=\sum_{{\mu=1}}^{N}(2\xi_{j}^{\mu}-1)(2\xi_{k}^{\mu}-1)$.

It is useful to take a finer perspective on cellular automata by decomposing them into spacetime coordinates or occasions [2]. An occasion ${v}_{l}=n_{{i,t}}$ is a cell $n_{i}$ at a time point $t$. Two occasions are linked ${v}_{k}\rightarrow{v}_{l}$ if there is a connection from ${v}_{k}$’s cell to ${v}_{l}$’s (because they are neighbors or the same cell) and their time coordinates are $t-1$ and $t$ respectively for some $t$, so occasions form a directed graph. More generally:

###### Definition 4.

A *distributed dynamical system* ${\mathbf{D}}$ consists of
the following data:

- ${\mathbf{D}}$1.
*Directed graph*. A graph $G_{{\mathbf{D}}}=(V_{{\mathbf{D}}},E_{{\mathbf{D}}})$ with a finite set of vertices or occasions $V_{{\mathbf{D}}}=\{{v}_{1}\ldots{v}_{n}\}$ and edges $E_{{\mathbf{D}}}\subset V_{{\mathbf{D}}}\times V_{{\mathbf{D}}}$. - ${\mathbf{D}}$1.
*Alphabets.*Each vertex ${v}_{l}\in V_{{\mathbf{D}}}$ has finite alphabet ${A}_{l}$ of outputs and finite alphabet ${S}_{l}:=\prod_{{k\in src(l)}}A_{k}$ of inputs, where $src(l)=\{{v}_{k}|{v}_{k}\rightarrow{v}_{l}\}$. - ${\mathbf{D}}$1.
*Mechanisms.*Each vertex ${v}_{l}$ is equipped with stochastic map ${\mathfrak{m}}_{l}:{\mathcal{V}}{S}_{l}\rightarrow{\mathcal{V}}{A}_{l}$.

Taking any cellular automaton over a finite time interval
$[t_{\alpha},t_{\omega}]$ initializing the mechanisms at time
$t_{\alpha}$ with fixed values (initial conditions) or
probability distributions^{} (noise sources) yields a distributed
dynamical system, see Fig. 1. Each cell of the
original automaton corresponds to a series of occasions in
the distributed dynamical system, one per time step.

Cells with memory – i.e. whose outputs depend on their neighbors outputs over multiple time steps – receive inputs from occasions more than one time step in the past. If a cell’s mechanism changes (learns) over time then different mechanisms are assigned to the cell’s occasions at different time points.

The sections^{} below investigate the compositional structure of
measurements: how they are built out of submeasurements.
Technology for tracking subsystems and submeasurements is
therefore necessary. We introduce two closely related
categories:

###### Definition 5.

The *category of subsystems* ${\mathtt{Sys}}_{{\mathbf{D}}}$ of ${\mathbf{D}}$
is a Boolean lattice with objects given by sets of ordered
pairs of vertices ${\mathbf{C}}\in\underline{2}^{{V_{{\mathbf{D}}}\times V_{{\mathbf{D}}}}}$ and arrows given by inclusions $i_{{12}}:{\mathbf{C}}_{1}\hookrightarrow{\mathbf{C}}_{2}$. The initial and terminal
objects are $\bot_{{\mathbf{D}}}=\emptyset$ and $\top_{{\mathbf{D}}}=V_{{\mathbf{D}}}\times V_{{\mathbf{D}}}$.

###### Remark 2.

Subsystems are defined as ordered pairs of vertices,
rather than subgraphs of the directed graph of ${\mathbf{D}}$.
Pairs of occasions that are not connected by edges are
*ineffective*; they do not contribute to the
information-processing performed by the system. We include
them in the formalism precisely to make their lack of
contribution explicit, see Remark 3.

Let $src({\mathbf{C}})=\{{v}_{k}|({v}_{k},{v}_{l})\in{\mathbf{C}}\}$ and similarly for $trg({\mathbf{C}})$. Set the input alphabet of ${\mathbf{C}}$ as the product^{} of the output alphabets of its source occasions ${S}^{{\mathbf{C}}}=\prod_{{src({\mathbf{C}})}}A_{k}$ and similarly the output alphabet of ${\mathbf{C}}$ as the product of the output alphabets of its target occasions ${A}^{{\mathbf{C}}}=\prod_{{trg({\mathbf{C}})}}A_{l}$.

###### Definition 6.

The *category of measuring devices* ${\mathtt{Meas}}_{{\mathbf{D}}}$ on ${\mathbf{D}}$ has objects $\Hom_{{\mathtt{Stoch}}}({\mathcal{V}}{A}^{{\mathbf{C}}},{\mathcal{V}}{S}^{{%
\mathbf{C}}})$ for ${\mathbf{C}}\in\underline{2}^{{V_{{\mathbf{D}}}\times V_{{\mathbf{D}}}}}$. For ${\mathbf{C}}_{1}\hookrightarrow{\mathbf{C}}_{2}$ define arrow

$\displaystyle r_{{21}}:\Hom\left({\mathcal{V}}{A}^{{{\mathbf{C}}_{2}}},{% \mathcal{V}}{S}^{{{\mathbf{C}}_{2}}}\right)$ | $\displaystyle\rightarrow\Hom\left({\mathcal{V}}{A}^{{{\mathbf{C}}_{1}}},{% \mathcal{V}}{S}^{{{\mathbf{C}}_{1}}}\right)$ | ||

$\displaystyle\left[{\mathcal{V}}{A}^{{{\mathbf{C}}_{2}}}\xrightarrow{T}{% \mathcal{V}}{S}^{{{\mathbf{C}}_{2}}}\right]$ | $\displaystyle\mapsto\left[{\mathcal{V}}{A}^{{{\mathbf{C}}_{1}}}\xrightarrow{% \pi^{\natural}_{{A}}}{\mathcal{V}}{A}^{{{\mathbf{C}}_{2}}}\xrightarrow{T}{% \mathcal{V}}{S}^{{{\mathbf{C}}_{2}}}\xrightarrow{\pi_{{S}}}{\mathcal{V}}{S}^{{% {\mathbf{C}}_{1}}}\right],$ |

where $\pi_{A}$ and $\pi_{S}$ are shorthands for projections as in Example 1

The reason for naming ${\mathtt{Meas}}_{{\mathbf{D}}}$ the category of measuring devices will become clear in §4 below. The two categories are connected by contravariant functor ${\mathcal{F}}$:

###### Theorem 4 (structure presheaf).

The *structure presheaf ^{}* ${\mathcal{F}}$ taking

${\mathcal{F}}_{{\mathbf{D}}}:{\mathtt{Sys}}_{{\mathbf{D}}}^{{\mathtt{op}}}% \rightarrow{\mathtt{Meas}}_{{\mathbf{D}}}:{\mathbf{C}}\mapsto\Hom\left({% \mathcal{V}}{A}^{{\mathbf{C}}},{\mathcal{V}}{S}^{{\mathbf{C}}}\right)\mbox{ % and }i_{{12}}\mapsto r_{{21}}$ |

satisfies the gluing axiom but has non-unique descent.

Proof: Functor ${\mathcal{F}}$ is trivially a presheaf since it is
contravariant. It is an *interesting* presheaf because
the gluing axiom holds.

For gluing we need to show that for any collection
$\{{\mathbf{C}}_{j}\}_{{j=1}}^{l}$ of subsystems and sections
${\mathfrak{m}}_{j}^{\natural}\in{\mathcal{F}}_{{\mathbf{D}}}({\mathbf{C}}_{j})$ such that
$r_{{j,ji}}({\mathfrak{m}}_{j}^{\natural})=r_{{i,ji}}({\mathfrak{m}}_{i}^{%
\natural})$
for all $i$, $j$ there exists section ${\mathfrak{m}}^{\natural}\in{\mathcal{F}}_{{\mathbf{D}}}\left(\bigcup_{{j=1}}^%
{l}{\mathbf{C}}_{j}\right)$ such that
$r_{i}({\mathfrak{m}}^{\natural})={\mathfrak{m}}^{\natural}_{i}$ for all $i$. This reduces
to finding a conditional^{} distribution that causes diagram

in ${\mathtt{Meas}}_{{\mathbf{D}}}$ to commute. The vertices are conditional distributions and the arrows are marginalizations, so rewrite as

where $p(x|w)=\sum_{{v,z}}p(x,z|v,w)p^{{maxH}}(v)$ and similarly for the vertical arrow. It is easy to see that

$p(x,y,z|u,v,w):=\frac{p(x,y|u,w)p(x,z|v,w)}{p(x|w)}$ |

satisfies the requirement.

For ${\mathcal{F}}$ to be a sheaf it would also have to satisfy
unique descent: the section satisfying the gluing axiom must
not only *exist* for any collection
$\{{\mathbf{C}}_{j}\}_{{j=1}}^{l}$ with compatible restrictions^{} but must
also be *unique*. Descent in ${\mathcal{F}}$ is not unique
because there are many distributions satisfying the requirement
above: strictly speaking $r$ is a marginalization operator
rather than restriction. For example, there are many
distributions $p(y,z)$ that marginalize to give $p(y)$ and
$p(z)$ besides the product distribution $p(y)p(z)$.
$\blacksquare$

The structure presheaf ${\mathcal{F}}$ depends on the graph structure and alphabets; mechanisms play no role. We now construct a family of sections of ${\mathcal{F}}$ using the mechanisms of ${\mathbf{D}}$’s occasions. Specifically, given a subsystem ${\mathbf{C}}\in{\mathtt{Sys}}_{{\mathbf{D}}}$, we show how to glue its occasions’ mechanisms together to form joint mechanism ${\mathfrak{m}}_{{\mathbf{C}}}$. The mechanism ${\mathfrak{m}}_{{\mathbf{D}}}={\mathfrak{m}}_{\top}$ of the entire system ${\mathbf{D}}$ is recovered as a special case.

In general, subsystem ${\mathbf{C}}$ is not isolated: it receives
inputs along edges contained in ${\mathbf{D}}$ but *not* in
${\mathbf{C}}$. Inputs along these edges cannot be assigned a fixed
value since in general there is no preferred element of
${A}_{l}$. They also cannot be ignored since ${\mathfrak{m}}_{l}$ is defined
as receiving inputs from all its sources. Nevertheless, the
mechanism of ${\mathbf{C}}$ should depend on ${\mathbf{C}}$ alone. We
therefore treat edges not in ${\mathbf{C}}$ as sources of extrinsic
noise by marginalizing with respect to the uniform distribution
as in Corollary 3.

For each vertex ${v}_{l}\in trg({\mathbf{C}})$ let ${S}^{{\mathbf{C}}}_{l}=\prod_{{k\in src(l)\cap src(C)}}{A}_{k}$. We then have projection $\pi_{l}:{\mathcal{V}}{S}_{l}\rightarrow{\mathcal{V}}{S}^{{\mathbf{C}}}_{l}$. Define

${\mathfrak{m}}^{{\mathbf{C}}}_{l}:=\left[{\mathcal{V}}{S}^{{\mathbf{C}}}_{l}% \xrightarrow{\pi_{l}^{\natural}}{\mathcal{V}}{S}_{l}\xrightarrow{{\mathfrak{m}% }_{l}}{\mathcal{V}}{A}_{l}\right].$ | (1) |

It follows immediately that ${\mathbf{C}}$ is itself a distributed dynamical system defined by its graph, whose alphabets are inherited from ${\mathbf{D}}$ and whose mechanisms are constructed by marginalizing.

Next, we tensor the mechanisms of individual occasions and glue
them together using the diagonal map $\Delta:{S}^{{\mathbf{C}}}\rightarrow\prod_{{v_{l}\in trg({\mathbf{C}})}}{S}^{{%
\mathbf{C}}}_{l}$. The
diagonal map used here^{1}^{1}which is surjective^{} in the
sense that all rows contain non-zero entries generalizes
$X\xrightarrow{\Delta}X\times X$ and removes redundancies in
$\prod_{l}{S}^{{\mathbf{C}}}_{l}$, which may, for example, include the
same source alphabets many times in different factors.

Let mechanism ${\mathfrak{m}}_{{\mathbf{C}}}$ be

${\mathfrak{m}}_{{\mathbf{C}}}:=\left[{\mathcal{V}}{S}^{{\mathbf{C}}}% \xrightarrow{\iota_{\Delta}}\bigotimes_{{{v}_{l}\in trg({\mathbf{C}})}}{% \mathcal{V}}{S}^{{\mathbf{C}}}_{l}\xrightarrow{\otimes_{{{v}_{l}\in trg({% \mathbf{C}})}}{\mathfrak{m}}^{{\mathbf{C}}}_{l}}{\mathcal{V}}{A}^{{\mathbf{C}}% }\right].$ | (2) |

The dual of ${\mathfrak{m}}_{{\mathbf{C}}}$ is

${\mathfrak{m}}_{{\mathbf{C}}}^{\natural}:=\left[{\mathcal{V}}{A}^{{\mathbf{C}}% }\rightarrow{\mathcal{V}}{S}^{{\mathbf{C}}}\right].$ | (3) |

Finally, we find that we have constructed a family of sections of ${\mathcal{F}}$:

###### Definition 7.

The *quale* $\mathbf{q}_{{\mathbf{D}}}$ is the family of
sections of ${\mathcal{F}}$ constructed in
Eqs. (1), (2) and
(3)

$\mathbf{q}_{{\mathbf{D}}}:=\left\{{\mathfrak{m}}^{\natural}_{{\mathbf{C}}}\in{% \mathcal{F}}({\mathbf{C}})=\Hom\left({\mathcal{V}}{A}^{{\mathbf{C}}},{\mathcal% {V}}{S}^{{\mathbf{C}}}\right)\Big|{\mathbf{C}}\in{\mathtt{Sys}}_{{\mathbf{D}}}% \right\}.$ |

The construction used to glue together the mechanism of the entire system can also be used to construct the mechanism of any subsystem, which provides a window – the quale – into the compositional structure of distributed processes.

# References

- 1
DJ Amit (1989):
*Modelling brain function*. Cambridge University Press.^{}: the world of attractor neural networks - 2
David Balduzzi (2011):
*Detecting emergent processes in cellular automata with excess information*. preprint . - 3
ER Berlekamp, JC Conway &
RK Guy (1982):
*Winning Ways for your Mathematical Plays*. 2, Academic Press. - 4
JJ Hopfield (1982):
*Neural networks and physical systems with emergent computational properties*. Proc. Nat. Acad. Sci. 79, pp. 2554–2558.

## Mathematics Subject Classification

60J20*no label found*81P15

*no label found*18F20

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections