Source-linked AI summary

Interpretability for Turing Machines

Billy Snikkers, Rumi Salazar, Daniel Murfet, Will Troiani

arXiv:2609.04661v1cs.LGcs.FLstat.ML

TL;DR

How internal computational structure is represented in the local loss geometry of Turing machines is the central question. Using susceptibilities for noisy Turing machines, the paper proves that path separation and transition symmetries induce low-rank blocks and permutation symmetries, and finds an exact rank criterion for path separability in the studied DFA solutions.

  • Problem

    How internal computational structure is represented in the local loss geometry of Turing machines is the central question.

    Source: §1 · pp. 3–4
  • Method

    The paper adapts susceptibility analysis to noisy Turing machines, relating transition symmetries and path separation to structure in the susceptibility matrix.

    Source: §1 · p. 4, §2.3 · p. 12
  • Results

    For the studied DFAs, path separability corresponded exactly to the rank-≤2 susceptibility criterion, and susceptibility-space clusters separated path-separable from non-path-separable machines.

    Source: §1.1 · p. 5, §5.6 · p. 34
  • Takeaways & Limitations

    Susceptibility space captures path-separation structure in the studied DFA solutions.

    Source: §1.1 · p. 5, §5.6 · p. 34

    The experiments use µ=0, where smoothness and criticality fail, although the paper says its theorems do not require either property.

    Source: §2.3 · p. 13

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 asks whether a Turing machine’s internal computational structure is encoded in the local geometry of a loss that vanishes on machines with specified input-output behavior. It uses susceptibilities to connect path separation and transition symmetries to low-rank blocks and permutation symmetries.

1 Introduction

  • The framework probes loss geometry near exact solutions using susceptibilities, the linear responses of transition-component observables to perturbations of the input distribution.The loss is zero at machines that produce the specified halting state for every input in the finite support set.Source: §1 · pp. 3–4

1.1 Path separation and low-rank blocks

  • When accepting and rejecting runs use disjoint non-initial states, the cross-outcome susceptibility blocks have rank at most 2; numerical DFA estimates recover this criterion and organize machines into clusters.For the tested DFAs, path separation holds exactly when some partition has rank(Xacc,R) ≤2 and rank(Xrej,A) ≤2.Source: §1.1 · pp. 4–5, §1 · p. 4

1.2 Recoding symmetries and permutation symmetries

  • A machine’s recoding symmetry induces the corresponding row-and-column permutation symmetry in susceptibility; in PCA, recoded DFAs appear as reflections, with symmetric machines on the axes.For the studied recodings, the corresponding susceptibility blocks are identified up to the recoding of rows and columns.Source: §1.2 · pp. 6–7

1.3 Further contributions

  • The paper also contributes a circuit calculus for noisy computations and a minimal singular example where susceptibilities reveal structure that the Hessian cannot.The circuit calculus applies to noisy computations used in [MT25] and this paper.Source: §1.3 · p. 7

2 Noisy Turing machines

This section defines noisy Turing machines as a smooth learning setup built from machine transition codes, a pseudo-universal simulator, and relaxed execution. It then specifies the truth-model-prior loss and component susceptibilities used to probe machine behavior.

2.1 Pseudo-UTMs

  • A pseudo-UTM encodes transition tuples on auxiliary tapes and simulates one step of the coded machine in a fixed period, returning those tapes to their loaded configuration.The machine code records, for each symbol-state pair, the write symbol, next state, and head movement.Source: §1 · p. 3, §2.1 · pp. 9–10

2.2 Smooth relaxation of a pseudo-UTM

  • Noisy Turing machines extend the classical transition-code parameter space [CMW21], while a periodic smooth relaxation induces a smooth cycle map that agrees with classical execution at machine-code vertices.The noisy loading map carries transition distributions and noisy configurations into the simulator's tapes; periodicity requires the code to remain unchanged through each cycle.Source: §2.2 · pp. 10–12

