3. Distributed dynamical systems

Probabilistic cellular automata provide useful toy models of awide range of physical and biological systems. A cellularautomaton consists of a collection of cells, each equipped withneighbors. Two important important examples are

Example 2 (Conway’s game of life).

The cellular automaton is a grid of deterministic cellswith 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 anydeterministic 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 [\frac{1}{T}\sum _{j\to k}{\alpha }_{jk}\cdot n_{j,t-1}].$$

Temperature $T$ controls network stochasticity. Attractors$\{{\xi }^1,\mathrm{\dots },{\xi }^N\}$ are embedded into a network by settingthe 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 automataby 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$’scell to $v_l$’s (because they are neighbors or the same cell)and their time coordinates are $t-1$ and $t$ respectively forsome $t$, so occasions form a directed graph. More generally:

Definition 4.

A distributed dynamical system $𝐃$ consists ofthe following data:

1. Directed graph.A graph $G_{𝐃}=(V_{𝐃},E_{𝐃})$ with a finite set ofvertices or occasions $V_{𝐃}=\{v_1\mathrm{\dots }{v}_n\}$ andedges $E_{𝐃}\subset V_{𝐃}\times V_{𝐃}$.

2. Alphabets.Each vertex $v_l\in V_{𝐃}$ 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\}$.

3. Mechanisms.Each vertex $v_l$ is equipped with stochastic map${𝔪}_l:𝒱S_l\to 𝒱A_l$.

Figure 1: Mapping a cellular automaton to a distributeddynamical system.

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) orprobability distributions (noise sources) yields a distributeddynamical system, see Fig. 1. Each cell of theoriginal automaton corresponds to a series of occasions inthe distributed dynamical system, one per time step.

Cells with memory – i.e. whose outputs depend on theirneighbors outputs over multiple time steps – receive inputsfrom occasions more than one time step in the past. If a cell’smechanism changes (learns) over time then different mechanismsare assigned to the cell’s occasions at different time points.

The sections below investigate the compositional structure ofmeasurements: how they are built out of submeasurements.Technology for tracking subsystems and submeasurements istherefore necessary. We introduce two closely relatedcategories:

Definition 5.

The category of subsystems ${\mathrm{𝚂𝚢𝚜}}_{𝐃}$ of $𝐃$is a Boolean lattice with objects given by sets of orderedpairs of vertices $𝐂\in {\underset{¯}{2}}^{V_{𝐃}\times V_{𝐃}}$ and arrows given by inclusions $i_{12}:{𝐂}_1\hookrightarrow {𝐂}_2$. The initial and terminalobjects are ${\perp }_{𝐃}=\mathrm{\varnothing }$ and ${\top }_{𝐃}=V_{𝐃}\times V_{𝐃}$.

Remark 2.

