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

> A single width-4 iterated ReLU network can simulate any Turing machine on convex inputs, making verification NP-complete, NEXP-complete, or undecidable depending on the time bound.

- **Source:** [arXiv](https://arxiv.org/abs/2611.02840)
- **Published:** 2026-11-07
- **Permalink:** https://picx.dev/p/dqPYAy
- **Whiteboard:** https://picx.dev/p/dqPYAy/image

## Summary

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

## Summary (Overview)

- **Turing completeness at width 4**: The paper proves that iterating a single fixed ReLU network of width 4 (a recurrent network with no per-step input) can simulate any deterministic Turing machine exactly on encoded inputs, with the iteration count playing the role of time.

- **Convex input certification**: A novel "online validity certificate" (a fourth coordinate that accumulates error) resolves a fundamental continuity obstruction that previously prevented exact TM simulation on convex input regions—the regime required by practical verifiers.

- **Verification complexity spectrum**: Bounded-time reachability for iterated width-4 ReLU networks is **NP-complete** (unary time bound), **NEXP-complete** (binary time bound), and **RE-complete/undecidable** (no time bound).

- **Extension to smooth activations**: At width 6, robust verification (a promise problem with δ/2δ gap) is NP-complete for tanh, sigmoid, GELU, Swish, ELU, and any polynomial-time-computable continuous non-polynomial activation satisfying mild regularity conditions.

- **Neural ODE transfer**: The entire complexity spectrum transfers to discretized Neural ODEs in dimension 5 via the correspondence of Duan et al. [2024].

## Introduction and Theoretical Foundation

### Background and Motivation

The paper studies the discrete-time dynamical system obtained by iterating a fixed ReLU network:

$$x_{k+1} = N(x_k), \quad x_0 \in [0,1]^4$$

where $N: [0,1]^4 \to [0,1]^4$ is a feedforward ReLU network of width 4. This is equivalent to a weight-tied recurrent network with no external input, or a deep equilibrium model [Bai et al., 2019], or a discretized Neural ODE [Chen et al., 2018].

### The Continuity Obstruction

The central technical challenge is encoding a Turing machine tape (an infinite binary string) into a single real number. The authors identify why naive approaches fail:

- **Base-2 encoding fails**: $0.0\overline{1}_2 = 0.1_2$, so two different tapes can map to the same number, and reading the first bit is discontinuous.
- **Base-4 with digits {1,3}** (a device from Siegelmann and Sontag [1991]) repairs both defects: the encoding becomes injective, and leading digits are separated by a fixed gap.

However, the valid encodings form a Cantor-like set $\mathbb{DD}_{1,3}$ of measure zero, while verification problems ask about full-dimensional convex regions. The incompatibility is fundamental:

> **Proposition 11 (No continuous encoding)**: Every continuous map from a convex subset of $\mathbb{R}^n$ into $\mathbb{DD}_{1,3}$ is constant.

Since ReLU networks compute only continuous piecewise-affine maps, no subnetwork can map a convex set onto valid encodings. The paper's key innovation is a **continuous certificate**: a fourth coordinate that accumulates error, irreversibly flagging any input whose simulation reads an invalid digit.

### Key Definitions

**Definition 1 (Reachability)**: Given a ρ-network $N: [0,1]^d \to [0,1]^d$ and convex regions Init, Acc ⊆ [0,1]^d specified by rational linear inequalities, does $\exists x \in \text{Init}, \exists t \geq 0: N^{[t]}(x) \in \text{Acc}$?

**Definition 2 (Bounded-time reachability)**: Same input plus a time bound $T \in \mathbb{N}$ (unary or binary), asking whether $\exists x \in \text{Init}, \exists t \leq T: N^{[t]}(x) \in \text{Acc}$.

## Methodology

### The Encoding Scheme

A configuration $c = (u, q, v)$ (state $q$, left tape $u$ reversed, right tape $v$) is encoded as:

$$\text{enc}_M(c) = (\text{enc}_{\{1,3\}}(u), \text{enc}_M(q,v), 0, 0) \in [0,1]^4$$

where $\text{enc}_{\{1,3\}}(u) = \sum_{i=1}^{n}(2u_i + 1)4^{-i}$ maps binary words to base-4 strings using only digits {1,3}, and $\text{enc}_M(q,v)$ co-encodes the state as a constant-length prefix followed by the right tape.

### Three-Stage Network Construction

The width-4 network $N_M$ is assembled from three modular components:

**Stage 1 (Width-3 TM step)**: A width-3 ReLU network $g_M$ that simulates one TM step exactly on encoded configurations (Theorem 12, based on Bournez et al. [2025]).

**Stage 2 (Continuous validity certificate)**: A per-step error gadget:

$$\text{err}(x) = \text{ReLU}\left(3 - x - \text{ReLU}\left(5 - 2x - \text{ReLU}\left(2 - x + \text{ReLU}(1-x)\right)\right)\right)$$

This continuous piecewise-affine function vanishes exactly on $[1,2] \cup [3,4]$ and is positive elsewhere. Applied to $4x_j$, it vanishes iff the leading base-4 digit of $x_j$ lies in {1,3}.

**Stage 3 (Combination)**: Each iteration:
1. Applies the error gadget to update the certificate: $x_4' \gets \max\{x_4, \varepsilon(x_1, x_2)\}$ (computed as $a + \text{ReLU}(b-a)$)
2. Applies the width-3 TM step simulation to $(x_1, x_2, x_3)$

### Main Theorems

**Theorem 3 (Turing completeness on convex input spaces)**: For every deterministic TM M, a single polynomial-time-constructible width-4 ReLU network $N_M: [0,1]^4 \to [0,1]^4$ of depth poly(|M|) satisfies:

- **(i) Faithful simulation**: $N_M^{[C_M t]}(\text{enc}_M(c_0(\tau))) = \text{enc}_M(\text{step}_M^t(c_0(\tau)))$ for all $t \geq 0$
- **(ii) Online validity certificate**: $\pi_4(N_M^{[k]}(x))$ is non-decreasing, bounded in [0,1], and equals 0 iff all visited leading digits lie in {1,3} and the state prefix stays valid.

**Theorem 7 (Verification spectrum at width 4)**: For iterated width-4 ReLU networks, T-bounded reachability is:
- **(i)** NP-complete when T is encoded in unary
- **(ii)** NEXP-complete when T is encoded in binary  
- **(iii)** RE-complete (undecidable) with no time bound

**Theorem 10 (Robust verification at width 6)**: For any activation ρ satisfying:
- (H1) ρ is continuous and non-polynomial
- (H2) ρ is $C^1$ at some point with non-zero derivative
- (H3) ρ is polynomial-time computable with polynomial-time-computable Lipschitz constant

δ-robust verification for width-6 ρ-networks is NP-complete.

## Empirical Validation / Results

### Verification Complexity Results

The reductions follow a uniform recipe: reduce a classical TM complexity problem to width-4 reachability by constructing the network $N_M$ from Theorem 3, then defining:

$$\text{Init} = \{x \in [0,1]^4: \text{enc}_M(q_0) \leq 4^{|q|_4} x_2 \leq \text{enc}_M(q_0) + 1, x_3 = 0, x_4 = 0\}$$

$$\text{Acc} = \{x \in [0,1]^4: \text{enc}_M(q_F) \leq 4^{|q|_4} x_2 \leq \text{enc}_M(q_F) + 1, x_4 \leq 0\}$$

Both are convex, axis-aligned hyperrectangles with rational endpoints.

### Robust Verification Reduction

The reduction from ReLU to smooth activations uses a per-layer ρ-emulation lemma:

**Lemma 16 (Per-layer ρ-emulation at width k+2)**: For every ReLU-register layer R and every η > 0, there exists a ρ-network of width k+2 and depth O(1) approximating R uniformly within η on any compact set.

The proof of NP-hardness for Theorem 10 uses a robust reduction: given a width-4 ReLU instance (N, Init, R, δ), apply Lemma 17 with precision ε = δ/4 to obtain a width-6 ρ-network $\tilde{N}$ with $\sup_K \|\tilde{N} - N\|_\infty \leq \delta/4$, then output $(\tilde{N}, \text{Init}, R^{+\delta}, \delta/4)$.

**YES preservation**: If $\exists x \in \text{Init}$ with $N(x) \in R^{+\delta}$, then $\text{dist}(\tilde{N}(x), R) \leq \delta + \delta/4 = 5\delta/4$, so $\tilde{N}(x) \in (R^{+\delta})^{+\delta/4}$.

**NO preservation**: If $\forall x \in \text{Init}$, $\text{dist}(N(x), R) > 2\delta$, then $\text{dist}(\tilde{N}(x), R) > 2\delta - \delta/4 = 7\delta/4 > 3\delta/2$, so the output instance is NO.

### Position in the Literature

| | mode | input domain | guarantee | width | activation |
|---|---|---|---|---|---|
| Siegelmann–Sontag [1991, 1994, 1999] | recurrent | fractal $\mathbb{DD}_{1,3}$ | exact TM simulation | not optimized | saturated linear |
| Hanin and Sellke [2017], Park et al. [2020] | feedforward | compact $\mathbb{R}^d$ | uniform approx. | d+1 to d+4 | ReLU |
| Bournez et al. [2025], main thm. | feedforward | convex $[0,1]^d$ | uniform approx. of CPAMs | 12 | ReLU |
| Bournez et al. [2025], Thm. 23 | iterated | fractal $\mathbb{DD}_{1,3}$ | exact TM step | 3 | ReLU |
| **This paper, Th. 3** | **iterated** | **convex $[0,1]^4$** | **exact TM simulation + certificate** | **4** | **ReLU** |
| **This paper, Th. 10** | **both** | **convex $[0,1]^d$** | **robust verif. NP-c.** | **6** | **smooth ρ** |

## Theoretical and Practical Implications

### Theoretical Significance

1. **Resolving the convexity obstruction**: The paper's key theoretical contribution is showing that exact TM simulation can be extended from fractal encoding sets to full-dimensional convex regions via a continuous certificate mechanism, resolving a limitation that had previously forced either approximation (at width 12) or restricted preprocessing (3-SAT reductions).

2. **Complete complexity spectrum**: The results establish that verification complexity for narrow networks spans the entire classical hierarchy along the time-bound axis, from NP to NEXP to undecidable—demonstrating that width restriction alone does not restore tractability.

3. **Width-efficiency**: Width 4 suffices for the full spectrum, and width 6 for smooth activations. This is remarkably narrow compared to prior constructions.

4. **Robust verification is not easier**: The δ/2δ promise gap—the standard remedy for transcendental constraints in smooth activation verification—does not restore tractability.

### Practical Implications

- **Certification cost scales with depth, not width**: The practical reading is that verification cost scales along the number of steps (depth), not width. This is consistent with empirical observations that depth dominates the cost of complete verifiers like Marabou and α,β-CROWN.

- **Closed-loop verification**: For neural controllers where reachable sets over k control steps are exactly $N^{[k]}(\text{Init})$, the results imply fundamental computational barriers.

- **Neural ODEs**: The transfer to dimension-5 discretized Neural ODEs extends the hardness to continuous-depth models.

## Conclusion

### Main Takeaways

The paper establishes that iterated width-4 ReLU networks are Turing complete on convex input regions, with a novel continuous certificate mechanism that resolves a fundamental continuity obstruction. The verification complexity spans NP → NEXP → undecidable along the time-bound axis, and the hardness extends to all common smooth activations at width 6 in the robust verification framework.

### Open Problems

1. **Width 2**: Width 1 admits polynomial-time verification; widths 3-4 are NP-complete (via fractal preprocessing); width 4 gives the full spectrum; width 2 is open.

2. **Continuous-time simulation**: Whether a Lipschitz piecewise-affine ODE admits TM simulation by its continuous flow (not just discretization) remains open.

3. **Constrained networks**: Non-expansive iterates (spectral norm ≤ 1, as in deep equilibrium models) cannot create digit resolution; the authors conjecture that bounded-time reachability leaves the NEXP/RE regime under such constraints.

4. **Beyond piecewise-affine activations**: Extending to softmax, attention, and Transformer-style architectures is a natural direction.

The paper's central message is that **depth, not width, is the axis along which verification cost scales superpolynomially**—a result with both theoretical depth and practical significance for the neural network verification community.

---

_Markdown view of https://picx.dev/p/dqPYAy, served by PicX — AI-generated visual whiteboard summaries of research papers._