Beta-reduction in the untyped lambda calculus now runs on spiking neurons, matching a symbolic oracle across ten validation classes
Synopsis
Beta-reduction in the untyped lambda calculus has until now been carried out by symbolic engines, or represented by neural components that hand the rewriting to an external interpreter. This closed-loop reducer assigns redex detection, subterm segmentation, variable-binding detection, De Bruijn index arithmetic, token copying and inter-step role maintenance to leaky integrate-and-fire neurons with membrane dynamics, synaptic currents, axonal delays and spike-timing plasticity, and agrees with a symbolic oracle across ten validation classes.
Interpretation
Every step of beta-reduction is now performed by spike dynamics, with no symbolic engine rewriting terms outside the circuit. Earlier neural implementations either encoded compositional structure in activation patterns while an external symbolic interpreter applied the rewriting rules, or used rate-coded population vectors for vector arithmetic and associative memory, which is not a reduction strategy for a formal calculus. The closed-loop system agrees with a symbolic oracle across ten validation classes, covering Church numeral arithmetic, Boolean logic with divergent branches, Y-combinator steps, up to six bound-variable occurrences, deep nesting with De Bruijn indices up to 12, noise robustness and determinism.
Each sub-operation maps onto a documented neural mechanism rather than borrowing a biological label. Redex detection uses Jeffress-type delay-line coincidence, subterm segmentation an oculomotor-style line-attractor balance counter, variable binding theta–gamma phase coincidence, depth-index arithmetic a phase-ring traveling wave, token copying theta-cycle spike-timing plasticity, and inter-step role maintenance recurrent persistent firing. All synaptic weights are derived analytically from measured excitatory postsynaptic potential amplitudes through a single calibration, with no hand tuning or gradient optimization; validation runs on randomly generated terms, combinators and Church numeral arithmetic.
Perspective
The demonstrated scope is leftmost-outermost reduction on closed lambda terms, with test terms ranging from a few to roughly a dozen tokens and each reduction step taking hundreds of milliseconds in simulation.
Open terms with free variables fail the encode-decode round trip, because a free variable's binding channel is zero and cannot be distinguished from a bound variable at depth zero; the system performs beta-reduction only, not eta-reduction, and lacks the sharing mechanism lazy evaluation would need; the neuron count for nested substitution grows quadratically with term size in the worst case.
