Interpretability for Turing Machines

Billy Snikkers; Rumi Salazar; Daniel Murfet; Will Troiani

Figure 1: Turing machines in susceptibility space. A UMAP embedding of the susceptibility matrices of

38{,}019

deterministic finite automata (DFAs) that agree with the language

\mathcal{L}_{\texttt{A},\texttt{0}}

of strings containing an A or a 0 on a finite set of test strings ( Sections 5.1 and 5.4 ). Each DFA is coloured by

\operatorname{PSV}_{\min}

, which is zero when accepted and rejected inputs pass through disjoint sets of intermediate states, and grows as they overlap. The fully path-separated machines form the large purple cluster on the left. Three example machines are shown of varying path-separability: in

M_{1}

every accepted input passes through

s_{1}

only and every rejected input through

s_{2}

only, while in the two machines on the right, accepted and rejected inputs share intermediate states.

Figure 2: Two structurally different deciders of

\mathcal{L}_{\texttt{A},\texttt{0}}

which are deterministic finite automata (DFAs; read-only and always move right), depicted by their transition graph on the set of states. An edge

q\to q^{\prime}

labelled

\sigma

denotes the transition

(\sigma,q)\mapsto(\sigma,q^{\prime},R)

. Left: the machine

M_{1}

is path-separable (only accepted

x

visit

s_{1}

and only rejected visit

s_{2}

). The shaded regions partition the non-initial states into an accept side

\{s_{1},q_{\mathrm{acc}}\}

and a reject side

\{s_{2},q_{\mathrm{rej}}\}

, and runs of

M_{1}

never enter the region of the opposite outcome. Right: in

M_{4}

the bold run of the accepted input BBA passes through both regions.

Figure 3: Exchanging the symbols

\texttt{A}\leftrightarrow\texttt{0}

and

\texttt{B}\leftrightarrow\texttt{1}

throughout the transition table of

M_{3}

(left) produces the machine

\overline{M_{3}}

(right); exchanging the states

s_{1}\leftrightarrow s_{2}

instead produces the same machine. Performing both exchanges therefore returns

M_{3}

unchanged: this is the symmetry

(\theta,s_{1}{\leftrightarrow}s_{2})

of

M_{3}

, made precise in Section 3.2 .

Figure 4: Recoding acts on the PCA by reflections. The

\mathrm{PC}_{2}\times\mathrm{PC}_{3}

plane of the PCA of the set of susceptibility matrices

\{\widehat{\psi}([M])\}

of the solution DFAs ( Section 5.4 ). Left: The recoding

(\theta,\mathrm{id}_{Q})

swaps

\texttt{A}\leftrightarrow\texttt{0}

and

\texttt{B}\leftrightarrow\texttt{1}

in a machine’s transitions, and this action becomes the reflection negating

\mathrm{PC}_{3}

, e.g.

M_{3}\mapsto\overline{M_{3}}

.

M_{1}

is invariant to

(\theta,\mathrm{id}_{Q})

and sits fixed on the horizontal axis. Right:

(\theta,s_{1}{\leftrightarrow}s_{2})

does the same but also swaps the states

s_{1}\leftrightarrow s_{2}

, and becomes the reflection negating

\mathrm{PC}_{2}

, e.g.

M_{1}\mapsto\overline{M_{1}}

.

M_{3}

is invariant to

(\theta,s_{1}{\leftrightarrow}s_{2})

and sits fixed on the vertical axis. DFAs are coloured by their asymmetry

\operatorname{Asym}(M;g)

at each of the two recodings

g

, which measures changes in

M

’s behaviour on inputs ( Definition 3.7 ), and is

0

on fixed points. Stars mark the DFAs

M_{1}

,

M_{3}

, and

M_{5}

, and the reflections

\overline{M_{1}}

,

\overline{M_{3}}

. The only machine fixed by both symmetries is

M_{5}

, which sits near the origin.

Figure 5: The initial configuration (left) of a Turing machine with input

x=x_{0}x_{1}x_{2}x_{3}\in\Sigma^{*}