2.3 The noisy Turing machine truth-model-prior triple

  • The noisy-machine truth-model-prior setup [MT25] uses finite labeled inputs, a full-support input distribution, a target state map, and a step limit to define a relaxed-execution model and loss.Mixing predictions with a uniform component makes the loss finite and smooth; experiments use the log-loss at µ = 0, since the cited theorems do not require smoothness or criticality.Source: §2.3 · pp. 12–13

2.4 Components, observables, and susceptibilities

  • Components index each symbol-state transition's write-symbol, next-state, and direction factors; susceptibilities are Gibbs-distribution responses to input-distribution perturbations, following [BWHM26].The input perturbation changes the loss, and each component observable is evaluated on the slice varying that component around the classical solution.Source: §2.4 · p. 14
  • Susceptibilities measure how component observables respond to perturbing the input distribution, and a minimal example shows they detect an error direction invisible to the Hessian.The observable is supported on the slice varying one transition component; susceptibility can also be written as a covariance under the unperturbed Gibbs distribution [BWHM26].Source: §2.4 · p. 14

3 Structures in Turing machines

This section characterizes algorithmic structure through path-separation partitions and recoding symmetries, then illustrates both structures with example finite automata.

3.1 Path separation partitions

  • A path-separation partition divides noninitial states into accepting and rejecting regions, with each run confined to its outcome’s region; its violation is zero exactly for such partitions.Accepting runs may continue through states in the accepting region before halting, and rejecting runs likewise remain in the rejecting region.Source: §3.1 · p. 15

3.2 Recoding symmetries

  • A recoding symmetry is a code-preserving pair of alphabet and state bijections, and the symmetries of a machine form the group Aut(M).The alphabet map fixes the blank and preserves the input set; the state map fixes the initial, accepting, and rejecting states.Source: §3.2 · p. 16
  • For a classical solution, a recoding symmetry gives zero asymmetry and makes the output on a recoded input equal the recoded output.In symbols, Asym(M; a, s) = 0 and y(a(x)) = s(y(x)).Source: §3.2 · p. 16

3.3 Examples

  • The examples comprise five 5-state DFAs deciding the same finite-alphabet language, with varying path-separation partitions and recoding symmetries.Source: §3.3 · pp. 16–17

4 Theorems

The section proves that path separation yields low-rank off-diagonal susceptibility blocks, while compatible recoding symmetries make the susceptibility matrix equivariant and induce group actions on loss singularity germs.

4.1 Rank bounds from path separation

  • Under unmatched-component invariance, path separation makes both opposite-region off-diagonal susceptibility blocks rank at most 2.The result applies to a classical solution whose state partition separates accepting and rejecting paths.Source: §4.1 · p. 20

4.2 Susceptibility symmetry from recoding symmetry

  • With a recoding-equivariant cycle map and invariant input distribution and prior, a machine symmetry makes the susceptibility matrix equivariant.The target map must respect the recoding, as follows for a classical solution and its symmetry.Source: §4.2 · p. 22
  • Under Proposition 4.12’s hypotheses, recoding symmetries act on the loss singularity germ; if the hypotheses hold for every element of G, the germ carries a G-action.For a cyclic symmetry generated by g, the action is by ⟨g⟩; for a subgroup G, it is a G-action.Source: §4.2 · p. 22

5 Experiments … A.4 The cycle maps in closed form

This section studies whether estimated DFA susceptibilities reveal theoretical symmetries, path separation, and transition structure, and how solution machines organize in susceptibility space. Its appendix details the pseudo-UTMs, circuit semantics, and cycle maps used in the analysis.

5.1 The DFA task and parameter space

  • The DFA task uses nonempty strings over either alphabet of length at most 3, runs for T = 5 steps, and has 15 free transitions.The parameter space fixes terminal states to self-loop and preserves that restriction under noise.Source: §5.1 · p. 23, §5.4 · p. 31

5.2 From theoretical to empirical susceptibilities

  • The experiments estimate renormalized and standardized log-loss susceptibilities from local Gibbs samples; renormalization avoids an infinite normalization ratio when α < 1.The reported conclusions of Section 4 survive renormalization and standardization.Source: §5.2 · pp. 24–25

