PaperlayerView exact revision on arXiv

Source-linked AI summary

Interpretability for Turing Machines

Billy Snikkers, Rumi Salazar, Daniel Murfet, Will Troiani

arXiv:2609.04661v1cs.LGcs.FLstat.ML

TL;DR

The paper asks whether local loss geometry can reveal algorithmic structure in Turing machines, then adapts susceptibilities to noisy Turing-machine models to probe that geometry. It proves that path separation and recoding symmetries induce low-rank blocks and permutation symmetries in susceptibility matrices, and finds corresponding structure empirically in DFA susceptibility space.

  • Problem

    The paper addresses whether the internal structure of a learned Turing-machine program is encoded in the local geometry of its loss and can be made explicit.

  • Method

    The paper adapts susceptibilities to noisy Turing machines and arranges component responses across inputs into susceptibility matrices.

  • Results

    Path separation yields susceptibility blocks of rank at most 2, while machine recoding symmetries yield corresponding permutation symmetries in susceptibility matrices.

  • Takeaways & Limitations

    Algorithmic features such as path separation and recoding symmetry can be recovered from susceptibility space using rank analysis, principal components, and clustering of DFA solutions.

  • Takeaways & Limitations

    The experiments use µ = 0, where smoothness and criticality do not hold, although the paper states these properties are not required by its theorems.

Abstract

from arXiv · show

We show that susceptibilities, an interpretability technique developed for neural networks, can identify the presence of algorithmic structure in Turing machines by probing the local loss landscape of a learning problem for noisy Turing machines introduced by Murfet and Troiani (arXiv:2504.08075). We prove that symmetries and path separation in the algorithm implemented by a Turing machine induce permutation symmetries and low-rank blocks in its susceptibility matrix. We study this empirically on a set of deterministic finite automata (DFAs) and demonstrate that algorithmic features can be recovered by principal component analysis and clustering methods in susceptibility space.

1 Introduction

The paper studies how algorithmic structure in Turing machines is encoded in the local geometry of a loss function and recovered through susceptibilities. It proves that recoding symmetries and path separation induce corresponding structure in susceptibility matrices, then tests these relationships on DFAs.

  • Motivation and method: The noisy-machine framework replaces deterministic transition entries with probability distributions, producing output distributions after a fixed number of simulation steps.These distributions model error channels affecting the description tape, while a smooth relaxed step function propagates the resulting uncertainty.
  • Motivation and method: Susceptibilities probe the local geometry around classical Turing-machine solutions, where higher-order information can matter in singular models.The method adapts susceptibility theory from neural networks to noisy Turing machines and organizes component responses into a susceptibility matrix.
  • Path separation: Path separation makes certain susceptibility blocks have rank ≤2 when non-initial states separately route accepted and rejected inputs to constant final states.For the studied DFAs, numerical estimates agree with this bound, and the rank conditions characterize path separability.
  • Empirical analysis: Principal-component projections and clustering organize DFAs according to algorithmic features such as path separability and recoding symmetry.The examples distinguish path-separable and non-path-separable machines, while asymmetry measurements provide visual evidence that the observed reflection is caused by recoding.
  • Recoding symmetries: Recoding symmetries of a Turing machine induce permutation symmetries of its susceptibility matrix under invariance assumptions on the dynamics, input distribution, and prior.In the DFA experiments, recoding exchanges susceptibility blocks and appears as a reflection in principal-component space, with fixed-point machines on the symmetry axis.
  • Additional contributions: The paper also develops a circuit calculus for noisy computations and gives a singular example where susceptibilities probe structure unavailable to the Hessian.These are presented as minor contributions alongside the main symmetry and low-rank results.

2 Noisy Turing machines

