The Program Is Still There: A Conservation Law for Program Discovery

• URL: http://arxiv.org/abs/2606.13799v1
• Date: Thu, 11 Jun 2026 18:11:49 GMT
• Title: The Program Is Still There: A Conservation Law for Program Discovery
• Abstract summary: 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.<n>We prove an unconditional worst-case lower bound, exponential in that width with base one less than the domain size.<n>A deterministic engine built on this theory recovers a generating program, certified by compressing its data and predicting an unseen continuation.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• FaultLens: Learning Compact Behavioral Test Suites for Generated Operational Programs [13.55424508650495]
  FaultLens is a method for learning compact behavioral test suites while preserving an auditable connection to executed evidence.<n>It executes a rich probe domain once, stores the fault-probe kill relation as a sparse outcome cache, and learns probe orderings only from earlier program generations.<n>We evaluate twenty generated operational policies across four environments, ten execution seeds, 1,200 measured run summaries, 2,160 controlled program transformations, and 4,120,200 executed program-probe pairs.
  arXiv  Detail & Related papers  (2026-08-27T07:37:28Z)
• The Time-Space Complexity of Checking Multiple Assertions in Quantum Programs [0.5524804393257919]
  checking a quantum program that contains multiple assertions often requires using additional space or running the program additional times.<n>For a program with $n$ assertions, a naive strategy uses $n$ ancillas to learn all $n$ outcomes.<n>An alternative uses one ancilla but repeats program execution over $n$ rounds, checking one assertion per round.
  arXiv  Detail & Related papers  (2026-07-13T15:09:04Z)
• Piercing Gilbreath's Conjecture: From Deep Number Theory Insights to Fintech and Cybersecurity [0.0]
  Gilbreath's conjecture about prime numbers was first posted in 1878 and unsolved to this day.<n>I propose a new methodology to attack the fascinating Gilbreath's conjecture about prime numbers, first posted in 1878 and unsolved to this day.<n>This paper changes the game by presenting a new approach based on sieving, a number of new results with proof, a precise path to the solution, and solid references.
  arXiv  Detail & Related papers  (2026-07-05T08:09:25Z)
• The Deterministic Horizon: Impossibility Results as Design Specifications for Trustworthy AI Systems [0.0]
  This thesis turns impossibility results from curiosities into design rules.<n>Its flagship result proves an accuracy ceiling set by architecture alone.<n>The same argument recasts across subfields.
  arXiv  Detail & Related papers  (2026-05-21T20:48:35Z)
• Grover Adaptive Search with Problem-Specific State Preparation [0.0345923194452408]
  We build upon previous work by Baertschi and Eidenbenz to construct a state preparation routine for the Traveling Salesperson Problem.<n>With our iterations, we aim to achieve a reasonable approximation ratio with only a number of iterations.
  arXiv  Detail & Related papers  (2026-02-09T09:21:04Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  We propose two algorithms that enjoy provable scaling laws for the test-time compute of large language models.<n>One is a two-stage knockout-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.<n>The other is a two-stage league-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  We introduce a new toolkit for analyzing cloning games.<n>This framework allows us to analyze a new cloning game based on binary phase states.<n>We show that the binary phase variantally optimal bound offers quantitative insights into information scrambling in idealized models of black holes.
  arXiv  Detail & Related papers  (2024-11-07T14:09:32Z)
• A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences [39.58317527488534]
  Closest String Problem is an NP-hard problem that aims to find a string that has the minimum distance from all sequences that belong to the given set of strings. In this paper, we introduce a three-stage algorithm that comprises the following process: first, we apply a novel alphabet pruning method to reduce the search space for effectively finding promising search regions. Second, a variant of beam search to find a solution is employed. This method utilizes a newly developed guiding function based on an expected distance score of partial solutions.
  arXiv  Detail & Related papers  (2024-07-17T21:26:27Z)
• Recursive Causal Discovery [22.56309301911757]
  Causal discovery is often the first step toward the identification and estimation of causal effects. This paper builds upon and extends four of our prior publications. We present a unified framework for the proposed algorithms, refined with additional details and enhancements for a coherent presentation.
  arXiv  Detail & Related papers  (2024-03-14T11:46:25Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  We study differentially private approximation algorithms for hierarchical clustering. We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset. We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
  arXiv  Detail & Related papers  (2023-01-31T19:14:30Z)
• NAPG: Non-Autoregressive Program Generation for Hybrid Tabular-Textual Question Answering [52.10214317661547]
  Current numerical reasoning methods autoregressively decode program sequences. The accuracy of program generation drops sharply as the decoding steps unfold due to error propagation. In this paper, we propose a non-autoregressive program generation framework.
  arXiv  Detail & Related papers  (2022-11-07T11:25:21Z)
• A Non-monotonic Self-terminating Language Model [62.93465126911921]
  In this paper, we focus on the problem of non-terminating sequences resulting from an incomplete decoding algorithm. We first define an incomplete probable decoding algorithm which includes greedy search, top-$k$ sampling, and nucleus sampling. We then propose a non-monotonic self-terminating language model, which relaxes the constraint of monotonically increasing termination probability.
  arXiv  Detail & Related papers  (2022-10-03T00:28:44Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination [82.52105963476703]
  A recurring theme in statistical learning, online learning, and beyond is that faster convergence rates are possible for problems with low noise. First-order guarantees are relatively well understood in statistical and online learning. We show that the logarithmic loss and an information-theoretic quantity called the triangular discrimination play a fundamental role in obtaining first-order guarantees.
  arXiv  Detail & Related papers  (2021-07-05T19:20:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.