5.3 Block structure in estimated susceptibilities

  • M1, M4, and M5 show approximate susceptibility permutation symmetries reflecting transitions that treat A like 0 and B like 1.The paired blocks are visually similar, and the symmetry defect is small for machines carrying the corresponding recoding symmetry.Source: §5.3 · p. 26
  • Input susceptibility vectors show alphabet-involution reflections in selected machines, while a leading principal component appears correlated with input length.The observed reflections align roughly with PC1 in M5 and PC2 in M3 and M4; the text notes that a larger input set would support a more conclusive analysis.Source: §5.3 · p. 26, Figure 8 · p. 27
  • For path-separated DFAs, estimated off-diagonal susceptibility blocks have numerical rank at most 2, while the non-path-separated M4 blocks exceed that bound.Figure 9 reports ranks 2 and 1 for M1, versus 5 and 4 for M4; Table 3 summarizes numerical ranks by partition.Source: §5.3 · p. 28, Figure 9 · p. 29, Table 3 · p. 30

5.4 The solution set in susceptibility space

  • Among 38,019 canonical representatives of the solution DFAs, estimated susceptibilities show organizational structure along leading principal components, explored against minimum path-separation violation and expected halting time.The staged UTM used for this analysis does not satisfy recoding equivariance, yet estimated susceptibilities still exhibit the predicted permutation symmetries.Source: §5.4 · pp. 31–32
  • Path-separable machines form a distinct susceptibility-space cluster, while PC1 correlates with path-separation violation and expected halting time.The reported correlations with PC1 are −0.97 for path-separation violation and 0.84 for expected halting time.Source: §5.4 · p. 32, Figure 10 · p. 33

5.5 Symmetry statistics

  • Reflections across the two symmetry axes place recoded machines nearby: median distances are 0.06 and 0.07, versus 1.42 for random pairs.Machines with zero algorithmic asymmetry also have lower symmetry defects than machines with nonzero asymmetry.Source: §5.5 · p. 33, Figure 11 · p. 33

5.6 Rank statistics

  • Across 38,019 machines, path-separation rank is at most 2 exactly for path-separable DFAs, with no exceptions in the solution set.The rank bound holds for every path-separable machine; the converse is empirical. In blocks exceeding the bound, the median third singular value is 0.52σ1, well above sampling noise.Source: §5.6 · p. 34, Figure 13 · p. 35

5.7 UMAP embeddings of susceptibilities

  • UMAP clusters separate machines with zero minimal path-separation violation, and linear classifiers recover those classes from susceptibilities alone.Colouring the same embedding by path-separation rank recovers the same cluster organization.Source: §5.7 · p. 36, Figure 14 · p. 36

5.8 Interpreting clusters

  • Transition-rule decision trees resolve susceptibility clusters: initial-state loops distinguish major groups, while blank-symbol transitions further split path-separable machines.Machines whose two subroutine states accept on blank form a disc that separates from the main body between β = 1 and β = 30.Source: §5.8 · p. 37, Figure 15 · p. 37, Figure 16 · p. 37

A Details of the model

  • The appendix records the finite-set circuits behind the model, including two pseudo-UTMs and closed-form cycle maps from naive probabilistic extensions.The staged machine comes from [MT25, §5.1]; the lookup pseudo-UTM is introduced because its cycle map is recoding equivariant, as required by Theorem 4.13.Source: A Details of the model · p. 39

A.1 The lookup pseudo-UTM

  • The lookup pseudo-UTM reads each input pair once, records it in its control state, then copies the matching output triple before updating the simulated tapes.Unlike the staged machine of [MT25, §5.1], its naive probabilistic extension does not depend on scan order.Source: §A.1 · pp. 40, 42, Figure 17 · p. 41

