Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers

1 Introduction

• Approximation constructions may rely on infinite-precision weights or activations, or exponentially many parameters, making expressivity guarantees less meaningful.For finite-width, finite-precision RNNs, streaming lower bounds preclude Turing-machine simulation.Source: §1 · pp. 1–2
• Statistically meaningful approximation requires an approximating family with good statistical learnability, addressing whether a target can be fit from finite training data rather than merely represented.It studies sample complexity while leaving optimization concerns possible.Source: §1 · p. 2
• Feedforward networks SM-approximate Boolean circuits with sample complexity polynomial in circuit size, while transformers SM-approximate bounded-time Turing machines with complexity polynomial in alphabet and state-space sizes and log(T).For the transformer construction, the paper reports loglog(T) precision, compared with at least log(T) in prior work, yielding an exponential sample-complexity improvement.Source: §1 · p. 2

1.1 Related works

• Prior formal-language results show Turing completeness using arbitrary precision, while finite-precision language results do not analyze Turing machines or statistical properties of their constructions.Concurrent finite-precision RNN work uses dynamically growing memory but does not analyze statistical properties.Source: §1.1 · p. 3

1.2 Notation

• The notation section defines composition, asymptotic shorthand, and expected n-sample Rademacher complexity for later statements.It uses rO to hide poly-logarithmic factors and poly(·) to denote a polynomial in the argument.Source: §1.2 · p. 3

2 Statistically meaningful approximation

• Classical approximation requires a close function in the approximating class, but that alone does not ensure finite-sample fitting or a good sample complexity.The concern includes solutions that rely on infinite precision or other unrealistic characteristics.Source: §2 · pp. 3–4
• SM approximation requires a surrogate loss whose empirical risk minimizer over the approximating family achieves low population approximation error from a finite sample.The definition measures sample complexity by the number of examples needed to guarantee ε approximation error.Source: §2 · p. 4
• Unlike PAC learnability, SM approximation combines expressivity with generalization by also requiring the best function in the approximating family to achieve near-zero loss.PAC-learning focuses on learnability, or in the agnostic case, low loss relative to the best hypothesis.Source: §2 · p. 4

2.1 Background and tools

• A surrogate that upper-bounds the target loss, has low Rademacher complexity, and is small for some approximator yields an SM-approximation guarantee.The surrogate and evaluation losses may differ, and the surrogate can include regularization.Source: §2.1 · p. 4, §2 · p. 4
• The all-layer-margin surrogate connects classification margins to generalization; the paper’s bound applies when an approximator has a sufficiently large all-layer margin.The parameter-space margin formulation accounts for weight sharing, which matters for the Turing-machine results.Source: §2.1 · p. 5

3 SM approximation of Boolean circuits with feedforward nets

• The theorem gives feedforward networks an SM approximation bound polynomial in circuit size and only logarithmic in network width, under the stated width, norm, and depth conditions.The guarantee holds for every positive approximation error and any input distribution over the Boolean input domain.Source: §3 · p. 6
• The all-layer margin loss is essential: alternative surrogate losses yield weaker bounds, including polynomial dependence on overparameterized width or depth-sensitive norm bounds.The output-margin ramp-loss bounds depend on products of operator norms, which are exponentially large in depth for the naive construction.Source: §3 · p. 6

3.1 Proof sketch for Theorem 3.1

• A layered circuit is simulated by composing ReLU networks that compute its gate layers, preserving the circuit's outputs on Boolean inputs.The circuit model uses AND, OR, NOT, and identity gates; each transition maps one layer's gate values to the next.Source: §3 · p. 5, §3.1 · p. 6
• Correction functions between layers preserve the computed function while giving the resulting network an all-layer margin of at least 1/poly(s) on every Boolean input.The proof adds only a constant-factor increase in depth; the correction functions can be implemented with two activation and linear layers.Source: §3.1 · p. 7

4 SM approximation of Turing machines with transformers

• Polynomial in log(T), state-space size, and alphabet size is the sample-complexity dependence for transformers SM-approximating Turing machines bounded by T steps.The paper contrasts this with prior constructions whose bounds depend at least linearly on T.Source: §4 · p. 8

4.1 Transformer architecture for SM-approximating Turing machines

• The encoder embeds each input symbol with a learnable symbol embedding plus a fixed positional encoding, while the decoder produces outputs over T steps.The decoder output at one timestep is fed into the next timestep.Source: §4.1 · pp. 8–9

4.2 Proof sketch for Theorem 4.1

• Binary encodings of timestep indices use ceil(log(T)) bits, avoiding prior positional values as small as 1/poly(T) that could undermine the all-layer margin.The construction uses decoder self-attention to search past timesteps by binary search, requiring O(r log(T)) layers, and encoder-decoder attention to copy an input symbol when no prior timestep wrote to that tape location.Source: §4.2 · pp. 9–10
• Each decoder representation maintains the machine state, symbol under the head, and head location, then applies the transition function to compute the next state, written symbol, and head movement.The construction retrieves a tape symbol from the most recent prior write, the input, or otherwise the blank symbol.Source: §4.2 · p. 10

5 Conclusion

• Statistically meaningful approximation requires an approximating family to have sufficient expressivity and good statistical learnability.The paper proposes this definition to provide more meaningful guarantees.Source: §5 · p. 10
• The paper shows that Boolean circuits and Turing machines can be approximated with sample-complexity guarantees depending on intrinsic properties of those function classes.Source: §5 · p. 10
• The paper identifies proving further bounds for other target functions and architectures, and comparing architectures through this definition, as future directions.Source: §5 · p. 10

