arXiv:2606.13799 · v2
The program is still there, and searching for it obeys a conservation law
摘要
The length of the shortest program that generates a sequence, its Kolmogorov complexity, is uncomputable, so we ask what finding a short program costs when one exists. Many search algorithms, including Levin search, evolutionary methods, simulated annealing and the cross-entropy method, learn about a candidate program only through its score, how much of the sequence it reproduces. For such algorithms we define the coupling width of a search problem, the largest number of program fields that must change together before the score moves. We prove an unconditional worst-case lower bound on the number of candidates scored, exponential in that width. Under stated conditions, a conservation law follows, in which each bit of structural knowledge injected into a search removes at most one bit of search. The structure plus the logarithm of the remaining search is at least a fixed fraction of the sequence's Kolmogorov complexity. That fraction tends to one as the instruction set grows, so the lower bound approaches Levin's 1973 upper bound, apart from the program's running time. Search by score must pay this cost to be complete. We prove that our engine's structural inference avoids it only by giving up coverage, as does, if one-way functions exist, every method that runs in polynomial time. Our deterministic engine, built on this theory, recovers a generating program, certified by compressing its data and predicting an unseen continuation, for 2,383 of 3,914 candidate sequences in four populations of integer sequences and cellular automata, including the chaotic Rule 30.
作者备注：v2 revised throughout and retitled. 8 pages and 3 figures, with the SI Appendix (40 pages) appended. Code and data at https://github.com/jorgeMFS/omnis, archived at https://doi.org/10.5281/zenodo.23863377