A.2 Circuits

  • The circuit formalism represents computation with finite-set gates and string diagrams, and yields the same relaxations as differential linear logic with Sweedler semantics.The appendix defines gates as functions between finite input and output types.Source: A Details of the model · p. 39, §A.2 · p. 42
  • Circuit coordinate interpretations compose sequential gates and tensor side-by-side gates, but naive probabilistic semantics treats duplicated wires as independent.For the circuit computing s ∧ ¬s, the naive extension agrees with the constant-zero gate only at the two vertices of the binary-distribution simplex.Source: §A.2 · pp. 43, 45

A.3 The cycle circuits

  • The eval, lookup, and staged cycle circuits each compute one machine step; lookup and staged present one period of a pseudo-UTM, while eval is the abstract transition-table circuit.All three share the fixed update circuit and differ only in their resolve circuits; the pseudo-UTM periods leave the description tape unchanged.Source: §A.3 · p. 46

A.3.1 Resolve

  • The eval, lookup, and staged resolve circuits compute the same lookup on classical inputs but implement it differently.Staged resolve scans tuple entries through overwrite gates, lookup carries match information in its state, and eval selects code fields using the read pair as an address.Source: §A.3.1 · pp. 48–50

A.3.2 Update

  • In a finite window, each tape-update output reads its cell and two neighbours, expanding the output window by one square on each side.Because inputs are copied to local gates, perturbing one input square can affect three output squares.Source: §A.3.2 · p. 51
  • The update circuit writes the resolved symbol at the head square, passes other squares through, and shifts the overwritten register by the direction, using blank constants beyond the finite window.Figure 24 shows the shift subcircuit for window h = 2, with duplicated square and direction inputs feeding output-cell multiplexers.Source: Figure 23 · p. 52, Figure 24 · p. 52

A.4 The cycle maps in closed form

  • Combining resolve and update gives cycle maps that are polynomial, hence smooth, and restrict to one classical period of the simulated machine.The cycle maps are constructed directly as circuits.Source: §A.4 · p. 53
  • The cycle circuits are faithful to the canonical relaxation’s dependency structure, a match verified numerically despite the full P-step circuit having too many paths to reason about usefully.The authors say the identification can be checked mechanically, though at length; the cycle circuits render only dependencies that survive across a period.Source: §A.4 · p. 53
  • The lookup machine’s cycle map is the naive probabilistic extension of the eval cycle circuit.The lookup and eval cycle circuits share the update circuit.Source: §A.4 · p. 55

A.5 Invariance and equivariance of the cycle maps

The staged and lookup pseudo-UTM relaxations are invariant to changes in an unmatched tuple component, while the lookup pseudo-UTM is equivariant under recodings of symbols and states. For the lookup machine, recoding compatibility follows from reindexing the input-pair mixtures, and it implies that the lookup UTM is smooth relaxation preserving.

A.5 Invariance and equivariance of the cycle maps

  • The staged and lookup pseudo-UTM relaxations are unmatched-component invariant.At a configuration whose read pair does not match the component being replaced, that component contributes with zero decision weight, leaving the cycle map unchanged.Source: §A.5 · p. 55
  • The lookup pseudo-UTM is equivariant under recodings of symbols and states.This also implies that the lookup UTM is smooth relaxation preserving [Xu21].Source: §A.5 · p. 55
  • For the lookup machine, the decision weights satisfy νj = λj and νX = 0, so its cycle map is determined by input-pair mixtures.Under a recoding, match weights transform by the symbol and state bijections and are preserved after reindexing input pairs.Source: §A.5 · p. 56
  • Because pushforward commutes with mixtures using the same weights, the recoded cycle-map outputs are the recodings of the original outputs.Direction values are unchanged by the action, while output cells and states are mapped by the symbol and state bijections.Source: §A.5 · p. 56

B Details of the experiments

The appendix expands the Section 5 experiments, examining whether susceptibility properties persist under alternative loss and preprocessing choices, and documenting experimental methods and analyses.