A Proofs for Section 2

• The empirical risk minimizer has population loss bounded using uniform deviations between population and empirical risks, controlled by Rademacher complexity.The proof compares the empirical minimizer with a function whose population loss is at most epsilon, then uses a surrogate loss that upper-bounds the target loss.Source: A Proofs for Section 2 · p. 15
• The loss-class covering number is bounded through parameter-space covering numbers, and a Dudley entropy integral yields a Rademacher-complexity bound used to solve for sample size.Source: A Proofs for Section 2 · p. 15
• The appendix states a parameter-space all-layer-margin generalization corollary for classifiers achieving zero training loss.It follows by substituting the covering-number bound into a result from [56].Source: A Proofs for Section 2 · pp. 15–16

B Proofs for Section 3

• A two-layer neural network can implement each circuit layer with parameter 1-norm O(r_i), using simple ReLU constructions for AND and OR gates.The construction also handles identity and NOT gates and pads the representation to the network width.Source: B Proofs for Section 3 · pp. 16–17
• The proof simulates each circuit layer with two feedforward ReLU layers, then inserts correction functions that round perturbed outputs back to binary values.The correction layers increase depth by only a constant factor and yield a margin bound tied to individual-layer Lipschitz constants.Source: B Proofs for Section 3 · p. 16
• Polynomial-in-circuit-width Lipschitzness parameters yield an all-layer margin lower bound of 1/poly(s), which is used to obtain the approximation guarantee.Source: B Proofs for Section 3 · p. 16

• The transformer simulates a fixed machine from an input-on-tape configuration and loops in its terminal state until computation time T.Source: §C.1 · p. 17
• Position embeddings use binary encodings of timestep indices with effective dimension wpos = ceil(log2 T).Source: §C.1 · p. 17
• Hidden coordinates are grouped to store state, symbols, positions, and scratch information, with overparameterized coordinates set to zero.Source: §C.1 · p. 17
• At each step, the decoder output embedding maintains the machine state, tape symbol, and head position.Source: §C.1 · p. 18

C.2 Completing the proof

• Two feedforward ReLU layers encode the next state-symbol pair q_i(x) as one-hot, preserve required coordinates, and have parameter norm O(|Z||A|+w_pos).The construction selects the state-symbol pair and maps it to the machine output for that pair.Source: §C.2 · p. 18
• O(w_pos) feedforward ReLU layers update the head-position encoding by binary addition or subtraction, producing Bin(l_i(x)) with parameter norm O(w_pos(|Z|+|A|+w_pos)).The movement bits determine whether the previous position is decreased or increased by one.Source: §C.2 · p. 19
• O(w_pos) self-attention/linear layers binary-search for the latest prior matching head position i1, then attend to i1 to copy u_i1(x), with parameter norm O(w_pos(|Z|+|A|+w_pos)).The binary search reveals one bit of i1 per attention layer.Source: §C.2 · pp. 19–21
• A single decoder self-attention layer tests whether a matching prior timestep exists, with parameter norm O(w_pos), to initialize the binary search.When no matching timestep exists, attention selects the null position.Source: §C.2 · p. 20
• In the stated setting, a function f is realized by a single encoder-decoder attention layer; it is zero at all other coordinates, with parameter norm O(|A|+w_pos).This completes step 4 in Section 4.2 using encoder-decoder attention.Source: §C.2 · p. 23
• Composing layers for the five outlined operations produces a one-hot encoding of the machine’s state, which a classifier maps to the desired accept-or-reject output.Correction functions are inserted between layer groups, and the constructed transformer outputs 2G(x) − 1.Source: §C.2 · p. 25
• The construction is converted to the fixed transformer architecture by replacing unused modules with identities, padding to width w, and appending identity layers to reach depth d.These changes preserve the parameter-norm bounds, and the correction functions can be placed in the final two feedforward layers of each transformer layer.Source: §C.2 · p. 25
• The generalization analysis treats the transformer as a depth-O(T log T) network with layer-based weight sharing; Theorem D.6’s margin bound does not depend on depth.The intermediate layers are sparse binary vectors with at most |Z| + |A| + log T nonzero entries, satisfying Condition D.4 for polynomial λ.Source: §C.2 · p. 25
• For valid inputs, the all-layer margin is at least on the order of 1/poly(|Z|, |A|, log T); applying Lemma 2.4 with γ at that scale and parameter 1-norms bounded by α gives the desired result.Source: §C.2 · p. 26
• Attention choices remain stable under inverse-polynomial perturbations because the largest score exceeds the second largest by 1, except where tied positions have identical value vectors.This supports polynomial Lipschitz and distance bounds for Condition D.3 and the resulting inverse-polynomial all-layer margin.Source: §C.2 · p. 26

• Correction functions repair hidden-state errors within radius σζ, enabling a model with potentially small all-layer margin to have a larger margin.Source: D All-layer margin lower bounds via… · p. 26
• The argument assumes standard Lipschitzness-based layer conditions and bounded layer norms, with the margin bound expressed through their constants.Source: D All-layer margin lower bounds via… · p. 27
• Theorem D.6 bounds all-layer margin by combining layerwise perturbation tolerances, and the bound also holds for valid layer-based weight sharing.Source: D All-layer margin lower bounds via… · p. 27
• If bounded parameter perturbations keep output change below 1, the model’s ±1 output sign is preserved, yielding a margin lower bound from the minimum perturbation threshold.Source: D All-layer margin lower bounds via… · pp. 27, 28, 30