揭示程序发现中的能量守恒定律,证明结构知识与搜索代价的等价交换。
The Program Is Still There: A Conservation Law for Program Discovery

- 提出耦合宽度概念,量化搜索问题的不可约难度。
- 证明搜索代价指数级增长,与程序长度呈强相关性。
- 适用于进化算法、模拟退火等主流搜索方法,适合理论研究者。
寻找生成序列的最短程序是不可计算的,但这一事实并非不可逾越的障碍,而是一种代价。本文针对仅通过评分学习候选程序的算法(涵盖Levin搜索、进化方法、模拟退火和交叉熵法),定义了搜索问题的耦合宽度,并证明了一个无条件的最坏情况下界:该下界随耦合宽度指数增长,底数为领域大小减一。由此推导出一条守恒定律:注入的结构知识与所消除的搜索代价等价交换,二者之和永远不低于目标程序的长度。Levin 1973年的上界与本文证明的下界共同构成同一守恒量的两端,随着指令集增大而相互逼近。唯一突破路径是直接读取候选程序的结构而非其评分,但这代价是不完备性——对通用目标而言,我们已证明其不可避免。基于此理论构建的确定性引擎,在四个独立种群中成功恢复了2,383/3,914个序列的生成程序,包括244/256个初等元胞自动机,其发现成本随程序长度增加超过一个数量级,仍低于评分预言机的最坏情况。
原文摘要 · Abstract (English)
Finding the shortest program that generates a sequence is uncomputable, and for six decades that fact has been mistaken for a wall around finding any generating program. It is not a wall but a price, and this paper measures it. For every algorithm that learns about a candidate program only through its score, a class spanning Levin search, evolutionary methods, simulated annealing, and the cross-entropy method, we define the coupling width of a search problem and prove an unconditional worst-case lower bound, exponential in that width with base one less than the domain size. From it follows a conservation law: 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. Levin's 1973 upper bound and the lower bound proved here are the two ends of one conserved quantity, closing on each other as the instruction set grows. The only escape is to read a candidate's structure rather than its score, and its price, which we prove for generic targets, is incompleteness. A 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 sequences across four independent populations, including 244 of the 256 elementary cellular automata, with measured discovery cost rising along program length more than an order of magnitude inside the score-oracle worst case.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。