B Details of the experiments

  • It checks whether the susceptibility rank bound and equivariance persist with log-loss and after localisation, renormalisation, and standardisation.It also gives the Dirichlet localiser a Bayesian interpretation and isolates divergence of its slice evaluations when α < 1.Source: B Details of the experiments · p. 56
  • It describes the GRLD sampler and calibration, embedding parameters and compute, and input kernels for the running examples.Source: B Details of the experiments · p. 56
  • It reports analyses of eigenmatrix parities, cluster validation for Fig. 1, binary-classifier weights, temperature sweeps, and halting-time organisation of the solution set.Source: B Details of the experiments · p. 56

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

Reparametrising the error probability preserves the susceptibility rank bound and, for input-independent reparametrisations, the equivariance result. The section also establishes that these conclusions apply to the unshifted log-loss and that the renormalised susceptibility converges as the shifted loss parameter tends to zero.

  • Reparametrising the error probability preserves the off-diagonal rank bound of at most 2 and the equivariance result for input-independent reparametrisations.Each off-diagonal column is a linear combination of two vectors; the equivariance proof applies to the reparametrised observable.Source: §B.1 · pp. 56–57

Remark B.2

  • The rank and equivariance conclusions also hold for the unshifted log-loss, despite its infinite value when the error probability is 1.The infinite-loss set has measure zero, so the relevant expectations remain finite and the proofs apply unchanged.Source: §B.1 · p. 57

Proposition B.3

  • As the shift parameter μ tends to zero, the renormalised susceptibility converges to its value at μ = 0.The expectations of ℓ_x, L, Lℓ_x, and L² under the shifted Gibbs distributions converge to their values at μ = 0.Source: §B.1 · pp. 57–58

B.2 Properties of the localiser and the estimator

This subsection characterizes how the Dirichlet localiser concentrates around classical machines and clarifies when susceptibility calculations on slices are well-defined. It also establishes that recoding equivariance and low-rank block structure persist under renormalisation, standardisation, and estimation.

B.2 Properties of the localiser and the estimator

  • For α ≤ 1 and γ + α ≥ 1, the Dirichlet localiser pulls gradient flow toward the classical value, while for α > 1 it pulls toward the interior mode.The localiser is a posterior after observing each description square’s classical value γ times; γ controls the expected probability of that value.Source: §B.2 · p. 59
  • At (γ, α) = (1, 0.01), the experiments use a posterior concentrated near deterministic squares; with |ZC| = 5, the classical-value probability is 0.96, versus 1/3 at (1, 1).The α → 0 limit is improper, but α = 0.01 is empirically indistinguishable from it.Source: §B.2 · p. 59
  • For α < 1, the uncancelled slice susceptibility is ill-defined, but the cancelled distribution is proper and the renormalised susceptibility and estimator remain usable.The conclusions about susceptibility columns survive positive column scalings; at α = 1 the slice quantities are finite without cancellation.Source: §B.2 · pp. 59–60
  • Under the stated recoding and target-invariance conditions, susceptibility is recoding-equivariant, and this property passes to its renormalised and standardised forms.The conditions hold for recodings that are symmetries of a classical solution; both recodings in Section 3.2 are symmetries of M5.Source: §B.2 · p. 60
  • The rank bound of at most 2 holds for renormalised and standardised susceptibility blocks and for estimated blocks, with the estimator bound exact at any sample count up to floating-point rounding.The columns lie in a two-dimensional span; for estimated blocks, the span is generated by the sample-dependent vector and the constant vector.Source: §B.2 · p. 61

B.3 The GRLD sampler

The section describes GRLD as the full-gradient sampler used to draw from the local Gibbs distribution on products of simplices, and reports its calibration against NUTS.

