From Approximation to Computation: Universal Power of Deep Narrow Networks at Constant Width

Deep narrow neural networks underlie modern architectures from ResNets to Neural ODEs, yet their fundamental computational properties at constant width remain poorly understood. We prove that, for every deterministic Turing machine $M$, there is a single $ReLU$ network $N_M \colon [0,1]^4 \to [0,1]^4$ of width $4$ and depth $\mathrm{poly}(|M|)$, polynomial-time constructible, whose iterates simulate $M$ on every infinite binary tape encoded in a \emph{convex} initial region of $[0,1]^4$, with iteration count proportional to Turing-machine time. This establishes a tight correspondence between depth in width-$4$ networks and time on a Turing machine. The correspondence has three immediate consequences. First, verification of width-$4$ $ReLU$ networks spans the full complexity hierarchy along the single axis of depth: it is $NP$-complete for unary-encoded time bound, $NEXP$-complete for binary-encoded time bound, and $RE$-complete (undecidable) for unbounded time. Second, the hardness extends with two extra neurons of width to every common smooth activation: at width $6$, the robust verification problem (a promise problem with $\delta/2\delta$ gap) is $NP$-complete for $\tanh$, sigmoid, GELU, Swish, ELU, and any polynomial-time-computable continuous non-polynomial activation admitting a polynomial-time computable Lipschitz constant. A corollary is a discretized Neural ODE analogue at dimension 5. The simulation and statements are carried out on convex inputs, covering a regime previously inaccessible because of a continuity obstruction inherent to $\ReLU$ networks.