, and the next configuration (right) after the first transition

[M](x_{0},q_{0})=(\sigma^{\prime},q^{\prime},d)

, split into the three cases of the direction

d

. Note that the head is always over tape position

0

, so we do not additionally track a position

p\in\mathbb{Z}

with the configuration data. It is natural to think of shifting the tape in the opposite direction, rather than shifting the head.

Figure 6: The loading map

\langle-\,;\,-\rangle

for the lookup pseudo-UTM ( Section A.1 ). The figure implicitly defines its code layout

\ell

. The code

{\color[rgb]{0,0,0.6}[M]}

(blue) occupies the squares

\ell(\sigma_{j},q_{j})

of the description tape, and the configuration

({\color[rgb]{0,0.5,0}\vec{y}},{\color[rgb]{0,0.5,0}q})

(green) the working and state tapes. Every other square (grey) is fixed by

\mathcal{U}

, independent of the code and the configuration. The red triangles mark the initial positions of the four UTM heads, and the circle is the initial UTM state

q_{\mathcal{U}}

, fixed by

\mathcal{U}

.

	diagram	measurements
$M_{1}$	$q_{0}$ $s_{1}$ $s_{2}$ $q_{\mathrm{acc}}$ $q_{\mathrm{rej}}$ $\texttt{B},\texttt{1}$ $\texttt{A},\texttt{0}$ $\square$ $\texttt{A},\texttt{B},\texttt{0},\texttt{1}$ $\square$ $\texttt{A},\texttt{B},\texttt{0},\texttt{1}$ $\square$	$\operatorname{PSV}(M_{1};\,\{q_{\mathrm{acc}},s_{1}\},\{q_{\mathrm{rej}},s_{2}\})=0$ ; $\operatorname{Asym}(M_{1};\,\theta,\,\mathrm{id}_{Q})=0$
$M_{2}$	$q_{0}$ $s_{1}$ $s_{2}$ $q_{\mathrm{acc}}$ $q_{\mathrm{rej}}$ $\texttt{B},\texttt{1}$ $\texttt{A},\texttt{0}$ $\square$ $\texttt{A},\texttt{B},\texttt{0},\texttt{1}$ $\square$ $\texttt{A},\texttt{B},\texttt{0},\texttt{1}$ $\square$	$\operatorname{PSV}(M_{2};\,\{q_{\mathrm{acc}},s_{1},s_{2}\},\{q_{\mathrm{rej}}\})=0$ ; $\operatorname{PSV}(M_{2};\,\{q_{\mathrm{acc}}\},\{q_{\mathrm{rej}},s_{1},s_{2}\})\neq 0$ ; $\operatorname{Asym}(M_{2};\,\theta,\,\mathrm{id}_{Q})=0$
$M_{3}$	$q_{0}$ $s_{1}$ $s_{2}$ $q_{\mathrm{acc}}$ $q_{\mathrm{rej}}$ B 1 $\texttt{A},\texttt{0}$ $\texttt{B},\texttt{1}$ A $\square$ $\texttt{B},\texttt{1}$ $\square$ 0	$\operatorname{Asym}(M_{3};\,\theta,\,s_{1}{\leftrightarrow}s_{2})=0$ ; $\operatorname{Asym}(M_{3};\,\theta,\,\mathrm{id}_{Q})\neq 0$
$M_{4}$	$q_{0}$ $s_{1}$ $s_{2}$ $q_{\mathrm{acc}}$ $q_{\mathrm{rej}}$ $\texttt{B},\texttt{1}$ $\texttt{A},\texttt{0}$ $\texttt{B},\texttt{1}$ $\texttt{B},\texttt{1}$ $\texttt{A},\texttt{0}$ $\square$ $\square$ $\texttt{A},\texttt{0}$	$\operatorname{Asym}(M_{4};\,\theta,\,\mathrm{id}_{Q})=0$ ; $\operatorname{Asym}(M_{4};\,\theta,\,s_{1}{\leftrightarrow}s_{2})\neq 0$
$M_{5}$	$q_{0}$ $s_{1}$ $s_{2}$ $q_{\mathrm{acc}}$ $q_{\mathrm{rej}}$ $\texttt{B},\texttt{1}$ $\texttt{A},\texttt{0}$ $\square$	$\operatorname{PSV}(M_{5};\,A,R)=0$ for every partition; $\operatorname{Asym}(M_{5};\,\theta,\mathrm{id}_{Q})=0$ ; $\operatorname{Asym}(M_{5};\,\theta,s_{1}\leftrightarrow s_{2})=0$

