  Neural networks have in recent years shown promise for helping software
engineers write programs and even formally verify them. While semantic
information plays a crucial part in these processes, it remains unclear to what
degree popular neural architectures like transformers are capable of modeling
that information. This paper examines the behavior of neural networks learning
algorithms relevant to programs and formal verification proofs through the lens
of mechanistic interpretability, focusing in particular on structural
recursion. Structural recursion is at the heart of tasks on which symbolic
tools currently outperform neural models, like inferring semantic relations
between datatypes and emulating program behavior. We evaluate the ability of
transformer models to learn to emulate the behavior of structurally recursive
functions from input-output examples. Our evaluation includes empirical and
conceptual analyses of the limitations and capabilities of transformer models
in approximating these functions, as well as reconstructions of the ``shortcut"
algorithms the model learns. By reconstructing these algorithms, we are able to
correctly predict 91 percent of failure cases for one of the approximated
functions. Our work provides a new foundation for understanding the behavior of
neural networks that fail to solve the very tasks they are trained for.