The noisy Turing-machine framework embeds machine codes and configurations into probability simplices, then smoothly relaxes execution so uncertainty propagates through a pseudo-UTM. This supplies the parameterized model used to define losses and susceptibilities.

  • Classical machines: A Turing machine is represented by a transition code assigning write symbol, next state, and movement direction to each symbol-state pair.The code space varies transition functions while fixing the tape alphabet and state set.
  • Execution: The classical configuration update writes a symbol, changes state, and shifts the tape relative to a head kept at position 0.Left, stay, and right moves are represented by head-relative tape shifts rather than by tracking an explicit head position.
  • Pseudo-UTMs: A pseudo-UTM loads the machine code onto auxiliary tape squares and the simulated configuration onto working and state tapes.The code layout maps each symbol-state pair to three auxiliary squares, while other auxiliary contents are fixed.
  • Noisy parameter space: Noisy machines replace each transition entry with probability distributions over symbols, states, and directions.Simulation for a fixed number of steps therefore produces a distribution over final states or outputs.
  • Smooth relaxation: A smooth relaxation of the pseudo-UTM step induces a smooth cycle map that preserves the code while smoothly updating the working and state configuration.At classical codes and configurations, the relaxed dynamics reduce to ordinary execution.
  • Learning setup: The truth-model-prior triple uses a finite input set, target final states, an input distribution, a time horizon, and the noisy-machine parameter space.This instantiates the general truth-model-prior framework for noisy Turing-machine learning.
  • Scope and assumptions: The experiments use µ = 0 even though the resulting loss lacks smoothness and criticality at the relevant point.The paper states that these properties are not needed by the Section 4 theorems.

3 Structures in Turing machines

The paper formalizes path separation and recoding symmetries as algorithmic structures in Turing machines, then illustrates them in a family of DFAs. These structures distinguish accepting and rejecting computation paths and organize equivalent symbols, states, and machine components.

  • Path separation partitions: Path separation partitions divide noninitial states into accepting and rejecting regions, requiring each corresponding classical run to remain in its correct region.The partition contains qacc in the accepting region and qrej in the rejecting region.
  • Path separation partitions: The path separation violation measures the q-weighted fraction of intermediate computation steps spent in the wrong region.Its minimum is obtained by minimizing over admissible partitions.
  • Path separation partitions: For a classical solution, a partition is path-separating exactly when its path separation violation is zero.This equivalence follows because all summands are nonnegative and the input distribution has full support.
  • Recoding symmetries: A recoding is a pair of bijections on alphabet symbols and states, fixing the blank and distinguished initial, accepting, and rejecting states.The alphabet map must preserve the input set under symbolwise extension.
  • Recoding symmetries: A recoding symmetry fixes the machine code under conjugation, and all such symmetries form the automorphism group Aut(M).The paper also defines an asymmetry measure that vanishes for a symmetry and implies equivariance of the target map for classical solutions.
  • DFA examples: The running examples are five five-state DFAs deciding one finite-alphabet language, with varying path-separation partitions and recoding symmetries.The DFA family is read-only and always moves right, so its state function determines the machine.

4 Theorems

The theorems connect algorithmic structures to susceptibility-matrix structure under compatibility assumptions on the smoothly relaxed universal Turing machine. Path separation yields low-rank off-diagonal blocks, while recoding symmetry yields equivariance and a group action on the loss singularity germ.

  • Path separation: Path separation partitions the susceptibility matrix into input-region blocks, including off-diagonal blocks pairing each input class with the opposite state region.The relevant blocks are Xacc,R and Xrej,A.
  • Path separation: Unmatched-component invariance means that perturbations outside the components used by a simulated transition do not affect its result.The assumption is satisfied by the staged and lookup smooth relaxations cited in the paper.
  • Path separation: Under unmatched-component invariance, the off-diagonal susceptibility blocks have bounded rank because each column is a linear combination of two vectors.This is the mechanism used in Theorem 4.5.
  • Compatibility assumptions: The paper notes that recoding equivariance depends on the smooth relaxation: the lookup pseudo-UTM satisfies it, whereas the staged pseudo-UTM violates it.The violation arises because the staged relaxation depends on tuple order, which recodings permute.
  • Recoding symmetry: For a machine recoding symmetry, recoding-equivariant dynamics and invariant input distribution and prior make the susceptibility matrix equivariant.The theorem assumes both q(g · x) = q(x) and φ(g · w) = φ(w).
  • Recoding symmetry: The same hypotheses endow the loss singularity germ at the machine code with an action of the cyclic group generated by the symmetry, or more generally a subgroup of Aut(M).The action restricts to bijections of the zero set fixing the classical code.

5 Experiments

