Chapter 30
A Network That Learns by Rewriting
The four preceding chapters built learners at four sizes: the individual with its budget, the game it plays, the composite that a population of individuals is, and the enzyme that individuates one from another. Each was argued at the scale where the argument is interesting and none was small enough to watch run.
This chapter is the small one. It takes the graded where-clause of Chapter 14 and points it at the smallest system in which the whole apparatus is visible at once — rate constants, multiplicity, plasticity, and the funding gate — and what comes out is a spiking neural network with learning in it. The network is not an analogy and it is not an encoding. It is what Equation (14.2) computes when the theory is a handful of for-comprehensions, each carrying a clause.
The reason it belongs in this part rather than beside the construction is the last of those four factors. A neuron here has an energy budget, because the funding gate of Proposition 14.2 applies to it like anything else, and a neuron whose local supply is exhausted is silent regardless of how strong its synapses are. Weight is what a synapse is worth; cost is what a spike costs. That a strong synapse on a starving neuron transmits nothing is a statement neither decoration makes alone, and it is the mortal computation of Chapter 26 arriving at a scale where one can count the tokens.
30.1 The design decision that makes the example an example
One can always model a neural network in a process calculus by writing the arithmetic into the payloads: send a real number down a channel, multiply it by a stored weight, sum, squash, forward. Nothing in Chapter 14 would be doing any work; the calculus would be a programming language and the network a program written in it.
We do the opposite. The synaptic efficacies are not arithmetic in the payloads. Each is the value of the graded clause on the synapse’s receipt. In one sentence:
Synaptic efficacy is represented as transition intensity in the operational semantics, and the same transition updates that intensity.
There is a subtlety in “not in the payloads” that the earlier form of this chapter, written for weight maps, did not have to face, and it is best faced at once. A weight map kept the efficacies in a table beside the term. A clause has no table; by Remark 14.10, whatever a clause’s value depends on must be in the term, so a plastic efficacy must be written down somewhere a clause can read it. We write it as a datum on a channel of its own — a weight register — and the clause reads it. That is not the arithmetic-in-the-payload design in disguise. The register holds a number, but the number is never added to anything or passed through a function written in the term; it is read by the clause and becomes a rate. The difference between a term that computes with a weight and a term that is weighed by one is the whole design decision, and the clause is what lets the second be said.
Three consequences follow, and the third is the one the chapter exists for. Firing is a stochastic event rather than an arithmetic one. The network’s response nonlinearity is a property of the chain rather than a function written down anywhere. And synaptic plasticity is a rewrite of the weight register performed by the same firing that reads it, so that a network which learns and a network which infers are the same graded theory running the same transition relation.
It is worth being careful about what the object is, since the temptation to overname it is strong. It is an asynchronous stochastic spiking recurrent network with plastic transition rates. It is not a recurrent neural network in the machine-learning sense: there is no backpropagation, no membrane potential, no refractory period, no global clock and no discrete timestep, and the quantity compared below with a textbook neuron’s pre-activation is a hazard rate rather than an affine form awaiting an activation function. Nothing in the argument needs the stronger name, and the claim it does support is the more interesting one.
30.2 Neurons are persistent for-comprehensions
Let neuron \(i\) have presynaptic channels \(a_{1i}, \ldots, a_{k_i i}\) — its dendrites — and postsynaptic targets \(\mathrm{post}(i)\). Its threshold presentation at \(\theta_i\) is the persistent for-comprehension \[N_i \;\triangleq\; \texttt{for}\bigl(\, \underbrace{x_{s_1} \Leftarrow a_{s_1 i} \;\&\; \cdots \;\&\; x_{s_\theta} \Leftarrow a_{s_\theta i}} _{\text{one group per }\theta_i\text{-subset } S} \;;\; \cdots \,\bigr) \;\bigl\{\; \textstyle\prod_{j \in \mathrm{post}(i)} a_{ij}!(\mathrm{spk}) \;\bigr\},\] with one join group per \(\theta_i\)-element subset of the dendrites, \(\&\) joining within a group and \(;\) separating groups. The network is \(\mathsf{Net} \triangleq \texttt{new}\ \vec{a}\ \texttt{in}\ \{\prod_i N_i \mid M_0\}\), with \(M_0\) an initial multiset of pending spikes.
Three points, in increasing order of importance.
The receipts are persistent. A linear receipt evaporates after one firing, so a network built from linear receipts models a single sweep and not a network. Persistence is what makes the object a standing structure rather than a trace through one. The pending spikes are still consumed per firing; it is the neuron that survives. (Chapter 14 took the linear receipt as its default and noted that persistence is harmless where a surviving receipt distinguishes no candidate; that is the case here, since the receipt is the same whichever spike it consumes.)
Recurrence is not an additional construct. It is the statement that some \(a_{ij}\) for \(j \in \mathrm{post}(i)\) feeds a dendrite of a neuron from which \(i\) is reachable, \(i\) itself included. The unrolled network in the machine-learning sense is the reduction graph; the hidden state at a given moment is the marking, the standing multiset of pending spikes on the restricted channels. Since the marking is part of the term and the weight registers are part of the term, hidden state and weights are carried by one object and that object is the term. That is Remark 14.10 paying for itself: there is no configuration beside the term because the term is the configuration.
And the threshold is in the join structure.
30.2.1 The clauses
For each synapse \((j,i)\) let \(w_{ji}\) be a channel — the weight register of the synapse — carrying exactly one datum, a value in a finite set \(\{0, \eta, 2\eta, \ldots, w_{\max}\}\). The receipt on dendrite \(a_{ji}\) in Definition 30.1 carries the clause \[\psi_{ji} \;\triangleq\; \bigoplus_{k=0}^{w_{\max}/\eta} \; k\eta \;\tensorv\; \crisp{\,w_{ji}\ \text{carries}\ k\,},\] over \(\Semi = \Rnn\): the value of the clause at a candidate is the number in the register.
\(\psi_{ji}\) is a graded clause in normal form (Theorem 14.4), its crisp subformulae are structural of depth \(2\), and it is evaluated by one lookup in the bag.
The indicators \(\crisp{w_{ji}\ \text{carries}\ k}\) for distinct \(k\) are exclusive, since the register holds one datum, and exhaustive over the finite value set; so the clause is a sum over a partition, which is the normal form. Each indicator is “an output on \(w_{ji}\) with payload \(k\)”, a structural formula of depth \(2\) checked by lookup.
The value \(\sem{\psi_{ji}}\) is the efficacy of synapse \((j,i)\). Nothing else in the presentation does arithmetic with it. The register is quantized and bounded for a reason the chapter returns to in Section 30.4: it is what makes the clause a finite sum, and finiteness is what the complex instance of Chapter 39 required of the earlier construction in another form.
30.2.2 Threshold is join structure
The threshold presentation of Definition 30.1 realizes the monotone Boolean threshold function “at least \(\theta_i\) of the dendrites carry a pending spike”. It uses \(\binom{k_i}{\theta_i}\) join groups.
A group is enabled exactly when every channel it binds carries a spike, since \(\&\) requires simultaneous availability of all its binds; the receipt is enabled exactly when some group is, since \(;\) separates alternatives. Some \(\theta_i\)-subset is fully populated exactly when at least \(\theta_i\) dendrites are.
So the historical origin of the neuron model — McCulloch and Pitts’ threshold unit [35] — is not encoded in a weighted theory but is a for-comprehension, with the threshold appearing as the arity of the joins and the alternatives as the group separator. The qualification “expressivity lemma” is not cosmetic: \(\binom{k}{\theta}\) groups is unusable at realistic fan-in, so the scalable presentation is the one at \(\theta = 1\), where threshold behavior is trivial and the join structure carries no weight. What the lemma establishes is that no apparatus beyond the for-comprehension is needed to express a threshold. What it does not establish is that this is how one would build a large network.
\(\theta_i = k_i\) gives a pure coincidence detector: the neuron fires only on simultaneous arrival at every dendrite. \(\theta_i = 1\) gives a pure rate integrator: any arrival can trigger it, and the weights determine how fast. Real cortical neurons sit between, and so does the presentation, with \(\theta\) as the dial. This is a rare case in which a biological parameter and a syntactic parameter are the same parameter.
30.3 The weighted sum, and where the squashing function went
Take \(\theta_i = 1\), so \(N_i\) has \(k_i\) single-bind alternatives, and let the marking assign \(m_{ji}\) pending spikes to dendrite \(a_{ji}\).
With every redex funded, the total rate of the candidates belonging to neuron \(i\) is \[\prop_i \;=\; \sum_j \sem{\psi_{ji}} \cdot m_{ji} .\]
The receipt is persistent, so exactly one pattern is available on each \(a_{ji}\), and the marking supplies \(m_{ji}\) datum occurrences; by Definition 14.12 there are therefore \(m_{ji}\) candidates at the site, one per occurrence, and each evaluates the clause to the same value \(\sem{\psi_{ji}}\), since the clause reads the register and not the spike. Equation (14.2) sums them, giving \(\sem{\psi_{ji}}m_{ji}\) per synapse, and distinct synapses are distinct sites.
Formally this is the weighted sum \(\sum_j w_{ji}m_{ji}\) of the textbook artificial neuron, with presynaptic activity read as the marking — and it has not been written into any term. It is what the clause language computes when candidates are counted by occurrence, which is the multiplicity factor of Chapter 14 doing its one job.
The comparison should nevertheless be made carefully, because the two quantities are not the same kind of thing. \(\prop_i\) is a hazard rate, with units of inverse time, governing a race between exponential clocks. It is not an affine pre-activation waiting to be passed through an activation function. What the next result shows is that a saturating nonlinearity nevertheless appears, and appears without being supplied.
Hold the marking on \(i\)’s dendrites fixed over a window \([0,\Delta]\). The probability that neuron \(i\) fires at least once in the window is \[\Pr[\,i \text{ fires}\,] \;=\; 1 - \exp\bigl(-\Delta \textstyle\sum_j \dec(\varphi_{ji})m_{ji}\bigr),\] a monotone function of the weighted sum, with slope \(\Delta\) at the origin and asymptote \(1\).
Under a marking held fixed the propensity \(\prop_i\) is constant, so firings of \(i\) within the window are the events of a homogeneous Poisson process of rate \(\prop_i\): the chain is on terms (Remark 14.10), and along the sub-chain where the marking on \(i\)’s dendrites and the registers do not change, the clauses do not change. The probability of at least one event in \([0,\Delta]\) is \(1 - e^{-\prop_i \Delta}\).
Two provisos, one standard and one easy to miss. The standard one is that the marking is not in fact frozen, since other neurons are firing into it; the corollary is a statement about a window short enough that the input has not moved, which is the usual justification for a rate-coded neuron and the usual approximation. The one easy to miss is that \(i\)’s own firings change the marking, since a firing consumes the spike it fired on. The hypothesis must be read as freezing the marking against all sources of change, \(i\)’s own consumption included, which is why the statement is about the first event rather than about a count.
\(1 - e^{-\Delta x}\) is an exponential saturation function and not the logistic \(\sigma(x) = (1+e^{-x})^{-1}\); the distinction is worth keeping because the claim is worth as much either way and should be stated exactly. A saturating nonlinear activation emerges from exponential race semantics without being programmed into the term. No squashing function was supplied and none is needed. A neuron under enormous drive still cannot fire more than once per event, so its firing probability per window is bounded by \(1\) however large the weighted sum grows, and that bound is the waiting-time law of the chain rather than a modeling choice.
30.3.1 Boundedness
Let \(f_i = |\mathrm{post}(i)|\) be the fan-out of neuron \(i\). If \(f_i \leq \theta_i\) for every \(i\), the total number of pending spikes is non-increasing along every run and the reachable term set is finite.
Firing \(N_i\) consumes \(\theta_i\) pending spikes, one per bind in the selected group, and produces \(f_i\), so the total marking changes by \(f_i - \theta_i \leq 0\). The neurons are persistent and the channel set is fixed, so a reachable term is determined by its marking, and markings with at most \(|M_0|\) tokens over finitely many channels are finite in number.
The hypothesis forbids fan-out exceeding threshold, which most networks want. The repair we take is a capacity guard: bound the occupancy of a target channel after the firing, which is a saturating synapse and is what a real one does. The marking is then bounded per channel and the reachable state space is finite unconditionally. It matters that the bound is read after the firing rather than before; the obvious alternative, refusing a send when the target is already full, blocks the consumer and deadlocks the network. The other standard repair — a leak rule discarding a pending spike at its own rate — does not bound the state space but makes the marking positive-recurrent, which is enough for stationary analysis and for classical simulation.
30.4 Plasticity is a rewrite of the register
Let the receipt on dendrite \(a_{ji}\) also bind the register: it consumes the datum \(k\) on \(w_{ji}\) along with the spike on \(a_{ji}\), and its continuation re-emits \(w_{ji}!(\min\{w_{\max},\ k + \eta\})\) together with the outgoing spikes. The clause \(\psi_{ji}\) is unchanged.
So the firing that transmits is the firing that potentiates, and nothing new has been added to the calculus to say so: a join that consumes two data and re-emits one of them incremented is an ordinary for-comprehension. This is Proposition 14.3 in the flesh. The weight map’s version of this chapter needed an update function on a table, a closure with no compilable form; the clause’s version needs a rewrite that the language already had.
The ceiling is not cosmetic. With a quantized increment it is what makes the register’s value set finite, hence the clause a finite normal form, hence the reachable term set finite once the marking is bounded — and it is a case where a modeling convenience and a mathematical necessity happen to be the same stipulation.
The transition relation of the graded theory on terms has two marginals: the projection to markings is the network’s inference dynamics, and the projection to registers is its learning dynamics. Neither is a separate process. In particular there is no training schedule, no separate learning clock and no distinguished learning phase, and the learning rate \(\eta\) is not a hyperparameter of an outer loop but a constant in the continuation of the receipt whose clause it modifies.
Immediate from Definition 30.3: a single firing consumes a spike and a register value and emits spikes and a register value, so one step moves both marginals, and no step moves one without the other being available to move.
This is the claim the chapter exists to make, and it is exactly what a static-rate calculus cannot express. In the Stochastic Pi Machine a rate is fixed at declaration, so a stochastic \(\pi\) model of a neural network can model the firing but not the learning: one must step outside the calculus, adjust the rates, and re-run. Here the adjustment is a transition of the same system. Theorem 14.2 says precisely which restriction is being lifted.
Definition 30.3 potentiates \(\varphi_{ji}\) when a communication on \(a_{ji}\) fires — that is, when a presynaptic spike is consumed by an enabled postsynaptic receipt. The event is local and activity-dependent, and the condition “pre and post were jointly involved” is not a correlation computed by an observer but the firing of a single rewrite, which by construction requires both parties. That much is the structural content of Hebb’s proposal [36], and it is the part worth having: the event which transmits is the event which potentiates, because a communication is one rewrite.
It is nevertheless less than Hebbian learning as usually meant. Hebbian plasticity invokes a correlation between pre- and postsynaptic firing, and successful transmission into an enabled receipt is not by itself postsynaptic firing, since the receiving neuron may not reach threshold. What we have is a minimal local potentiation rule, and the timing-dependent version costs something specific.
Spike-timing-dependent plasticity makes the weight change a function of the interval between pre- and postsynaptic spikes [37]. The clause cannot see an interval, because an interval is not in the term; this is exactly the hypothesis of Proposition 14.3 failing, and Remark 14.10 says what to do. Write down what the interval depends on: one eligibility register per synapse, holding a decaying trace, decremented by a leak rule at its own rate and reset by the firing. The potentiation continuation then reads two registers instead of one, and the clause is unchanged. The chain remains a chain on terms provided the eligibility register takes finitely many values, which a quantized decay guarantees. What does not survive is a weight change that depends on unbounded history, which no finite register can hold and which would make the process non-Markovian on any state space; the eligibility-trace formulation is precisely the standard device for staying inside the bounded case, and it is pleasant that the constraint arrives here from the requirement that the state be a term rather than from computational convenience.
30.5 Uniformity: one theory for every network
Definition 30.2 gives one key per synapse, so a network with \(10^4\) synapses has \(10^4\) keys and a network that grows needs a new theory. Reflection removes both problems. Take the synapse channels to be structured names built from the network’s own name and the two endpoint indices, so that a name predicate can recover the endpoints. Then \[\varphi_{\mathrm{syn}} \;\triangleq\; \exists j, i.\ \text{a communication redex on the synapse channel of } (j,i)\] is a single crisp formula describing the whole namespace of this network’s synapses, which is namespace logic doing what it was built for [39]. One clause then serves every synapse: it recovers \((j,i)\) from the channel, names the register \(w_{ji}\) by the same structure, and reads it. The theory has one for-comprehension schema per network rather than one per synapse, and per-synapse efficacies live where they always did, in the registers — the standard move of trading a large table for a small clause over structured names.
The point generalizes well beyond bookkeeping, and it is the reason this chapter sits in this part of the book. A namespace is the computationally coherent notion of scope (Chapter 20), and what the reflective calculus buys here is that a population of synapses can be priced by one formula because the population is a nameable thing. In an atomic-name calculus none of this is available: the indices would have to travel as message payloads, and the logic could reach them only by observing traffic. This is the same manoeuvre by which Chapter 28 takes a learner to be a weighted population and hence a namespace, run at the scale of a synapse instead of the scale of a scientific community.
30.6 The complex instance, and an honest negative
Replace the efficacies by amplitudes, keeping the clauses, the neurons and the capacity bound. The example is finite in every respect the complex instance of Chapter 39 asks about: the capacity bound makes the marking finite and the ceiling \(w_{\max}\) with a quantized increment makes the registers finite, so the reachable term set is finite and the state space is finite-dimensional.
\(m\) indistinguishable pending spikes on \(a_{ji}\) give \(m\) candidates with a common outcome. It is tempting to conclude that the quantum network is superlinear in presynaptic multiplicity, transmitting at \(m^2\) times the single-spike rate where the classical network transmits at \(m\) times. It is not, and the reason is now a sentence about the clause rather than about a normalization chosen to prevent it: \(\psi_{ji}\) reads the register and not the spike, so every one of the \(m\) candidates carries the same amplitude, and the clause is in normal form (Theorem 14.4). A clause in normal form distinguishes no two candidates of one class, and Chapter 39 says that cancellation becomes available exactly when a clause leaves normal form. This one does not, so the \(m\) amplitudes add to \(m\) times one amplitude, the squared modulus is \(m^2\) times the single-spike probability only if the \(m\) candidates are alternatives, and they are not: they share a receipt, so they lie in one contention component whose matchings are the \(m\) ways of choosing a spike, and the completion of Proposition 39.2 normalizes over them. The network transmits at the classical rate.
What the complex reading would add, on either view of Chapter 39’s Section 39.5, is coherence somewhere this presentation does not put it: a clause that distinguishes candidates, or an equation withheld from the quotient. Definition 30.1 does neither. As written, complexifying it adds nothing at all. This is worth stating plainly because it is a negative instance of both views, and a construction whose negative instances are never displayed is not doing any work. It also names what would have to be done: write a synaptic clause that gives different spikes different phases — which is to say, a synapse that cares which spike it received — and then ask whether the result is in the quantum-safe fragment. We have not done it, and we do not claim that concurrency supplies it for free.
30.7 What this example does not show
The learning here is local. Nothing above implements backpropagation, which needs a global error signal propagated against the direction of inference. One can encode such a signal as traffic on a second family of channels with its own keys, and the apparatus does not forbid it, but the result would no longer have the property that makes Theorem 30.1 interesting — the error channel is an outer loop wearing a costume. Whether a genuinely local learning rule of this kind can match backpropagation is not a question answered here, and the honest statement is that the example demonstrates a mechanism for plasticity inside the calculus, not a competitive learning algorithm.
Nor is biological fidelity claimed. The neuron of Definition 30.1 has no membrane potential, no refractory period and no dendritic geometry. The first two are easy additions — a potential is a register, a refractory period is a crisp conjunct in the clause — and the third is what the geometric factor of Remark 14.4 is for, which is a use we have not developed.
What the example does show is worth restating against the four chapters that precede it. Those chapters argued that a learner is a population with a budget, that its inquiry terminates because assays are paid for, and that a community of such learners composes. This one exhibits the same architecture at a scale where every quantity is countable: the population is a marking, the budget is a funding gate, the inquiry is a race between exponential clocks, and the learning is the same relation as the inference. It is the smallest thing in this book that is recognisably a mind-shaped object, and nothing in it was put there by hand except the rules.