Table 1: The five running-example

\mathcal{L}_{\texttt{A},\texttt{0}}

-DFAs: state diagram with relevant

\operatorname{PSV}

and

\operatorname{Asym}

values. Omitted transitions are understood to be a self-loop

(\sigma,q)\mapsto q

.

Figure 7: Susceptibilities of the DFAs

M_{1},M_{3},M_{4},M_{5}

. Rows are inputs

x\in I\subseteq\Sigma^{*}

and columns are components

(\sigma,q)

, denoting the subspace

\Delta Q

of distributions over the “next-state” behaviour of

[M]

when seeing symbol

\sigma

in state

q

. The value at row

x

, column

(\sigma,q)

is the linear-response of the component observable

\phi_{(\sigma,q)}

(averaged over

W^{\mathrm{DFA}}

) to a perturbation of the data distribution on

I

that increases the probability of

x

( Definition 2.17 ). Rows are grouped by the partition

x\in\{\texttt{A},\texttt{B}\}^{*}\sqcup\{\texttt{0},\texttt{1}\}^{*}

, and columns by the partition

\sigma\in\{\texttt{A},\texttt{B}\}\sqcup\{\texttt{0},\texttt{1}\}\sqcup\{\square\}

, where

\sigma

is the symbol being read by

M

. The susceptibilities are computed by sampling a neighbourhood of

M_{i}

on the lookup UTM at inverse temperature

\beta=30

.

	$(\theta,\mathrm{id}_{Q})$		$(\theta,s_{1}{\leftrightarrow}s_{2})$
	$\operatorname{Asym}$	$\mathrm{sd}$	$\operatorname{Asym}$	$\mathrm{sd}$
$M_{1}$	$0$	0.040	$19/48$	$0.297$
$M_{2}$	$0$	0.012	$1/2$	$0.192$
$M_{3}$	$17/96$	$0.253$	$0$	0.016
$M_{4}$	$0$	0.011	$17/96$	$0.217$
$M_{5}$	$0$	0.005	$0$	0.005

Table 2: Machine asymmetry vs symmetry defect . The left column group is the symmetry that swaps the symbols

\texttt{A}\leftrightarrow\texttt{0}

and

\texttt{B}\leftrightarrow\texttt{1}

, and the right column group is the symmetry that swaps those symbols and the subroutine states

s_{1}\leftrightarrow s_{2}

. A machine carrying the symmetry has

0

in the

\operatorname{Asym}

column ( Proposition 3.8 ), and for the five machines shown the converse also holds, by direct inspection of their transition tables. Where

\operatorname{Asym}=0

, the symmetry defect (sd) of the estimate is small (bold).

Figure 8: First two principal components of the inputs in susceptibility space. Each point

x\in I

is an input to the DFA

M_{i}

, and embeds into a space of linear response-vectors

\widehat{\psi}([M_{i}])_{x}\in\mathbb{R}^{15}

, valued across the 15 component observables we measure during sampling. The leading principal components show projections of this space along which there is the greatest variance between inputs. Each panel is a separate PCA of its machine’s

28

rows, so components are not comparable across panels. Points are coloured as accepted inputs (green) and rejected inputs (orange). We observe each

M_{i}

has a component correlated with the length

|x|

(e.g.

\mathrm{PC}_{1}

of

M_{3}

), and in some cases the involution

\texttt{A}\leftrightarrow\texttt{0},\texttt{B}\leftrightarrow\texttt{1}

