arXiv:2604.24356cs.CCcs.LG2026-04

用动态系统统一解释神经网络、微分方程与多项式映射的计算能力。

Primitive Recursion without Composition: Dynamical Characterizations, from Neural Networks to Polynomial ODEs

  • 通过原始递归框架,三类连续动力系统可等价实现相同计算
  • 时间上界为原始递归,无需复合规则,输入为整数向量
  • 适合研究子递归层次与复杂度类的动态建模,对神经形态计算有启发

递归神经网络、多项式微分方程与离散多项式映射均在连续空间(实值状态)中演化,即使目标函数为离散。本文通过原始递归研究三者:证明它们可等价表征同一类计算——通过固定结构的ReLU网络迭代、固定多项式微分方程鲁棒计算、或带外部步长参数的固定多项式映射迭代。所有情形的时间边界本身是原始递归的,复合关系由动态过程自然生成而非人为定义,输入为原始整数向量。每个函数先编译为阈值仿射规范形式的有界迭代,再转化为神经网络或微分方程。等价性揭示结构不对称性:任意固定多项式映射无法统一取整或精确相位选择——而这些正是多项式微分方程通过连续流稳健实现的。每种模型弥补其他缺失的能力:ReLU门提供精确分支,连续时间实现自主取整与控制,步长参数可恢复两者但牺牲离散精度。该框架可用于通过限制时间界、多项式次数或离散资源来刻画子递归层次与复杂度类。更广泛地,这些模型不依赖子程序组合,而是通过时钟、相位选择器和误差校正机制塑造系统轨迹。这与符号编程结构不同,本定理为此差异提供了精确分析框架。

原文摘要 · Abstract (English)

What do recurrent neural networks, polynomial ODEs, and discrete polynomial maps each bring to computation, and what do they lack? All three operate over the continuum--real-valued states evolved by real-valued dynamics--even when the target functions are discrete. We study them through primitive recursion. We prove that primitive recursion admits equivalent characterizations in all three frameworks: bounded iteration of a fixed recurrent ReLU network, robust computation by a fixed polynomial ODE, and iteration of a fixed polynomial map with an externally supplied step-size parameter. In each, the time bound is itself primitive recursive, composition emerges from the dynamics rather than as a closure rule, and inputs are raw integer vectors. Every primitive recursive function is first compiled into bounded iteration of a single threshold-affine normal form, then interpreted as a ReLU computation and as a polynomial ODE. The equivalences expose a structural asymmetry: no fixed polynomial map can round uniformly to the nearest integer or realize exact phase selection--operations polynomial ODEs perform robustly via continuous-time flow. Each formalism compensates for a limitation the others lack: the ReLU gate provides exact branching, continuous time provides autonomous rounding and control, and the step-size parameter recovers both at the cost of discretization precision. This opens dynamical characterizations of subrecursive hierarchies and complexity classes by restricting time bounds, polynomial degrees, or discretization resources within one framework. More broadly, these models do not compute by composing subroutines: they shape the trajectory of a dynamical system through clocks, phase selectors, and error correction built into the dynamics. This differs structurally from symbolic programming, and our theorem gives a precise framework to study the difference.

神经网络微分方程计算理论动态系统

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。