Interpretability for Turing Machines

Abstract: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.

75 pages, 31 figures, 3 tables. Interactive companion: this https URL. Code and data: doi:https://doi.org/10.5281/zenodo.22205895

Machine Learning (cs.LG); Formal Languages and Automata Theory (cs.FL); Machine Learning (stat.ML)

arXiv:2609.04661 [cs.LG]

(or arXiv:2609.04661v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2609.04661 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.