The gap between knowing of something and knowing how to do it was the focus of a talk by Dale Schuurmans, research scientist at Google DeepMind and professor at the University of Alberta, delivered during the “New Directions in Reinforcement Learning and Control” workshop that was part of IMSI's Long Program on “Theoretical Advances in Reinforcement Learning and Control,” March 9 - May 29, 2026. Schuurmans used the example of Dijkstra's algorithm, a classical method for finding the shortest path through a weighted graph by systematically expanding the least costly frontier. Ask a large language model (LLM) to explain Dijkstra's algorithm and it will give you a fluent, accurate account. Ask it to actually execute that algorithm on a new graph, tracing every step in the correct sequence to a provably correct answer, and something must eventually go wrong for sufficiently large graphs. The model knows the algorithm in a similar way that a student knows a theorem they can recite, but not prove. In his talk, Schuurman's argued that: a) this gap has a rigorous computational explanation; b) the standard tools used to close it are structurally incapable of doing so; and c) reinforcement learning, the technique most commonly invoked as the fix, is largely being applied in ways that cannot work.

Reinforcement learning is a mathematical framework for training systems to make sequential decisions by optimizing for cumulative reward, rather than by imitating a fixed set of labeled examples. In standard supervised learning, a model is shown correct input-output pairs and then trained to reproduce them. Reinforcement learning lets a model generate its own attempts, then adjusts the model to favor attempts that receive higher scores. Applied to LLMs, this technique is used in a phase called post-training: after a model has been trained on a large body of data or text, reinforcement learning fine-tunes and steers its outputs toward specific prompt-driven objectives such as mathematical reasoning, instruction-following, or code generation. The most widely used approach is policy gradient. A policy gradient is a family of algorithms that samples sequences of tokens (the basic units of text a LLM works with, roughly corresponding to words or word fragments) from the model's own outputs, evaluates each sequence against a reward function (a scoring rule that measures how well an output achieves the desired goal), and adjusts the model's parameters to make higher-reward sequences more probable. A competing class of methods, called value-based reinforcement learning, tries to estimate the long-run worth of a given state in order to guide decisions. As Schuurmans explained, value-based approaches have largely been abandoned for LLMs, for reasons that turn out to be fundamental rather than practical.

Schuurmans began his talk by explaining what has changed in artificial intelligence. Classical machine learning assumed that for every problem, one can find a model that solves it. A specific solution is fitted to each new problem. Large language models invert this. We now have a single general model expected to solve a wide range of problems on demand. And this is precisely the structure of classical computer science: a fixed algorithm applied to arbitrary instances. Schuurmans argued that this implies that if LLMs operate as universal algorithms, then the laws of computation developed over decades in theoretical computer science apply to them. Ignoring those laws helps explain why so many puzzles about LLM behavior remain unresolved.

Whether LLMs actually qualify as universal computers turns out to be a question with a precise answer. A standard transformer-based model — one built on the architecture that underlies most modern AI systems, which processes text by learning which parts of its input to pay attention to — operating alone, cannot be a universal computer because it processes bounded inputs and produces bounded outputs, which rules out handling arbitrarily large problems. But a LLM paired with chain-of-thought reasoning, where the model emits intermediate steps that are appended to its context before the next step, can in principle process inputs of any size. In recent work, Schuurmans and his colleagues made this rigorous: a context window of just two symbols is sufficient to simulate any Turing machine. The simulation was verified on Meta's large mixture-of-experts language model with 17 billion active parameters drawn from a pool of 128 specialized sub-networks. This model was given the full 1,857 rules for a universal Turing machine as a 13,000-token system prompt and reproduced them with zero errors across all 1,857 cases, establishing Turing completeness for a production LLM. A subsequent result showed that even a randomly initialized transformer that has never been trained on text is computationally universal. Language training does not grant models their computational power. Rather, it adapts that power to be understandable to humans.

These results carry an immediate implication for training. The same laws that describe what computers can compute also describe what a training procedure can teach a model to do. Schuurmans made this concrete with experiments on propositional logic problems, which reduce to reachability on a directed graph. When models were given demonstrations of correct reasoning that followed the computational sequence the task requires, performance improved substantially, reaching around 90 percent accuracy. When given demonstrations in scrambled order (every step individually correct, but computationally non-sequential) performance collapsed to chance. The model could mimic the surface appearance of reasoning without executing the underlying computation. The same impossibility applies more broadly to supervised fine-tuning on path-finding tasks. For example, finding an optimal first move requires a computation whose cost scales with the size of the graph, while a transformer forward pass delivers a constant computational budget regardless of problem size. A model trained this way learns to produce plausible-looking moves rather than optimal ones.

This is where reinforcement learning enters, and where Schuurmans's critique became most pointed. Policy gradient methods have the structural advantage that because the model generates its own training trajectories, there are no computational gaps baked into the demonstrations. This advantage is real and explains measurable gains on reasoning benchmarks. But the gains come with a structural limitation. Policy gradient converges to a deterministic solution with probability 1, and the expected time to find an optimal solution is unbounded. The characteristic pattern seen in practice — gradual accuracy improvement followed by plateau and collapse — is universally diagnosed as a failure of exploration because the policy has become too deterministic and stopped searching. The standard response has been a succession of methods that attempt to restore diversity by adding noise to the policy distribution. Proximal policy optimization, the foundational method, stabilizes training by keeping policy updates within a bounded region. Group relative policy optimization eliminates a separate value-estimating model and instead compares a group of candidate outputs against each other. Subsequent methods further tune how aggressively the training clips or reweights candidate outputs. Schuurmans argued this entire progression misdiagnoses the problem. When the center of mass of the policy distribution drifts away from the region of correct solutions, adding noise does not move the center; it widens the spread of a random walk pointed in the wrong direction.

Value-based reinforcement learning fails for a related but distinct reason. Estimating the long-run value of a given state in a reasoning chain requires solving a dynamic program whose cost scales super-linearly with the remaining problem. Approximating this value with a single transformer forward pass applies a constant computational budget to a super-linear problem, producing estimates that are inconsistent with any realizable policy. This causes value-based methods to degrade systematically when applied to generalist models across diverse tasks.

What would actually close the gap? Schuurmans offered two directions, both speculative and both unresolved. First, algorithms generalize precisely because they are compressions: a finite description that correctly handles an infinite class of instances. Standard chain-of-thought reasoning allocates new memory for every emitted token, with no reuse across steps. Learning to reuse and address memory sparsely, as classical algorithms do, may be necessary for genuine generalization. Second, the reinforcement learning objective itself may need revision. Current approaches penalize long reasoning chains, but length is not the problem. Rather, redundancy is. A training signal that penalizes the gap between a full reasoning chain and its minimal compressed equivalent, without penalizing length, might select for real compression rather than surface imitation.

The IMSI workshop brought together mathematicians, computer scientists, and machine learning researchers, communities that rarely occupy the same room long enough to have this kind of exchange. Schuurmans's talk made visible something that gets obscured in benchmark-driven research: that apparent capability gaps in language models are not always empirical puzzles to be solved with more data and better prompts. Some have the structure of mathematically impossible results. Understanding which limitations are fundamental and which are merely engineering problems not yet solved requires exactly the kind of interdisciplinary dialogue that IMSI was designed to enable. "The problems are clear," Schuurmans acknowledged. "The solutions are not. They're at the intersection of machine learning and computer science, and we need help."