Iterated Narrow Networks: Turing Completeness at Width 4 on Convex Input Spaces and the Complexity of Verification
Organizations: Institut Polytechnique de Paris, LIX 91128 Palaiseau, France · LISN, CNRS, Université Paris-Saclay 91190 Gif-sur-Yvette, France · Computer Science Institute BTU Cottbus-Senftenberg D-03046 Cottbus, Germany
Abstract
We study the iterates of a fixed ReLU network of width 4, that is, the discrete-time system on . Equivalently, is the output of a weight-tied network made of copies of , or of a recurrent network with no external input, started at . We prove that every deterministic Turing machine admits such a network . The network can be constructed in polynomial time from . Each iteration has depth . The iterates of simulate exactly on every encoded tape. The number of iterations is proportional to the running time of . Moreover, the fourth coordinate irreversibly flags every point of the convex cube 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 gap) is NP-complete for , 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.
Figures & tables
| mode | input domain | guarantee | width | activation | |
| Siegelmann–Sontag ( 1991 ; 1994 ; 1999 ) | recurrent | fractal | exact TM simulation | not optimized | saturated linear |
| Hanin and Sellke (2017) Park et al. (2020) | feedforward | compact | uniform approx. | to | |
| Bournez et al. (2025) , main thm. | feedforward | convex | uniform approx. of CPAMs | ||
| Bournez et al. (2025) , Thm. 23 | iterated | fractal | exact TM step; no claim off fractal | ||
| Bournez et al. (2026) | iterated | fractal + convex | -hardness via 3-SAT | , | |
| this paper, Th. 3 | iterated | convex | exact TM simulation + certificate |
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
| Activation | Conditions of Theorem 10 | Notes |
| yes | smooth on | |
| sigmoid | yes | smooth on |
| GELU | yes | smooth on |
| Swish | yes | smooth on , any |
| ELU | yes | except at ; assumption holds at any other point |
| softplus | yes | smooth on |
ReLU Neural Networks
Rectified linear unit (ReLU) neural networks use piecewise-linear activations to study approximation, learning dynamics, expressivity, and verification.
See all 136 papers