q-bio.NCNov 17, 2026

Fully Spiking Neural Implementation of Lambda-Calculus Beta-Reduction via Biologically Documented Mechanisms

Authors: Vladimir A. Lazovskiy, Victor B. Kazantsev, Sergey V. Stasenko

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

Explore similar work

CardsList
  1. Plug-and-Play Spiking Operators: Breaking the Nonlinearity Bottleneck in Spiking Transformers

    May 19, 2026Xinzhe Yuan, Xiang Peng, Bin Gu +1Spiking TransformersSpiking Neural Networks

  2. Rethinking the Tradeoff Between Temporal Encoding and Nonlinear Computation in Spiking Language Models

    Oct 7, 2026Hanfei Liu, Shuchang Feng, Yanxia Chen +2Spiking Language ModelsLanguage Modeling