Iterated Narrow Networks: Turing Completeness at Width 4 on Convex Input Spaces and the Complexity of Verification

AI summary

Overview

• Research area: Machine learning theory — specifically computational complexity and expressivity of narrow ReLU networks, recurrent/iterated networks, neural network verification, and Neural ODEs.
• Technical level: Advanced (the paper assumes familiarity with Turing machines, complexity classes such as NP / NEXP / RE, and neural network verification problems).
• Scope: The paper proves that iterating a single fixed ReLU network of width 4 on the convex cube [0,1]^4 is Turing complete via an online validity certificate in a fourth coordinate, and derives a full reachability complexity spectrum (NP / NEXP / RE), extensions to width 6 smooth activations, and a transfer to discretized Neural ODEs in dimension 5.

What This Paper Is About

The paper asks what a very narrow network can compute when the same block is applied over and over — the discrete-time system x_{k+1} = N(x_k) on [0,1]^4, where N is a ReLU network of width 4. Prior exact simulations of Turing machines by ReLU networks worked only on a fractal, measure-zero set of encodings, so they could not be used to reason about verification queries posed over convex input regions, which is the regime real verifiers operate in. The goal is to bridge that gap and use it to classify how hard it is to verify the behavior of these networks.

Key Contributions

1. Turing completeness at width 4 on convex input spaces (Theorem 3). For every deterministic Turing machine M over the binary alphabet, a single width-4 ReLU network N_M on [0,1]^4 is constructible in polynomial time from M, with per-iteration depth poly(|M|), whose iterates simulate M exactly on encoded tapes, with iteration count proportional to M's running time.
2. An online, continuous validity certificate (part (ii) of Theorem 3, Proposition 13). The fourth coordinate is non-decreasing, stays in [0,1], and flags — irreversibly — every point of the convex cube whose simulation reads an invalid base-4 digit or leaves the set of valid state prefixes. This is what makes hardness reductions sound on convex regions.
3. A verification spectrum at fixed width 4 (Theorem 7). Bounded-time reachability is NP-complete for a unary time bound, NEXP-complete for a binary time bound, and RE-complete (undecidable) with no bound, with hardness holding even for axis-aligned hyperrectangles with rational endpoints. A corollary (Corollary 8) gives NP-completeness of verification for feedforward width-4 ReLU networks.
4. Extension to smooth activations at width 6 (Theorem 10) and to Neural ODEs at dimension 5 (Theorem 50). Adding two neurons of width extends NP-completeness of δ-robust verification to tanh, sigmoid, GELU, Swish, ELU, softplus, arctan, the Gaussian, leaky ReLU, and any polynomial-time-computable continuous non-polynomial activation with a polynomial-time-computable Lipschitz constant; via the correspondence of Duan et al. (2024), the spectrum transfers to discretized Neural ODEs in dimension 5.

Main Findings

• Width 4 is enough for exact Turing-machine simulation on a full-dimensional convex cube. The network has width 4, per-iteration depth poly(|M|), and simulates M on every encoded tape; with a universal machine U, a single fixed block N_U simulates every machine on every input.
• Exactness, not approximation, is forced. Each simulated tape shift multiplies a coordinate by 4, so a per-step error ε grows to roughly 4^k ε after k iterations; since the NEXP and undecidability results quantify over exponential and unbounded k with one fixed finite network, no approximation-based construction can reach them.
• A continuity obstruction rules out continuous encoding (Proposition 11). Every continuous map from a convex subset of R^n into the Cantor-like digit set DD_{1,3} is constant, because convex sets are connected and DD_{1,3} is totally disconnected; since ReLU networks compute only continuous piecewise-affine maps, no subnetwork can map a convex region onto valid encodings. The paper's answer is to detect invalid inputs online rather than encode them.
• The certificate gadget is explicit and simple. The per-step error function err vanishes exactly on [1,2] ∪ [3,4] and is positive elsewhere, implemented by a nested ReLU expression of constant depth inside the width-4 register network; the certificate update is x_4' ← max{x_4, ε(x_1,x_2)}, computed as a + ReLU(b − a) at width 2.
• A single fixed block suffices for the hardness ladder. The reductions for all three parts of Theorem 7 use the identical recipe: Init pins the initial-state prefix of x_2 and sets the scratch and validity registers to 0, Acc pins the final-state prefix, and the trajectory enters Acc exactly when the simulation stayed valid and M accepted within the time bound.
• The spectrum spans the full hierarchy along one axis. Relaxing only the time bound climbs PTIME → NP → NEXP → undecidable at fixed width 4; restricting the width does not restore tractability, since width 4 already suffices.
• The paper does not claim a width lower bound for the certificate property. Width 3 already suffices for exact simulation alone (Theorem 12, due to Bournez et al., 2025); width 4 is stated as the price of combining exact simulation with the online certificate, with no lower bound claimed for the pair.

Methodology in Plain English

The authors build a simulation in three modular stages. First, they borrow a known width-3 subnetwork that performs one Turing-machine step exactly, provided the input lies on a special set of encodings written in base 4 using only the digits 1 and 3 — a choice that makes the encoding injective and separates adjacent digits by a fixed gap, unlike base 2 or unrestricted base 4, where two different tapes can denote the same number and reading the first digit is discontinuous. Second, they add a small continuous gadget that measures whether the leading base-4 digit being read is valid; this gadget is zero exactly on the allowed digit ranges. Third, they wire the gadget to a fourth coordinate that accumulates the maximum of all errors seen so far, so that any input which was never a valid encoding is flagged and stays flagged.

