For six decades, computer scientists have treated a single result as gospel: finding the shortest program that produces a given sequence of numbers is, in general, uncomputable. That result, rooted in the work of Ray Solomonoff, Andrey Kolmogorov, and Gregory Chaitin in the 1960s, is correct. But a 2026 paper argues that the field has drawn the wrong lesson from it. The uncomputability of the shortest program is not a wall around finding any program at all — it is a price, and it can be measured.
The paper, available as [arXiv:2606.13799] and dated 11 June 2026, introduces what its authors call a conservation law for program discovery. The claim is precise enough to test: for any algorithm that learns about a candidate program only by asking for its score, there is a worst-case lower bound on the search cost, exponential in a quantity called the coupling width. That lower bound matches, in the limit, an upper bound proved by Leonid Levin in 1973, closing a gap that has been open since the field's earliest days.
The Core Finding
The authors define a class of algorithms that includes Levin's universal search, evolutionary methods, simulated annealing, and the cross-entropy method. What unites them is that they treat every candidate program as a black box and ask only one question: what does it output, and how well does that match the target sequence. For this entire class, the paper proves that the worst-case cost of finding a hidden program is exponential in the coupling width of the search problem, with the base of the exponent being one less than the size of the domain. The coupling width measures, roughly, how entangled a program's inputs and outputs are.
The conservation law that follows is intuitive once stated. As the abstract puts it:
structural knowledge injected into a search trades one for one against the search it removes, and their sum can never fall below the length of the program sought.In other words, the only way to escape the exponential cost is to abandon score-only search and instead inspect the structure of candidates directly. The price of that escape, the authors prove for generic targets, is incompleteness — a structural impossibility theorem in the spirit of Gödel.
Think of it like searching for a specific book in a library. If all you can do is ask each book whether it is the right one, and many books could plausibly say yes, you might have to check an enormous fraction of them. But if you can read the spines and use the table of contents to rule out whole sections at once, you can search much faster. The conservation law says: the total amount of book knowledge plus shelf-by-shelf searching is fixed, and it cannot be smaller than the length of the title you are looking for.
The empirical engine built on this theory is concrete. Across four independent populations of sequences totaling 3,914, a deterministic algorithm recovered a generating program, certified by compression and by predicting an unseen continuation, in 2,383 cases — a 60.9% success rate. In the most structured population, elementary cellular automata, the engine succeeded on 244 of 256 rules. The measured discovery cost rose with program length by more than an order of magnitude, but stayed well inside the worst-case bound.
The State of the Field
The upper-bound side of this conservation law is Levin's 1973 theorem, which showed that if you know the exact length of the hidden program, you can find it in time exponential in that length. For more than fifty years, the matching lower bound was missing. Solomonoff's 1964 induction, Kolmogorov's 1965 complexity definition, and Chaitin's 1969 incompleteness work all shaped the intuition, but none pinned down how hard score-only search must be. The new paper closes that gap by introducing coupling width as the right measure of structural entanglement and by proving the lower bound unconditionally.
The broader algorithmic-information-theory landscape has been unusually active. Work on minimum description length, on the resource bounds of Solomonoff induction, and on practical applications of Levin search to program synthesis has accumulated. What was missing was a quantity that tied all of these together. The conservation law, if it holds up to scrutiny, does exactly that: it reframes a half-century of results as the two ends of one conserved quantity.
From Lab to Reality
For researchers in algorithmic information theory and theoretical machine learning, the result is a target. The lower bound is unconditional, so the open questions are about tightness: for which families of targets does the lower bound match Levin's upper bound exactly, and for which does structural inspection help beyond what the conservation law predicts? The incompleteness result for structural-search methods opens a new line of work analogous to Rice's theorem in computability theory.
For practitioners, the empirical engine is the most immediately useful artifact. A 60.9% success rate across 3,914 sequences, with full certification of each discovered program, is a benchmark that program-synthesis systems can be measured against. The elementary-cellular-automata result is especially striking: 244 of 256 rules is close to exhaustive, and the 12 failures are themselves a dataset for studying where the engine's heuristics break down.
For product teams, the relevance is direct. The same conservation law applies to any domain where you search for a generating rule by its outputs: model recovery in scientific machine learning, program synthesis in automated reasoning, and interpretability in large neural models. Companies building tools for AI safety, automated discovery, and scientific simulation all sit in the path this work illuminates. The market for automated scientific discovery has been projected by several consultancies to grow into the multi-billion-dollar range by the early 2030s, though figures specific to program-discovery engines are not yet available.
What Still Needs to Happen
Two technical challenges stand between this conservation law and a finished theory. The first is tightness: the lower bound is proved for a specific class of score-only algorithms, and extending it to algorithms with limited structural access — for example, those that can evaluate partial programs — is open. The second is the incompleteness theorem for structural search. The paper proves it for generic targets, but the precise boundary at which structural inspection stops helping is not yet characterized. Groups working on related questions include the algorithmic-randomness community around the University of Heidelberg, the Levin-search program at IDSIA in Lugano, and complex-systems groups at the Santa Fe Institute.
The paper is not yet peer-reviewed, and no replication has appeared. The 2,383-of-3,914 figure is impressive, but until the engine's code is released and tested on held-out populations, the result is a strong claim rather than a settled one. If the conservation law survives scrutiny, the practical consequences will take years to develop. A realistic horizon for the first commercial program-discovery engines built on this foundation is the late 2020s, not next year.
In Short
In short: program discovery obeys a conservation law in which structural knowledge and brute-force search sum to at least the length of the program being sought, and a 2026 paper proves the lower bound that completes the picture first sketched by Levin in 1973.
FAQ
Q: What is the conservation law for program discovery?
It is a theorem stating that the amount of structural knowledge you inject into a search for a hidden program, plus the amount of brute-force search you still have to perform, can never be less than the length of the program itself. It is a lower bound on the combined cost of knowing and searching, and it holds for any algorithm that evaluates candidates only by their output score.
Q: How does the coupling width work?
The coupling width measures how entangled a program's inputs and outputs are — essentially, how much you can rule out a candidate by changing one input. Programs with low coupling width are easy to find. Programs with high coupling width force any score-only search to pay an exponential cost, with the base of the exponent equal to one less than the domain size.
Q: How does this compare to Levin's 1973 result?
Levin's result gave an upper bound: if you know the exact length of the hidden program, you can find it in time exponential in that length. The 2026 paper gives a matching lower bound for the broader class of score-only algorithms, closing a 53-year gap and turning two loose ends of the same story into the two ends of a single conserved quantity.
Q: When could this be commercially relevant?
The empirical engine is already a working tool, and the benchmark it sets — 2,383 of 3,914 sequences certified — is immediately usable for program-synthesis research. Broader commercial impact, in automated discovery and AI interpretability, is plausible on a three-to-five-year horizon, with first products likely to appear in the late 2020s.
Q: Which industries would benefit most?
Automated scientific discovery, AI safety and interpretability, and program synthesis for automated reasoning. The conservation law itself is a theoretical result, but the engine that operationalizes it has direct applications in any setting where you need to recover a generating rule from its outputs.
Q: What are the current limitations of this research?
The paper has not yet been peer-reviewed, the engine's code has not been released, and the lower bound is proved only for score-only algorithms. The incompleteness result for structural search is established for generic targets, not all targets, leaving a precise boundary yet to be drawn. Independent replication on held-out sequence populations is the immediate next step.