Subsystems are defined as ordered pairs of vertices,rather than subgraphs of the directed graph of $𝐃$.Pairs of occasions that are not connected by edges areineffective; they do not contribute to theinformation-processing performed by the system. We includethem in the formalism precisely to make their lack ofcontribution explicit, see Remark 3 (http://planetmath.org/4measurement#Thmrem3).

Let $src(𝐂)=\{v_k|(v_k,v_l)\in 𝐂\}$ and similarly for $trg(𝐂)$. Set the input alphabet of $𝐂$ as the product of the output alphabets of its source occasions $S^{𝐂}={\prod }_{src(𝐂)}{A}_k$ and similarly the output alphabet of $𝐂$ as the product of the output alphabets of its target occasions $A^{𝐂}={\prod }_{trg(𝐂)}{A}_l$.

Definition 6.

The category of measuring devices ${\mathrm{𝙼𝚎𝚊𝚜}}_{𝐃}$ on $𝐃$ has objects ${\mathrm{Hom}}_{\mathrm{𝚂𝚝𝚘𝚌𝚑}}(𝒱A^{𝐂},𝒱S^{𝐂})$ for $𝐂\in {\underset{¯}{2}}^{V_{𝐃}\times V_{𝐃}}$. For ${𝐂}_1\hookrightarrow {𝐂}_2$ define arrow

$r_{21}:\mathrm{Hom}(𝒱A^{{𝐂}_2},𝒱S^{{𝐂}_2})$$\to \mathrm{Hom}(𝒱A^{{𝐂}_1},𝒱S^{{𝐂}_1})$

$\left[𝒱A^{{𝐂}_2}\stackrel{𝑇}{\to }𝒱S^{{𝐂}_2}\right]$$\mapsto \left[𝒱A^{{𝐂}_1}\stackrel{{\pi }_A^{\mathrm{♮}}}{\to }𝒱A^{{𝐂}_2}\stackrel{𝑇}{\to }𝒱S^{{𝐂}_2}\stackrel{{\pi }_S}{\to }𝒱S^{{𝐂}_1}\right],$

where ${\pi }_A$ and ${\pi }_S$ are shorthands for projectionsas in Example 1 (http://planetmath.org/2stochasticmaps#Thmeg1)

The reason for naming ${\mathrm{𝙼𝚎𝚊𝚜}}_{𝐃}$ the category of measuringdevices will become clear in §4 (http://planetmath.org/4measurement)below. The two categories are connected by contravariantfunctor $ℱ$:

Theorem 4 (structure presheaf).

The structure presheaf $\mathrm{F}$ taking

$${ℱ}_{𝐃}:{\mathrm{𝚂𝚢𝚜}}_{𝐃}^{\mathrm{𝚘𝚙}}\to {\mathrm{𝙼𝚎𝚊𝚜}}_{𝐃}:𝐂\mapsto \mathrm{Hom}(𝒱A^{𝐂},𝒱S^{𝐂})\mathit{\text{ and }}{i}_{12}\mapsto r_{21}$$

satisfies the gluing axiom but has non-unique descent.

Proof: Functor $ℱ$ is trivially a presheaf since it iscontravariant. It is an interesting presheaf becausethe gluing axiom holds.

For gluing we need to show that for any collection${\{{𝐂}_j\}}_{j=1}^l$ of subsystems and sections${𝔪}_j^{\mathrm{♮}}\in {ℱ}_{𝐃}({𝐂}_j)$ such that$r_{j,ji}({𝔪}_j^{\mathrm{♮}})=r_{i,ji}({𝔪}_i^{\mathrm{♮}})$for all $i$, $j$ there exists section ${𝔪}^{\mathrm{♮}}\in {ℱ}_{𝐃}\left({\bigcup }_{j=1}^l{𝐂}_j\right)$ such that$r_i({𝔪}^{\mathrm{♮}})={𝔪}_i^{\mathrm{♮}}$ for all $i$. This reducesto finding a conditional distribution that causes diagram

in ${\mathrm{𝙼𝚎𝚊𝚜}}_{𝐃}$ 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 similarlyfor 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 $ℱ$ to be a sheaf it would also have to satisfyunique descent: the section satisfying the gluing axiom mustnot only exist for any collection${\{{𝐂}_j\}}_{j=1}^l$ with compatible restrictions but mustalso be unique. Descent in $ℱ$ is not uniquebecause there are many distributions satisfying the requirementabove: strictly speaking $r$ is a marginalization operatorrather than restriction. For example, there are manydistributions $p(y,z)$ that marginalize to give $p(y)$ and$p(z)$ besides the product distribution $p(y)p(z)$.$\mathrm{■}$

The structure presheaf $ℱ$ depends on the graphstructure and alphabets; mechanisms play no role. We nowconstruct a family of sections of $ℱ$ using themechanisms of $𝐃$’s occasions. Specifically, given asubsystem $𝐂\in {\mathrm{𝚂𝚢𝚜}}_{𝐃}$, we show how to glue itsoccasions’ mechanisms together to form joint mechanism${𝔪}_{𝐂}$. The mechanism ${𝔪}_{𝐃}={𝔪}_{\top }$ of theentire system $𝐃$ is recovered as a special case.

In general, subsystem $𝐂$ is not isolated: it receivesinputs along edges contained in $𝐃$ but not in$𝐂$. Inputs along these edges cannot be assigned a fixedvalue since in general there is no preferred element of$A_l$. They also cannot be ignored since ${𝔪}_l$ is definedas receiving inputs from all its sources. Nevertheless, themechanism of $𝐂$ should depend on $𝐂$ alone. Wetherefore treat edges not in $𝐂$ as sources of extrinsicnoise by marginalizing with respect to the uniform distributionas in Corollary 3 (http://planetmath.org/2stochasticmaps#Thmthm3).

For each vertex $v_l\in trg(𝐂)$ let $S_l^{𝐂}={\prod }_{k\in src(l)\cap src(C)}{A}_k$. We then have projection${\pi }_l:𝒱S_l\to 𝒱S_l^{𝐂}$.Define

$${𝔪}_l^{𝐂}:=\left[𝒱S_l^{𝐂}\stackrel{{\pi }_l^{\mathrm{♮}}}{\to }𝒱S_l\stackrel{{𝔪}_l}{\to }𝒱A_l\right].$$(1)

It follows immediately that $𝐂$ is itself a distributeddynamical system defined by its graph, whose alphabets areinherited from $𝐃$ and whose mechanisms are constructedby marginalizing.

Next, we tensor the mechanisms of individual occasions and gluethem together using the diagonal map $\mathrm{\Delta }:S^{𝐂}\to {\prod }_{v_l\in trg(𝐂)}{S}_l^{𝐂}$. Thediagonal map used here generalizes$X\stackrel{\Delta }{\to }X\times X$ and removes redundancies in${\prod }_l{S}_l^{𝐂}$, which may, for example, include thesame source alphabets many times in different factors.

Let mechanism ${𝔪}_{𝐂}$ be

$${𝔪}_{𝐂}:=\left[𝒱S^{𝐂}\stackrel{{\iota }_{\mathrm{\Delta }}}{\to }\underset{v_l\in trg(𝐂)}{\otimes }𝒱S_l^{𝐂}\stackrel{{\otimes }_{v_l\in trg(𝐂)}{𝔪}_l^{𝐂}}{\to }𝒱A^{𝐂}\right].$$(2)

The dual of ${𝔪}_{𝐂}$ is

$${𝔪}_{𝐂}^{\mathrm{♮}}:=[𝒱A^{𝐂}\to 𝒱S^{𝐂}].$$(3)

Finally, we find that we have constructed a family of sectionsof $ℱ$:

Definition 7.

The quale ${𝐪}_{𝐃}$ is the family ofsections of $ℱ$ constructed inEqs. (1), (2) and(3)

$${𝐪}_{𝐃}:=\left\{{𝔪}_{𝐂}^{\mathrm{♮}}\in ℱ(𝐂)=\mathrm{Hom}(𝒱A^{𝐂},𝒱S^{𝐂})\right|𝐂\in {\mathrm{𝚂𝚢𝚜}}_{𝐃}\}.$$

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