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 [\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 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 $t-1$ and $t$ respectively for some $t$, so occasions form a directed graph. More generally:

Definition 4.

A distributed dynamical system $𝐃$ consists of the following data:

1. Directed graph. A graph $G_{𝐃}=(V_{𝐃},E_{𝐃})$ with a finite set of vertices or occasions $V_{𝐃}=\{v_1\mathrm{\dots }{v}_n\}$ and edges $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 distributed dynamical 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) 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{𝚂𝚢𝚜}}_{𝐃}$ of $𝐃$ is a Boolean lattice with objects given by sets of ordered pairs of vertices $𝐂\in {\underset{¯}{2}}^{V_{𝐃}\times V_{𝐃}}$ and arrows given by inclusions $i_{12}:{𝐂}_1\hookrightarrow {𝐂}_2$. The initial and terminal objects 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 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(𝐂)=\{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 projections as in Example 1 (http://planetmath.org/2stochasticmaps#Thmeg1)

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

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 is contravariant. It is an interesting presheaf because the 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 reduces to 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 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 $ℱ$ 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 ${\{{𝐂}_j\}}_{j=1}^l$ with compatible restrictions but must also be unique. Descent in $ℱ$ 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{■}$

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

In general, subsystem $𝐂$ is not isolated: it receives inputs along edges contained in $𝐃$ but not in $𝐂$. 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 ${𝔪}_l$ is defined as receiving inputs from all its sources. Nevertheless, the mechanism of $𝐂$ should depend on $𝐂$ alone. We therefore treat edges not in $𝐂$ 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(𝐂)$ 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 distributed dynamical system defined by its graph, whose alphabets are inherited from $𝐃$ 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^{𝐂}\to {\prod }_{v_l\in trg(𝐂)}{S}_l^{𝐂}$. The diagonal map used here generalizes $X\stackrel{\Delta }{\to }X\times X$ and removes redundancies in ${\prod }_l{S}_l^{𝐂}$, which may, for example, include the same 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 sections of $ℱ$:

Definition 7.

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

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

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.