Fully Spiking Neural Implementation of Lambda-Calculus Beta-Reduction via Biologically Documented Mechanisms
Organizations: Moscow Center for Advanced Studies, 20 Kulakova Str., 123592 Moscow, Russia · Neurotechnology Department, Institute of Biology and Biomedicine, Lobachevsky State University of Nizhny Novgorod, Gagarin Avenue 23, 603022 Nizhny Novgorod, Russia
Abstract
We present the first complete implementation of -reduction in the untyped -calculus using exclusively spiking neural dynamics. Every step of the reduction---redex detection, subterm segmentation, variable-binding detection, DeBruijn index arithmetic, token copying, and inter-step role maintenance---is performed by leaky integrate-and-fire (LIF) neurons with explicit membrane dynamics, exponential synaptic currents, axonal delays, and pair-based spike-timing-dependent plasticity (STDP). Each neural component maps onto a specific, experimentally documented mechanism: Jeffress-type delay-line coincidence for redex detection; a line-attractor balance counter for subterm segmentation; -- cross-frequency coupling for DeBruijn variable binding; a phase-ring traveling wave for depth-index arithmetic; theta-cycle STDP for token copying; and recurrent persistent firing for role maintenance between reduction steps. All synaptic weights are derived analytically from measured EPSP amplitudes; no hand tuning is performed. The closed-loop system achieves 100,% agreement with a symbolic oracle across ten validation classes, including Church numeral arithmetic (plus, mult, pred), Boolean logic with divergent branches, Y-combinator steps, terms with up to six bound-variable occurrences, DeBruijn indices up to12, noise robustness, and determinism. To our knowledge this is the first Turing-complete symbolic computation performed entirely within spike dynamics using biologically grounded circuit primitives. We discuss implications for neuromorphic proof assistants and the neural basis of symbolic reasoning.
Figures & tables
| Parameter | Value | Role | Derivation |
|---|---|---|---|
| 0.1 ms | Simulation step | Standard LIF precision | |
| 8 ms | SCAN inter-token interval | Axonal delay budget | |
| 9.0 | WM / PERSIST recurrent | ||
| 2.4 | DET coincidence AND | ||
| 291 | Balance integrator | ||
| 20.0 | WTA latch | Sufficient to suppress DET |
| Component | Biological mechanism | Primary reference |
|---|---|---|
| Working memory | Recurrent self-sustaining firing | Goldman-Rakic [34] |
| SCAN delay-line | Theta-sequence sweep | Foster and Wilson [59] |
| Redex detector | Jeffress delay-line coincidence | Jeffress [44] |
| WTA latch | PV + lateral inhibition | Kremkow et al. [46] |
| Balance integrator | Oculomotor line attractor | Seung [53] |
| ARG_MODE | Entorhinal persistent firing | Egorov et al. [38] |
| Block | Terms | Description | Match |
| 1 | 6 | Church arithmetic: plus 2 3, mult 2 3, pred 3 etc. | 6/6 |
| 2 | 10 | Boolean logic: and , or , not , if-then-else with -branches | 10/10 |
| 3 | 3 | Y-combinator: divergence of ; step-by-step cube comparison (3 steps) | 3/3 steps |
| 4 | 7 | Bound-variable stress: , mixed KEEP/BOUND body | 7/7 |
| 5 | 5 | Deep nesting: up to 25 s, De Bruijn index 12 | 5/5 |
| 6 | 4 | Head normal form: (diverges), inner redexes | 4/4 |
Neuro-Symbolic Reasoning
Neuro-symbolic reasoning combines learned neural models with explicit logic, rules, knowledge structures, or executable tools to solve structured tasks.
See all 295 papers