The right prompt can theoretically turn a transformer into any computer program — but does training actually produce that, or just clever mimicry?

This explores the two-way relationship between program synthesis and transformers-as-computers. In one direction, the transformer is the thing being programmed; in the other, its internal computation is what gets synthesized back into explicit programs. The corpus puts both directions in tension with a harder question: do transformers actually compute general algorithms, or only appear to?

Start with the strongest claim that they can. A single finite-size transformer is provably Turing complete — there exists one fixed network that, given the right prompt, computes any computable function, with the prompt itself acting as the program Can a single transformer become universally programmable through prompts?. So in principle the transformer is a universal machine and the prompt is program synthesis by another name. The catch, stated in that same result, is that ordinary training almost never produces a model that has actually learned to run arbitrary programs this way. Existence is not learnability.

Program synthesis also runs the other direction: instead of writing programs for the transformer, you recover programs out of it. One line of work synthesizes executable code that matches 99% of an attention head's behavior, then swaps 30–40% of heads for their synthesized programs while preserving question-answering ability Can executable programs replace transformer attention heads?. That is a concrete bridge — it says a large chunk of what a transformer computes really is program-like enough to be extracted as testable code, which doubles as a formal interpretability method rather than a hand-wavy natural-language summary.

But when you ask whether transformers compute *general* algorithms, the corpus gets skeptical. Compositional reasoning often reduces to linearized subgraph matching — the model memorizes computation subgraphs from training and fails on novel compositions, with errors compounding Do transformers actually learn systematic compositional reasoning?. And chain-of-thought, which looks like an algorithm being executed step by step, may be an architectural workaround: feedforward transformers have no native recurrent state, so they externalize evolving state into tokens because depth runs out Why do transformers need explicit chain-of-thought reasoning?. There is even evidence the real computation hides in early layers and gets overwritten by filler tokens Do transformers hide reasoning before producing filler tokens?. So the surface program isn't always the actual computation.

What closes the gap is giving the architecture the machinery a general algorithm needs. Looped, recurrent-depth transformers with shared weights achieve compositional generalization and depth extrapolation vanilla ones cannot, emerging through a sharp memorize→in-distribution→out-of-distribution grokking transition Can looped transformers generalize to unseen knowledge combinations?. Hierarchical dual-recurrence escapes the fixed-depth AC0/TC0 ceiling to solve Sudoku and mazes where chain-of-thought fails outright Can recurrent hierarchies achieve reasoning that transformers cannot?. Adding an explicit stack tape buys 3–5x more sample-efficient recursive-syntax learning Can explicit stack tracking improve how transformers learn recursive syntax?. And transformers can even bootstrap themselves into true algorithmic generalization — self-training on their own filtered-correct solutions carries 10-digit addition to 100 digits Can transformers improve exponentially by learning from their own correct solutions?. The through-line: program synthesis is where transformers-as-general-computers stops being a proof-of-existence and becomes something you can either extract, engineer, or train into being.