Experiments show that estimated susceptibilities recover DFA symmetries, path separation, and algorithmic organisation through matrix block structure, principal components, and clustering. These patterns agree with the theoretical predictions and remain visible despite sampling and UTM-related approximations.

  • Symmetry: M1, M4, and M5 exhibit susceptibility matrices approximately invariant under permutations induced by the alphabet involution A ↔0, B ↔1.The observed permutation symmetry reflects intrinsic transition-function symmetries of these machines.
  • Interpretation: Across the solution set, susceptibility embeddings recover transition rules, halting times, asymmetries, and path-separation violations from estimated susceptibilities alone.The experiments use 38,019 canonical DFA solutions and recover these features through PCA, clustering, rank statistics, and symmetry analyses.
  • Clustering: Path-separable machines form a distinct susceptibility cluster, organised further by expected halting time and recovered by PCA, UMAP, and linear classification.The path-separable class is defined by PSVmin = 0 and is the most consistently observed partition across experiments.
  • Symmetry: The leading susceptibility eigenmatrices transform predictably under recodings, with distinct eigenvalue ratios and recoding-dependent symmetry defects.For example, λ1/λ2 = 1.82 and λ2/λ3 = 1.10, while the leading eigenmatrices have defects determined by the recoding.
  • Symmetry: Susceptibility-space distances between machines and their recodings are small, with median distances 0.06 and 0.07 compared with a random-pair median of 1.42.These distances support the interpretation that susceptibility geometry records recoding symmetries.
  • Rank statistics: Every path-separable machine satisfies the predicted off-diagonal rank bound, while rank violations identify most non-path-separable machines in the tested partitions.Theorem 4.5 holds without exception for path-separable machines; in one partition, Xacc,R exceeds rank 2 for 99.8% of machines with PSV(M; A, R) > 0.

A.5 Invariance and equivariance of the cycle maps

The lookup pseudo-UTM’s smooth relaxation is invariant under unmatched-component changes and equivariant under recodings. These properties follow from how lookup matching reindexes components and propagates mixtures.

  • Invariance: The staged and lookup pseudo-UTM smooth relaxations are unmatched-component invariant.Changing a component that cannot match the simulated read pair leaves the one-period output unchanged.
  • Equivariance: The lookup pseudo-UTM is recoding equivariant.Its cycle map therefore supports the permutation-symmetry argument for susceptibility matrices.
  • Interpretation: On deterministic codes, simulating the machine and then relaxing agrees with relaxing the machine’s own step.This is the smooth-relaxation-preserving property noted for the lookup UTM.
  • Equivariance: Recodings act by reindexing input pairs and pushing forward symbols and states, with inverse maps cancelling under the reindexing.This establishes compatibility between recoded configurations and the lookup cycle map.

B Details of the experiments

The experiments test whether the theoretical susceptibility properties persist under empirical estimation and alternative loss treatments. The appendix also documents the sampling and calibration procedures used for those experiments.

  • Experimental details: The experimental appendix checks rank bounds and equivariance under log-loss, justifies the Dirichlet localiser, and analyzes renormalized susceptibilities.It also describes the GRLD sampler and its calibration.

B.1 Reparametrising the loss preserves the rank bound and the equivariance

The rank bound and equivariance survive replacing squared error with a broad class of input-independent loss reparametrizations, including the unshifted log-loss used experimentally. Renormalized susceptibilities converge as the smoothing shift tends to zero, while α < 1 creates a divergence in localized slice evaluations.

  • Loss reparametrization: The rank proof remains valid after replacing squared error by any fixed post-composition of the error probability, including log-loss.Off-diagonal columns remain linear combinations of the expectation vector and the constant vector, yielding rank ≤2.
  • Loss reparametrization: Equivariance also survives input-independent reparametrization of the loss.The proof uses only properties preserved when the error probability is post-composed with a fixed function.
  • Log-loss: The unshifted log-loss is smooth on [0, 1) and infinite at 1, but its infinite-loss set has measure zero and the relevant expectations remain finite.The appendix therefore applies the preceding arguments unchanged to the experimental log-loss.
  • Renormalization: As µ →0, the shifted Gibbs distributions converge to their µ = 0 limits, and the renormalized susceptibility converges to its unshifted value.The convergence follows for the expectations entering the renormalized susceptibility.

B.2 Properties of the localiser and the estimator

The localiser concentrates noisy machines near a classical solution, while cancellation and standardisation make susceptibility estimation well-defined and preserve the structural results. Recoding equivariance transfers to susceptibility representations, and path-separation rank bounds persist for estimated matrices.

  • Localiser: The Dirichlet localiser concentrates probability near the classical machine, making susceptibility reflect M rather than the entire model class.It uses a Dirichlet family over simplex-valued machine descriptions, with concentration controlled by the classical value and γ.
  • Localiser: For α < 1, the uncancelled localiser contains divergent vertex factors, so the paper defines the slice distribution using its cancelled form.The cancelled form is proper for every α > 0, whereas the uncancelled expression is ∞/∞ at α < 1.
  • Estimator: The renormalised and standardised susceptibility matrices remain well-defined, and the theorem conclusions survive positive column scalings.The estimator replaces expectations by sample means, while standardisation removes constant column offsets.
  • Symmetry: Recoding equivariance passes from machines to susceptibilities, renormalised matrices, and standardised representations.The component partition functions and columnwise standardisation commute with the recoding operator.
  • Rank structure: Path separation constrains the relevant susceptibility blocks to rank at most 2, including renormalised, standardised, and estimated matrices.Estimated blocks lie in a two-dimensional span up to floating-point rounding, so the bound holds at any sample count.