is a reflection across this component (edges indicate the involution).

Figure 9: Blocks with low rank in path-separable DFAs vs high rank in non-path-separable DFAs . An illustration of the rank bound of Theorem 4.5 on susceptibility matrices for

M_{1}

and

M_{4}

. Since

M_{1}

never visits region

A

on rejected inputs, variations in

s_{1}

-transitions have no effect on the rejected input’s loss, therefore the block

X_{\mathrm{rej},A}

(rows

I_{\mathrm{rej}}

, columns

\mathcal{C}_{A}

), has rank

2\leq 2

, and since it never visits region

R

on accepted inputs, the block

X_{\mathrm{acc},R}

(rows

I_{\mathrm{acc}}

, columns

\mathcal{C}_{R}

) has rank

1\leq 2

(both bounded by

2

by Theorem 4.5 ).

M_{4}

does not keep

I_{\mathrm{rej}}

and

I_{\mathrm{acc}}

separated along the regions

A,R

, and the corresponding blocks have ranks exceeding the bound:

\mathrm{rank}(X_{\mathrm{rej},A})=5>2

and

\mathrm{rank}(X_{\mathrm{acc},R})=4>2

. Top: the transition diagrams of

M_{1}

and

M_{4}

, with the regions shaded and the run of BBA bolded (repeated from Fig. 2 ), juxtaposed above their susceptibility matrices.

$A$	$\{q_{\mathrm{acc}},s_{1}\}$			$\{q_{\mathrm{acc}},s_{2}\}$			$\{q_{\mathrm{acc}},s_{1},s_{2}\}$			$\{q_{\mathrm{acc}}\}$
	$\operatorname{PSV}$	$X_{\mathrm{acc},R}$	$X_{\mathrm{rej},A}$	$\operatorname{PSV}$	$X_{\mathrm{acc},R}$	$X_{\mathrm{rej},A}$	$\operatorname{PSV}$	$X_{\mathrm{acc},R}$	$X_{\mathrm{rej},A}$	$\operatorname{PSV}$	$X_{\mathrm{acc},R}$	$X_{\mathrm{rej},A}$
$M_{1}$	0	1	2	$19/48$	$5$	$1$	$7/96$	$-$	$3$	$31/96$	$6$	$-$
$M_{2}$	$17/96$	$1$	$2$	$31/96$	$5$	$1$	0	$-$	2	$1/2$	$6$	$-$
$M_{3}$	$17/192$	$3$	$3$	$17/192$	$3$	$3$	$11/96$	$-$	$6$	$1/16$	$6$	$-$
$M_{4}$	$3/32$	$4$	$5$	$1/12$	$5$	$5$	$11/96$	$-$	$6$	$1/16$	$6$	$-$
$M_{5}$	0	0	0	0	0	0	0	$-$	0	0	0	$-$

Table 3: Path separation violations and off-diagonal numerical ranks . Each row is one of the example DFAs

M_{1},\dots,M_{5}

of Table 1 . Each column group is a partition

Q=A\sqcup R\sqcup\{q_{0}\}

with

q_{\mathrm{acc}}\in A

,

q_{\mathrm{rej}}\in R

, named by

A

(which determines

R

). Each group gives the path separation violation

\operatorname{PSV}=\operatorname{PSV}(M;A,R)

( Definition 3.2 ), which is zero when all accepted inputs only visit states

q\in A

and all rejected inputs only visit states

q\in R

(other than

q_{0}

). The next two columns in each group give the numerical ranks of the two off-diagonal blocks

X_{\mathrm{acc},R},X_{\mathrm{rej},A}

of

\widehat{\psi}([M])

, with “

-

” when the block is empty (no component observables). Both ranks are at most

2

wherever

\operatorname{PSV}=0

(bold), as Theorem 4.5 requires.

Figure 10: PC1 correlates with path-separability and halting time. The first two principal components of the set of susceptibility matrices

\{\widehat{\psi}([M])\mid[M]\in W^{\mathrm{sol}}\}

. DFAs in the left plot are coloured by