B.3 The GRLD sampler

  • The expanded-mean update applies to unnormalised θ, with c − θ as stationary drift, reflection at the positive-orthant boundary, and a natural-gradient data drift.The simplex point w = θ/∥θ∥1 is recomputed for gradient evaluation and recorded samples, while θ itself is never rescaled; the data drift is diag(θ)∇θ(−L).Source: §B.3 · pp. 61–62
  • GRLD uses an exact full gradient, targets a tempered localised Gibbs distribution, keeps a constant step size, and clips θ to [10^-12, 10^30].It has no Metropolis correction and therefore incurs O(ε) discretisation bias; clipping guards single-precision arithmetic near the boundary where the α < 1 localiser diverges.Source: §B.3 · p. 62
  • Componentwise chains update θC alone while other factors stay at their corresponding [M] vertices; chains targeting p update all factors.The susceptibility matrix is assembled from the resulting sample means.Source: §B.3 · p. 62
  • At α=1, NUTS reaches CKA 0.999 in 200–800 samples versus GRLD’s 3000, costing 236–373s per machine versus 31s.Convergence is judged against self-similarity 0.999, above the largest between-machine CKA of 0.995 in the 2,216-machine reference set.Source: §B.3 · p. 62
  • Final kernel estimates agree at CKA ≥0.988 across γ∈{0, 1, 2, 10} for α=1, but agreement falls to 0.82 at α=0.1 and 0.49 at α=0.01.At α=0.01, NUTS requires 3503s per machine, while GRLD’s reflecting discretisation is insensitive to the localiser.Source: §B.3 · p. 62

B.4 Embedding and compute

Input-kernel embeddings use UMAP with cosine dissimilarity equivalent to 1 − CKA. The temperature sweep required about 145 GPU-hours, while aligned UMAP fits took one to two hours each on a CPU workstation.

B.4 Embedding and compute

  • UMAP embeds flattened, centred, normalised input kernels using 15 neighbors, min_dist = 0.1, and cosine distance, equivalent to 1 − CKA.The cosine similarity of these kernels is exactly the CKA.Source: §B.4 · p. 62
  • The 35 temperature-slice sampling jobs took about 145 GPU-hours in total, with a median runtime of 3.3 hours per job on one RTX 4090.Jobs covered 38,019 machines; runtimes ranged from 3.2 to 9.7 hours, with the slowest at the divergence-prone low-β end. Base-parameter susceptibility runs used the same job type, and each aligned UMAP fit took one to two hours on a CPU workstation.Source: §B.4 · p. 62

B.5 Input kernels of the running examples · B.6 Eigenmatrix parities · B.7 Cluster validation

Across the examples, susceptibility input-kernel alignments separate path-separable from non-separable machines, eigenmatrix axes show recoding parities, and PSVmin labels are linearly recoverable from susceptibility data.

B.5 Input kernels of the running examples

  • M1 aligns with M2 and M3 with M4 at approximately 0.9 CKA, while the two pairs score 0.4–0.6 and separate path-separable from non-separable examples.Source: §B.5 · p. 63
  • The input-kernel embedding extends the comparison to all 38,019 machines, placing them in a plane with UMAP [MHM18] on 1 −CKA.Source: §B.5 · p. 63

B.6 Eigenmatrix parities

  • The first eight eigenmatrix axes have definite recoding parity: v1 is fixed by both recodings, v7 is negated by both, and v2 and v3 are negated by exactly one.Source: §B.6 · p. 64, Figure 27 · p. 65
  • Among the leading 32 of 420 eigenmatrices, parity becomes indefinite from the ninth axis onward; Figure 27 also reports each axis’s fraction of variance.Source: §B.6 · p. 64, Figure 27 · p. 65

B.7 Cluster validation

  • Six-class errors on standardised matrices only confused adjacent PSVmin values, supporting that labels can be read directly from susceptibility data without the embedding.Source: §B.7 · p. 65
  • The binary label was recovered essentially perfectly in every representation; standardised matrices got all 38,019 held-out predictions correct versus 0.50 shuffled controls, and six-class accuracy was 0.99.Source: §B.7 · p. 65, Figure 28 · p. 66

B.8 The weights of the binary classifier

The binary classifier concentrates its squared weight on rejecting inputs, especially a rejecting-input/state block. Its matching row patterns are consistent with approximate equivariance under the alphabet involution.

