This paper presents a PyTorch library that compiles exact Turing machines into neural networks—no training required. You provide a transition function and terminal states, and the library builds either a Transformer (with attention and feedforward layers) or a recurrent network (encoding the stack in a Cantor set) whose forward pass corresponds to one step of the Turing machine. The code shows how ReLU networks implement Boolean logic gates and how hard attention implements positional lookup, serving as a runnable reference for the symbolic-neural bridge.
Main takeaways:
- The library constructs neural networks that exactly simulate a given Turing machine, producing weights directly from the transition table with no training.
- Two architectures: a Transformer based on hard attention (Wei et al. 2021) and a recurrent net encoding the stack via Cantor-set encoding (Siegelmann & Sontag 1995).
- ReLU layers implement Boolean gates (AND, OR, NOT, XOR) and compose them into circuits; hard attention implements tape lookups.
- Intended as a reference for understanding symbolic computation in neural form and a testbed for studying stability of constructed solutions under gradient descent.