The check runs before the simulation step reads a digit, so while the flag is zero the simulator provably never touches a forbidden digit. Because this certificate is continuous and defined over the whole cube [0,1]^4 — not just the fractal encoding set — the network can be plugged into standard verification queries over convex initial and target regions. The authors then reduce known Turing-machine complexity problems (acceptance within a unary-bounded time, Succinct-TM-Acceptance with binary bounds, and the halting problem) to reachability in these networks. For smooth activations, the argument is carried out at width 6 with a tolerance-based promise problem (a δ/2δ gap) so that transcendental constraints do not arise, and finally transferred to Neural ODEs through an existing discrete-to-continuous correspondence.

Why This Matters

Impact on research. The results separate expressivity from width: hardness does not vanish as networks get narrower, so tractability can only come from restricting the dynamics, the parameters, or the time horizon. The paper also supplies a new construction primitive — a continuous, online certificate of encoding validity — that replaces the fractal-domain assumptions of Siegelmann–Sontag-style results (Siegelmann and Sontag, 1991; 1994; Siegelmann, 1999) and of the width-3 and width-12 results in Bournez et al. (2025), and complements the companion work Bournez et al. (2026), which obtains NP-hardness at widths 3 and 4 via 3-SAT preprocessing plus #P/PP corollaries on the fractal encoding set (the only overlap is Corollary 8). It also extends the known NP-hardness of ReLU verification (Katz et al., 2017) to the full NP/NEXP/RE spectrum, and complements work on how sequential steps buy expressive power (Merrill and Sabharwal, 2024).

Real-world applications implied by the paper's framing:

• Robustness certification. An ℓ∞ ball around a data point is an axis-aligned box, i.e. a convex polytope; deciding whether some input in that box is misclassified is exactly the reachability query studied, in the VNN-LIB / VNN-COMP specification format (Brix et al., 2023) used by complete verifiers such as Reluplex, Marabou and α,β-CROWN.
• Closed-loop neural controller verification. The reachable set after k control steps is exactly N^{[k]}(Init), which is the iterated model analyzed here.
• Deep equilibrium models and weight-tied recurrent networks (Bai et al., 2019), where one block is iterated to a fixed point.
• Discretized Neural ODEs (Chen et al., 2018; Kidger, 2022), where the dimension-5 transfer applies.

Industry relevance. The practical reading the authors state is that certification cost scales along depth, or number of steps, and not along width — so deploying extremely narrow but repeatedly applied networks offers no free lunch for formal verification, and verification tooling must plan for NP-, NEXP-, or undecidability-level worst cases depending on how the time bound is specified.

Future Directions

• A width lower bound for the simulation-plus-certificate pair. The paper explicitly claims no lower bound for the combination of properties (i) and (ii) that width 4 achieves, leaving open whether width 4 is optimal.
• Reconciling the convex and fractal regimes. Since Proposition 11 forbids any continuous map from a convex set into DD_{1,3}, the open question is whether other constructions (beyond the online certificate) can make exact simulation sound on convex regions at still lower width.
• Extending beyond the stated activation class. Theorem 10 covers activations satisfying (H1)–(H3); activations outside that class — for instance those lacking polynomial-time-computable Lipschitz constants on bounded intervals — are not covered.
• Sharper complexity classifications for verification in practice. The hardness results hold for axis-aligned hyperrectangles with rational endpoints, but the paper does not report algorithmic results or empirical evaluation, so the gap between these worst cases and the behavior of deployed verifiers remains to be characterized.

Target Audience

Researchers in machine learning theory and computational complexity, particularly those working on expressivity and verification of neural networks; theorists interested in analog computation, recurrent networks, deep equilibrium models, and Neural ODEs; and verification practitioners who need to understand the worst-case complexity of certifying narrow but iterated network architectures. The paper is not suitable as an introductory read — it presumes comfort with Turing machines, reduction-based complexity arguments, and the neural network verification problem formulation.

Authors’ abstract

We study the iterates of a fixed ReLU network $N$ of width 4, that is, the discrete-time system $x_{k+1} = N(x_k)$ on $[0,1]^4$. Equivalently, $x_k$ is the output of a weight-tied network made of $k$ copies of $N$, or of a recurrent network with no external input, started at $x_0$. We prove that every deterministic Turing machine $M$ admits such a network $N_M$. The network can be constructed in polynomial time from $M$. Each iteration has depth $\mathrm{poly}(|M|)$. The iterates of $N_M$ simulate $M$ exactly on every encoded tape. The number of iterations is proportional to the running time of $M$. Moreover, the fourth coordinate irreversibly flags every point of the convex cube $[0,1]^4$ whose simulation reads an invalid digit. This flag is the certificate that makes hardness reductions sound on convex input regions, the regime of practical verifiers. Convex regions were previously inaccessible because of a continuity obstruction inherent to ReLU networks. The correspondence has three consequences. First, reachability for iterated width-4 ReLU networks spans the full complexity hierarchy along the single axis of the time bound: it is NP-complete for a unary bound, NEXP-complete for a binary bound and RE-complete (undecidable) with no bound. Second, two extra neurons of width suffice to extend the hardness to every common smooth activation: at width 6, the robust verification problem (a promise problem with $δ/2δ$ gap) is NP-complete for $\tanh$, sigmoid, GELU, Swish, ELU, and any polynomial-time-computable continuous non-polynomial activation with a polynomial-time-computable Lipschitz constant. Third, the whole spectrum transfers to discretized Neural ODEs in dimension 5.