B.8 The weights of the binary classifier

  • The {A, B}-class and {0, 1}-class rows show the same pattern, consistent with an approximately equivariant learned readout.The solution set is closed under the alphabet involution (Lemma B.6), and the labels are invariant under it.Source: §B.8 · p. 66
  • Per-fold classifier fits agree with the full-solution-set refit to cosine similarity ≥0.98.The classifier predicts whether PSVmin = 0 versus > 0 on standardised matrices.Source: §B.8 · p. 66
  • 37% of squared classifier weight falls on block Irej × C{s1,s2}, which occupies 14% of entries and corresponds to Xrej,A at A = {qacc, s1, s2}.The block is the off-diagonal block of Theorem 4.5 that organises the solution set.Source: §B.8 · p. 66, Figure 29 · p. 67
  • 43% of squared classifier weight falls on rejecting inputs, which make up 21% of entries.The classifier weights are reshaped to the input × component grid of b̃χ.Source: §B.8 · p. 66, Figure 29 · p. 67

B.9 The temperature sweep

An aligned UMAP temperature sweep shows susceptibility clusters separating and changing shape as inverse temperature β increases, using 35 jointly embedded checkpoints from β=0 to 1000.

B.9 The temperature sweep

  • Susceptibilities of the full solution set are recomputed at 35 inverse-temperature values from β∈[0, 1000], with one sampling run per value.The 35 checkpoints are jointly embedded so each machine’s position is comparable across β.Source: §B.9 · p. 67
  • Across β=0–17, low-positive-PSVmin blue points gradually separate from zero-PSVmin purple points; beyond 17, two blue clusters separate from the remaining points.The 35 slices are coloured by PSVmin.Source: §B.9 · p. 67, Figure 30 · p. 68
  • As β sweeps from 10 to 100, the lower purple cluster half forms a tightly packed disk while the upper half becomes more dispersed.This shape change occurs alongside the separation of the blue clusters.Source: §B.9 · p. 67, Figure 30 · p. 68
  • AlignedUMAP [MHM18] jointly optimizes the 35 slices with λ=5×10^-3, selected to preserve clustering nearly as in unaligned UMAP at β=30 while preventing large-scale rotations.The embedding penalizes displacement between consecutive slices with window size 2.Source: §B.9 · p. 67

B.10 Halting-time organisation · C Minimal theoretical example: What is the simplest thing susceptibilities see that the Hessian does not? · C.1 The noisy absorbing DFA

Susceptibility-space neighborhoods organize by halting-time pair, with that structure stable across β values. The appendix develops a minimal noisy-DFA example of structure susceptibilities reveal but the Hessian does not.

B.10 Halting-time organisation

  • Halting times t0 and tA in {1, 2, 3} proxy delay to acceptance, and class counts are symmetric because the alphabet involution exchanges (i, j) and (j, i).The halting-time organisation is present from the outset and stable across β.Source: §B.10 · pp. 68–69
  • At β=1, 67, and 610, 0.89, 0.88, and 0.90 of each machine’s 20 nearest neighbours share its (t0,tA) class, versus a largest-class share of 0.44.Figure 31 shows the halting-time clusters across β.Source: Figure 31 · p. 69, §B.10 · p. 69

C Minimal theoretical example: What is the simplest thing susceptibilities see that the Hessian does not?

  • The minimal example develops the noisy-DFA cycle-map reduction, exact error probabilities and Hessian blindness, Gibbs-moment asymptotics for susceptibility values, and a noisy-write extension with flat directions.Source: C Minimal theoretical example: What is… · p. 69

C.1 The noisy absorbing DFA

  • The noisy absorbing DFA uses states q0 (initial/reject) and q1 (accept), inputs A1 through AT, and runs each input for T steps with blanks padding the remainder.The output is the state after T steps.Source: §C.1 · p. 69
  • On A, q0 remains q0 with probability w and otherwise transitions to q1; blanks send either state to q1, which then remains absorbing.Small w perturbs the classical DFA at w=0, whose correct output is q1 for every input.Source: Figure 32 · p. 70, §C.1 · p. 71
  • For a noisy DFA on a deterministic tape, evaluation shifts the tape left in head-relative coordinates while keeping it deterministic, and the state-transition matrices are column-stochastic.Source: §C.1 · p. 71

