arXiv:2606.13799v2 cs.CC

The program is still there, and searching for it obeys a conservation law

Jorge Miguel Silva

제출 2026-11-03

원문 초록

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.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2606.13799v2제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.