B.3 The GRLD sampler

The paper samples the localised Gibbs distribution with full-gradient Riemannian Langevin dynamics and assembles susceptibilities from componentwise sample means. The implementation uses fixed-step dynamics and numerical safeguards, with a measured discretisation bias and substantial calibration differences from NUTS.

  • Sampler: GRLD targets the local Gibbs distribution on the product of simplices using full gradients rather than stochastic minibatches.The loss is evaluated exactly because the input set is finite and model probabilities are polynomial in the simplex coordinates.
  • Parameterisation: The sampler represents each simplex factor with unnormalised positive coordinates θC and recomputes wC = θC/∥θC∥1 at every step.The update includes Dirichlet stationary drift, data drift from the loss, and reflection at the positive-orthant boundary.
  • Numerical choices: The implementation uses constant step size without Metropolis correction, introducing an O(ε) discretisation bias.Clipping θ to [10^-12, 10^30] provides a numerical guard near the boundary where the α < 1 localiser diverges.
  • Estimator: Each susceptibility estimate combines componentwise chains targeting pC with chains targeting the joint distribution p.Componentwise chains vary one factor while holding the others at the classical vertex; sample means are assembled into the susceptibility matrix.
  • Experimental settings: The susceptibility runs use 4 chains, 3000 sampling steps, 500 burn-in steps, ε = 0.01, seed 42, β = 30, and (γ, α) = (1, 0.01).These are the base settings reported for the susceptibility experiments.
  • Calibration: At α = 1, NUTS reaches CKA 0.999 in 200–800 samples, while GRLD needs 3000 but costs 31s rather than 236–373s per machine.The calibration compares convergence against between-machine similarities in a 2,216-machine reference set.

B.4 Embedding and compute

The embeddings use UMAP on cosine distances between flattened, centred, normalised input kernels, where cosine similarity equals CKA. The full temperature sweep required substantial GPU and CPU compute.

  • Embedding: UMAP embeds susceptibility input kernels using cosine distance on flattened, centred, normalised kernels, equal to dissimilarity 1 − CKA.The embedding uses n_neighbors = 15 and min_dist = 0.1.
  • Compute: The 35 temperature-slice jobs covered 38,019 machines and required about 145 GPU-hours in total.Each job ran on a single RTX 4090, with median duration 3.3 hours and a 3.2–9.7 hour range.

B.5 Input kernels of the running examples

Input kernels compare machines by whether their susceptibility responses align across input pairs, revealing structure among the running DFAs and supporting broader susceptibility-space analyses. The figures examine pairwise alignment, symmetry in eigenmatrices, and linear recoverability of algorithmic labels.

  • Running examples: M1 aligns with M2 and M3 with M4 at approximately 0.9, while the cross-pair alignments are 0.4–0.6.This separates the path-separable M1, M2 from the non-separable M3, M4 in the running examples.
  • Solution-set embedding: All 38,019 machines are embedded with UMAP using 1 − CKA between their estimated renormalised susceptibility kernels.The embedding scales the input-kernel comparison from the five examples to the full solution set.
  • Symmetry: The first eight eigenmatrix axes have definite parity under the recodings, with defects indicating whether a recoding fixes or negates an eigenmatrix.The leading eigenmatrices are evaluated across the two recodings, and variance fractions are shown on a log scale.
  • Label recovery: Linear SVMs test whether binary and six-class PSVmin labels can be recovered from flattened susceptibility matrices or their input kernels.Performance is measured by class-balanced accuracy on held-out machines with shuffled-label controls.

B.8 The weights of the binary classifier

The binary classifier’s weights concentrate on rejecting inputs, especially the off-diagonal susceptibility block associated with rejecting inputs and auxiliary states.

  • 37% of the classifier weight falls on the block Irej × C{s1,s2}, which contains 14% of entries.This is the off-diagonal block Xrej,A identified by the path-separation theorem.
  • 43% of the squared classifier weight lies on rejecting inputs, which comprise 21% of entries.
  • The classifier was refitted on the full solution set, with per-fold fits agreeing at cosine similarity ≥0.98.
  • The weights are shown after reshaping the standardised susceptibility matrices to the input × component grid.