\operatorname{PSV}_{\min}

, which is zero for path-separable DFAs, whose rejected and accepted inputs visit disjoint sets of intermediate states, and increases with violations of this condition. The DFAs in the right plot are coloured by expected halting time , the time

M

takes to enter the reject or accept state on input

x

(subject to the input distribution

q(x)

).

Figure 11: Algorithmic symmetry is measurable from estimated susceptibilities. Left, middle: distributions of the symmetry defect

\mathrm{sd}_{g}(\widehat{\psi})

( 25 ) at the two symmetries

(\theta,\mathrm{id}_{Q})

and

(\theta,s_{1}{\leftrightarrow}s_{2})

, split between

\operatorname{Asym}=0

and

\operatorname{Asym}>0

. Dashed lines mark each group’s median, and we see the median

\operatorname{Asym}=0

machine has much lower defect than the median

\operatorname{Asym}>0

machine. Right: distributions of the distance, in the

\mathrm{PC}_{2}\times\mathrm{PC}_{3}

plane of Fig. 4 , from a machine reflected across its symmetry’s fixed axis (negating

\mathrm{PC}_{3}

at

(\theta,\mathrm{id}_{Q})

and

\mathrm{PC}_{2}

at

(\theta,s_{1}{\leftrightarrow}s_{2})

) to the recoded machine

g\cdot[M]

. Dashed lines mark the median of each distribution and a baseline median-distance between random pairs of machines.

Figure 12: Machines with

\operatorname{PSV}=0

satisfy the rank bound, and machines with

\operatorname{PSV}>0

exceed it. Numerical ranks of the off-diagonal blocks

X_{\mathrm{acc},R}

and

X_{\mathrm{rej},A}

( Definition 5.2 ) at the partitions

s_{1}\in A

,

s_{2}\in R

(top) and

s_{1},s_{2}\in A

(bottom), split by

\operatorname{PSV}(M;\,A,R)=0

versus

>0

. At

s_{1},s_{2}\in A

the block

X_{\mathrm{acc},R}

is empty:

R=\{q_{\mathrm{rej}}\}

has no component observables. The dashed line marks the bound of Theorem 4.5 .

Figure 13: The path separation rank agrees with path separability. Distribution of the path separation rank

\operatorname{PSR}(\widehat{\psi}([M]))

( Definition 5.2 ): the larger of the two off-diagonal block ranks, minimised over the four partitions of the non-initial states, split by

\operatorname{PSV}_{\min}(M)=0

versus

>0

. No machine falls on the wrong side of the bound of Theorem 4.5 (dashed line).

Figure 14: Path separation violation and path separation rank agree cluster by cluster. The input-kernel embedding of Fig. 1 (

\beta=30

), coloured by the minimal path separation violation

\operatorname{PSV}_{\min}

( Definition 3.2 , left) and by the path separation rank

\operatorname{PSR}(\widehat{\psi}([M]))

( Definition 5.2 , right).

Figure 15: The transition decision tree. Each internal node tests the indicated transition-table entries, edges answer yes (Y) or no (N), and each leaf carries its colour, name, and machine count.

\bar{s}

denotes the subroutine state that does not accept on blank.

Figure 16: The input-kernel clusters are conjunctions of transition-table facts. The aligned input-kernel embedding at three values of

\beta

, coloured by the leaves of the transition decision tree of Fig. 15 . Labels mark the running examples

M_{1}

–

M_{5}

.

Interpretability for Turing Machines

Abstract

Figures & tables

Appendix

Algorithmic Reasoning

Specific Algorithmic Interpretability of Neural Networks: A Case Study on Textures

Interpreting Reinforcement Learning Agents with Susceptibilities

A PyTorch Library of Turing-Complete Neural Networks

Abstract

Algorithmic Reasoning

Explore similar work

Specific Algorithmic Interpretability of Neural Networks: A Case Study on Textures

Interpreting Reinforcement Learning Agents with Susceptibilities

A PyTorch Library of Turing-Complete Neural Networks