The Assembly Calculus (Papadimitriou et al., PNAS 2020) proposes that brain computation reduces to a small set of operations on neural ensembles. Each operation is biologically plausible — it requires only Hebbian plasticity, sparse coding, and winner-take-all competition. Together, they are sufficient for universal computation. This page explains the operations, the convergence guarantees that make them reliable, and the extensions that make them Turing-complete.
What an assembly is
A brain area contains n neurons. At each timestep, exactly k of them — the winners of a competition based on total synaptic input. An assembly is the stable set of k neurons that wins repeatedly when a particular stimulus is presented. It is an attractor in the sense of Hopfield (1982): the network converges to it from many initial conditions and stays there under perturbation. The sparse coding principle — only k out of n neurons active — follows Olshausen & Field (1996): sparse representations are efficient, interpretable, and resistant to interference.
The ratio k/n determines the sparsity. Typical parameter values across the papers: n = 105 neurons per area, k = √n ≈ 317 or k = 500 winners, connectivity probability p = 0.01–0.1 (Erdős–Rényi random graph between areas), and plasticity rate β = 0.05–0.1. The k-cap operation selects the k neurons with the largest total synaptic input; Hebbian plasticity then strengthens the connections to those winners by a factor of (1 + β). An assembly in the network is a dynamic attractor — it can strengthen with repeated activation or if competing stimuli recruit its neurons. When we measure an assembly, we record a snapshot: the set of k winners at that moment. Overlap between two such snapshots — the fraction of shared neurons — is the natural similarity metric.
The operations
Projection
The most fundamental operation: create a stable representation of a stimulus (or source assembly) in a target brain area. The source drives synaptic input into the target. In the first round, the winners are essentially random — whichever k neurons happen to receive the most input. But Hebbian plasticity strengthens the connections to those winners, so in the next round, the same neurons win again, more strongly. After O(log n) rounds, the winners stabilize: consecutive rounds produce assemblies with >95% overlap. A new assembly has formed — a stable representation of the source now exists in the target area, encoded by a different set of neurons but carrying the same information.
We have validated this experimentally: 100% convergence rate across all tested configurations, with a mean of 2.4 steps to stability. Convergence time decreases with network size (R² = 0.989) — larger brains form assemblies faster, because more neurons means more competition and sharper winners.
Association
Link two assemblies through a shared target. The protocol has three phases: project assembly A into the target, project assembly B into the target, then project both simultaneously. The result: the assemblies in the target area overlap, representing the conjunction of A and B. This is how the brain might bind two concepts — “red” and “apple” become associated through shared neural substrate, not through a symbolic link table.
Merge
Combine two assemblies into a new one representing their relationship. Unlike association (which creates overlap in a shared target), merge produces a conjunctive representation that encodes the structure of the composition: “cat” + “runs” → a merged assembly representing the proposition the cat runs, not just the union of the two concepts. This is the operation that enables syntactic composition — the foundation of the language processing pipeline.
Sequence memorize and ordered recall
Dabagia et al. (2023) extended the calculus with two temporal operations. Sequence memorize learns an ordered sequence of assemblies via Hebbian bridges between consecutive steps — the activation of assembly Ai strengthens connections to Ai+1. Ordered recall replays the sequence from a cue using long-range inhibition (LRI): recently-fired neurons are suppressed so the network advances to the next assembly instead of back to the current one.
LRI has two parameters: the refractory period (how many past timesteps of firing history to track) and inhibition strength (a dimensionless multiplier on the suppression of recently-fired neurons). With refractory period 3 and inhibition strength ≥100, recall is reliable. These operations enable FSM simulation and, combined with the base calculus, achieve Turing completeness — assembly circuits can simulate any computation a digital computer can, using only biologically plausible mechanisms.
Why competition is essential
The single most important experimental finding about assemblies: without competition, they do not work. When we train assemblies for different stimuli in separate brains (independent random initialization, no shared inhibition), the resulting assemblies overlap by 94% — they are effectively indistinguishable, because both settle into the same high-input neurons by chance. When we train both stimuli in the same brain with winner-take-all , overlap drops to 3%. The assemblies become distinct representations.
This is not a parameter tuning result. It is a structural finding: lateral inhibition is the mechanism that forces neural populations to differentiate. Without it, Hebbian plasticity drives everything toward the same attractor. With it, competition carves out non-overlapping regions of representational space. This has implications beyond the Assembly Calculus — it suggests that any neural model claiming biological plausibility must include competitive dynamics, not just learning rules.
Convergence and scaling
The theory predicts that projection converges in O(log N) rounds, where N is the number of neurons. Our experiments confirm this with high precision:
| Property | Result |
|---|---|
| Convergence rate | 100% (all configurations) |
| Mean steps to stability | 2.375 |
| Scaling law | O(log N), R² = 0.989 |
| Effect of network size | Convergence faster at larger N |
| Convergence time range | 2–6 steps across all tested sizes |
The counter-intuitive result — larger networks converge faster — has a clean explanation: more neurons means sharper competition (the gap between the k-th and (k+1)-th largest inputs grows), which means Hebbian plasticity has a clearer signal to reinforce. The attractor basin is deeper when the network is larger.
Turing completeness
Dabagia et al. (2023) proved that the Assembly Calculus with sequences and long-range inhibition is Turing-complete. The construction: any finite state machine can be simulated by a sequence of assemblies where each state is an assembly and transitions are Hebbian bridges between them. Long-range inhibition ensures the system advances through the state sequence rather than oscillating. Because new assemblies can be created dynamically (providing unbounded memory), the FSM simulation extends to full Turing machine simulation.
This is a theoretical result with practical implications. It means that the biologically plausible mechanisms in the Assembly Calculus are not just sufficient for pattern recognition or associative memory — they are sufficient for any computation. The open question is efficiency: a Turing machine simulation via assemblies is possible but may be astronomically slower than a direct implementation. The Turing-machine simulation is a proof of power, not the practical payoff. The payoff is that the operations it provides (projection, merge, sequence) map naturally onto the kinds of computation the brain actually performs — language, planning, memory — with no general-purpose simulation in between.