# 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:

1. ${\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}}$.

2. ${\mathbf{D}}$2.

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}\}$.

3. ${\mathbf{D}}$3.

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 (http://planetmath.org/4measurement#Thmrem3).

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 $\operatorname{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}:\operatorname{Hom}\left({\mathcal{V}}{A}^{{\mathbf{C}}_{2% }},{\mathcal{V}}{S}^{{\mathbf{C}}_{2}}\right)$ $\displaystyle\rightarrow\operatorname{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 (http://planetmath.org/2stochasticmaps#Thmeg1)

The reason for naming ${\mathtt{Meas}}_{\mathbf{D}}$ the category of measuring devices will become clear in §4 (http://planetmath.org/4measurement) 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\operatorname{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 (http://planetmath.org/2stochasticmaps#Thmthm3).

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 here11which 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}})=\operatorname{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: the world of attractor neural networks. Cambridge University Press.
• 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. Title 3. Distributed dynamical systems 3DistributedDynamicalSystems 2014-04-30 18:41:46 2014-04-30 18:41:46 rspuzio (6075) rspuzio (6075) 15 rspuzio (6075) Feature msc 60J20 msc 81P15 msc 18F20