C.2 Exact error probabilities and Hessian blindness · C.3 The Gibbs distribution and monomial asymptotics · C.4 Susceptibilities

In the noisy absorbing-DFA slice, errors occur only when all T transitions fail, making the squared loss invisible to the Hessian for T≥2. The Gibbs moments yield a learning coefficient of 1/(2T), and nonterminal-input susceptibilities equal the variance of the loss.

C.2 Exact error probabilities and Hessian blindness

  • h_n(w)=0 for n<T, while h_T(w)=w^T: only the terminal input A_T contributes error in the one-parameter absorbing DFA.For n<T, a blank step deterministically sends the machine to q1; for n=T, all T noisy self-loops must occur.Source: §C.2 · pp. 71–72
  • For T=1, H′′(0)=2q1; for T≥2 with qT>0, the zero set is {0}, yet the Hessian vanishes because squared loss starts at order w2T.The error probability starts at order wT, so for T≥2 there is no quadratic term for the Hessian to detect.Source: §C.2 · p. 72

C.3 The Gibbs distribution and monomial asymptotics

  • The reported entropy has mean ⟨H⟩=1/(2Tβ)+o(β^-1) and variance Var(H)=1/(2Tβ^2)+o(β^-2).Source: §C.3 · p. 72
  • λ=1/(2T) attains the [MT25] bound λ≤1/(2T) for this d=1 slice, where the DFA corrects every error syndrome of weight less than T.Here C=T−1 because only failure of all T consecutive A-reads on input A_T can affect the output.Source: §C.3 · p. 73

C.4 Susceptibilities

  • For n<T, χ_A_n=Var(H)=1/(2Tβ^2)+o(β^-2), with per-input susceptibility defined as −Cov[H,∆n].Source: §C.4 · p. 74

C.5 Computational interpretation · C.6 Extension: noisy writes and flat directions

In the noisy-write example, the first blank erases transition faults before they can affect outputs, while a fault remains visible on an input with no blank before halting. Extending the model to noisy writes reveals free parameter directions with zero susceptibility, distinct from curved transition directions with informative susceptibilities.

C.5 Computational interpretation

  • The first blank is a repair boundary: it merges faulty and correct trajectories, yielding h_n(w) = 0 for n < T but h_T(w) = w^T.A fault remains visible only when the machine halts before a blank-reset phase.Source: §C.5 · p. 74
  • For n < T, the computation corrects every error pattern, so the likelihood of A^n is independent of w; only A^T constrains the Gibbs distribution in that direction.Source: §C.5 · p. 74
  • χ_A^T < 0 because upweighting A^T concentrates the Gibbs distribution, whereas χ_A^n > 0 for n < T because upweighting a shorter input broadens it.Source: §C.5 · pp. 74–75
  • The susceptibility magnitudes share a leading factor 1/(2Tβ^2), which decreases as β or T grows.As β → ∞, 2Tβ^2χ_A^n → 1 for n < T, while 2Tβ^2χ_A^T → −(1 − q_T)/q_T, whose magnitude is large when q_T is small.Source: §C.5 · p. 75

C.6 Extension: noisy writes and flat directions

  • The extension adds noisy writes via four parameters b(σ,q), each giving the probability of writing the wrong symbol, alongside the transition parameter a.The classical machine has b(σ,q) = 0 for all four state-symbol pairs, making the parameter space five-dimensional.Source: §C.6 · p. 75
  • Because the head always moves right, noisy writes are never re-read, so the four write parameters form distinct noisy machines computing the same input–output map.Source: §C.6 · p. 75
  • Write directions have zero susceptibility for every input, while transition directions retain informative signs; geometrically, the loss is flat along a four-dimensional fibre over the singular point.The local learning coefficient remains λ = 1/(2T); the transition direction is curved, with higher-order nonzero loss despite a vanishing Hessian.Source: §C.6 · p. 75
Loading 2609.04661v1…