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 $t1$ or (ii) it and two neighbors outputted 1s at $t1$. 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 ,t1})\propto \mathrm{exp}[\frac{1}{T}\sum _{j\to k}{\alpha}_{jk}\cdot {n}_{j,t1}].$$ 
Temperature $T$ controls network stochasticity. Attractors $\{{\xi}^{1},\mathrm{\dots},{\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}\to {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 $t1$ 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}\mathrm{\dots}{v}_{n}\}$ and edges ${E}_{\mathbf{D}}\subset {V}_{\mathbf{D}}\times {V}_{\mathbf{D}}$.

$\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}\to {v}_{l}\}$.

$\mathbf{D}$3.
Mechanisms. Each vertex ${v}_{l}$ is equipped with stochastic map ${\U0001d52a}_{l}:\mathcal{V}{S}_{l}\to \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 ${\mathrm{\U0001d682\U0001d6a2\U0001d69c}}_{\mathbf{D}}$ of $\mathbf{D}$ is a Boolean lattice with objects given by sets of ordered pairs^{} of vertices $\mathbf{C}\in {\underset{\xaf}{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 ${\perp}_{\mathbf{D}}=\mathrm{\varnothing}$ 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 informationprocessing 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 ${\mathrm{\U0001d67c\U0001d68e\U0001d68a\U0001d69c}}_{\mathbf{D}}$ on $\mathbf{D}$ has objects ${\mathrm{Hom}}_{\mathrm{\U0001d682\U0001d69d\U0001d698\U0001d68c\U0001d691}}(\mathcal{V}{A}^{\mathbf{C}},\mathcal{V}{S}^{\mathbf{C}})$ for $\mathbf{C}\in {\underset{\xaf}{2}}^{{V}_{\mathbf{D}}\times {V}_{\mathbf{D}}}$. For ${\mathbf{C}}_{1}\hookrightarrow {\mathbf{C}}_{2}$ define arrow
${r}_{21}:\mathrm{Hom}(\mathcal{V}{A}^{{\mathbf{C}}_{2}},\mathcal{V}{S}^{{\mathbf{C}}_{2}})$  $\to \mathrm{Hom}(\mathcal{V}{A}^{{\mathbf{C}}_{1}},\mathcal{V}{S}^{{\mathbf{C}}_{1}})$  
$\left[\mathcal{V}{A}^{{\mathbf{C}}_{2}}\stackrel{\mathit{T}}{\to}\mathcal{V}{S}^{{\mathbf{C}}_{2}}\right]$  $\mapsto \left[\mathcal{V}{A}^{{\mathbf{C}}_{1}}\stackrel{{\pi}_{A}^{\mathrm{\u266e}}}{\to}\mathcal{V}{A}^{{\mathbf{C}}_{2}}\stackrel{\mathit{T}}{\to}\mathcal{V}{S}^{{\mathbf{C}}_{2}}\stackrel{{\pi}_{S}}{\to}\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 ${\mathrm{\U0001d67c\U0001d68e\U0001d68a\U0001d69c}}_{\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^{} $\mathrm{F}$ taking
$${\mathcal{F}}_{\mathbf{D}}:{\mathrm{\U0001d682\U0001d6a2\U0001d69c}}_{\mathbf{D}}^{\mathrm{\U0001d698\U0001d699}}\to {\mathrm{\U0001d67c\U0001d68e\U0001d68a\U0001d69c}}_{\mathbf{D}}:\mathbf{C}\mapsto \mathrm{Hom}(\mathcal{V}{A}^{\mathbf{C}},\mathcal{V}{S}^{\mathbf{C}})\mathit{\text{and}}{i}_{12}\mapsto {r}_{21}$$ 
satisfies the gluing axiom but has nonunique 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 ${\U0001d52a}_{j}^{\mathrm{\u266e}}\in {\mathcal{F}}_{\mathbf{D}}({\mathbf{C}}_{j})$ such that ${r}_{j,ji}({\U0001d52a}_{j}^{\mathrm{\u266e}})={r}_{i,ji}({\U0001d52a}_{i}^{\mathrm{\u266e}})$ for all $i$, $j$ there exists section ${\U0001d52a}^{\mathrm{\u266e}}\in {\mathcal{F}}_{\mathbf{D}}\left({\bigcup}_{j=1}^{l}{\mathbf{C}}_{j}\right)$ such that ${r}_{i}({\U0001d52a}^{\mathrm{\u266e}})={\U0001d52a}_{i}^{\mathrm{\u266e}}$ for all $i$. This reduces to finding a conditional distribution that causes diagram
in ${\mathrm{\U0001d67c\U0001d68e\U0001d68a\U0001d69c}}_{\mathbf{D}}$ to commute. The vertices are conditional distributions and the arrows are marginalizations, so rewrite as
where $p(xw)={\sum}_{v,z}p(x,zv,w){p}^{maxH}(v)$ and similarly for the vertical arrow. It is easy to see that
$$p(x,y,zu,v,w):=\frac{p(x,yu,w)p(x,zv,w)}{p(xw)}$$ 
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)$. $\mathrm{\u25a0}$
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 {\mathrm{\U0001d682\U0001d6a2\U0001d69c}}_{\mathbf{D}}$, we show how to glue its occasions’ mechanisms together to form joint mechanism ${\U0001d52a}_{\mathbf{C}}$. The mechanism ${\U0001d52a}_{\mathbf{D}}={\U0001d52a}_{\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 ${\U0001d52a}_{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}_{l}^{\mathbf{C}}={\prod}_{k\in src(l)\cap src(C)}{A}_{k}$. We then have projection ${\pi}_{l}:\mathcal{V}{S}_{l}\to \mathcal{V}{S}_{l}^{\mathbf{C}}$. Define
$${\U0001d52a}_{l}^{\mathbf{C}}:=\left[\mathcal{V}{S}_{l}^{\mathbf{C}}\stackrel{{\pi}_{l}^{\mathrm{\u266e}}}{\to}\mathcal{V}{S}_{l}\stackrel{{\U0001d52a}_{l}}{\to}\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 $\mathrm{\Delta}:{S}^{\mathbf{C}}\to {\prod}_{{v}_{l}\in trg(\mathbf{C})}{S}_{l}^{\mathbf{C}}$. The diagonal map used here^{1}^{1}which is surjective^{} in the sense that all rows contain nonzero entries generalizes $X\stackrel{\Delta}{\to}X\times X$ and removes redundancies in ${\prod}_{l}{S}_{l}^{\mathbf{C}}$, which may, for example, include the same source alphabets many times in different factors.
Let mechanism ${\U0001d52a}_{\mathbf{C}}$ be
$${\U0001d52a}_{\mathbf{C}}:=\left[\mathcal{V}{S}^{\mathbf{C}}\stackrel{{\iota}_{\mathrm{\Delta}}}{\to}\underset{{v}_{l}\in trg(\mathbf{C})}{\otimes}\mathcal{V}{S}_{l}^{\mathbf{C}}\stackrel{{\otimes}_{{v}_{l}\in trg(\mathbf{C})}{\U0001d52a}_{l}^{\mathbf{C}}}{\to}\mathcal{V}{A}^{\mathbf{C}}\right].$$  (2) 
The dual of ${\U0001d52a}_{\mathbf{C}}$ is
$${\U0001d52a}_{\mathbf{C}}^{\mathrm{\u266e}}:=[\mathcal{V}{A}^{\mathbf{C}}\to \mathcal{V}{S}^{\mathbf{C}}].$$  (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\{{\U0001d52a}_{\mathbf{C}}^{\mathrm{\u266e}}\in \mathcal{F}(\mathbf{C})=\mathrm{Hom}(\mathcal{V}{A}^{\mathbf{C}},\mathcal{V}{S}^{\mathbf{C}})\right\mathbf{C}\in {\mathrm{\U0001d682\U0001d6a2\U0001d69c}}_{\mathbf{D}}\}.$$ 
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 Canonical name 3DistributedDynamicalSystems Date of creation 20140430 18:41:46 Last modified on 20140430 18:41:46 Owner rspuzio (6075) Last modified by rspuzio (6075) Numerical id 15 Author rspuzio (6075) Entry type Feature Classification msc 60J20 Classification msc 81P15 Classification msc 18F20