B.9 The temperature sweep

An aligned UMAP temperature sweep shows susceptibility-space separation emerging as inverse temperature increases, with distinct clustering changes across the sweep.

  • 35 susceptibility slices across β ∈[0, 1000] were embedded jointly using aligned UMAP.Joint embedding preserves comparability of each machine’s position across inverse-temperature values.
  • Across β ∈[0, 17], low-PSVmin blue points slowly separate from the PSVmin = 0 purple cluster.
  • Beyond β = 17, two blue clusters separate from the remaining points on the right.
  • Between β = 10 and β = 100, the lower purple half forms a tightly packed disk while the upper half becomes more dispersed.
  • The aligned embedding uses relation regularisation λ = 5 × 10−3 to penalise displacement between consecutive slices.

B.10 Halting-time organisation

Halting-time pairs organise DFA susceptibility embeddings from the outset and remain stable across inverse temperature, while alphabet involution preserves a corresponding symmetry between classes.

  • The aligned embedding is coloured by the halting-time pair (t0, tA), where each time measures the first step reaching the target state.For the single-symbol accepting inputs, these times lie in {1, 2, 3} and proxy delays through intermediate states.
  • The halting-time organisation is present from the outset and remains stable across the temperature sweep.
  • Halting-time classes achieve nearest-neighbour shares of 0.89 at β = 1, 0.88 at β = 67, and 0.90 at β = 610.These values exceed the largest-class share of 0.44.
  • The class counts are symmetric in (t0, tA), because alphabet involution exchanges the (i, j) and (j, i) cells.
  • In the noisy absorbing DFA, the only noisy transition is q0’s self-loop on A, while the first blank sends either state to q1 permanently.The model runs for exactly T steps, padding shorter inputs with blanks.

C.2 Exact error probabilities and Hessian blindness

The minimal absorbing-DFA example has an error probability that is zero for shorter inputs and w^T for the full-length input, making the Hessian blind in the singular regime while susceptibilities remain informative.

  • For inputs A^n, the exact error probabilities are h_n(w) = 0 for 1 ≤ n < T and h_T(w) = w^T.A blank repairs every shorter input, whereas the full-length input remains wrong only after T consecutive self-loop errors.
  • For T ≥2 and q_T > 0, the zero set is {0}, yet the Hessian vanishes completely.The model is therefore singular and the Hessian misses an error direction.
  • For T = 1, the model is regular with H′′(0) = 2q1.
  • The loss begins at order w^2T because changing the output requires T persistent transition errors.A single error is insufficient to alter the final state.
  • The Gibbs moments satisfy ⟨H⟩ = 1/(2Tβ) + o(β−1) and Var(H) = 1/(2Tβ^2) + o(β−2).
  • The one-parameter model attains the bound λ ≤ 1/(2T) because it corrects every error syndrome of weight less than T.

C.5 Computational interpretation

The example shows how susceptibility signs reveal whether computation corrects a fault before output or exposes it at termination. Extending the model to noisy writes separates informative curved directions from free directions with zero susceptibility.

  • Fault correction and exposure: For inputs A^n with n<T, the first blank repairs every fault before output, yielding χ_A^n > 0 and a broadened Gibbs distribution.The computation crosses the repair boundary before the output is read, so shorter inputs do not constrain the fault parameter.
  • Fault correction and exposure: For A^T, no blank-reset phase occurs before halting, so the fault remains visible, yielding χ_A^T < 0 and Gibbs concentration.The terminal input exposes the fault and constrains the Gibbs distribution in the parameter direction.
  • Fault correction and exposure: The susceptibility magnitude decreases as β or T grows, while the scaled limit for n<T is 2^Tβ^2χ_A^n → 1.For A^T, the corresponding limit is −(1−q_T)/q_T, whose magnitude is large when q_T is small.
  • Noisy writes and flat directions: With noisy writes, write errors are never reread, so four write parameters form a family of machines with the same input–output map.The state evolution depends only on the input and transition parameters a, not on the write parameters b.
  • Noisy writes and flat directions: Write directions have zero susceptibility, whereas the curved transition direction has nonzero, sign-informative susceptibilities and the local learning coefficient remains λ = 1/(2T).The loss factors through projection onto a, making the write directions a four-dimensional flat fibre over the singular point.
Loading 2609.04661v1…