論文の概要: The Program Is Still There: A Conservation Law for Program Discovery

• arxiv url: http://arxiv.org/abs/2606.13799v1
• Date: Thu, 11 Jun 2026 18:11:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-15 16:00:42.566271
• Title: The Program Is Still There: A Conservation Law for Program Discovery
• Title（参考訳）: プログラム発見のための保存法
• Authors: Jorge Miguel Silva,
• Abstract要約: シーケンスを生成する最も短いプログラムを見つけることは計算不可能であり、60年間、その事実は生成プログラムを見つけるための壁と誤解されてきた。 非条件の最悪の場合、その幅で指数関数的な境界を証明し、ベース1をドメインサイズより小さくする。 この理論に基づいて構築された決定論的エンジンは、そのデータを圧縮し、目に見えない継続を予測することで認定された生成プログラムを回復する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: シーケンスを生成する最も短いプログラムを見つけることは計算不可能であり、60年間、その事実は生成プログラムを見つけるための壁と誤解されてきた。 壁ではなく価格であり、この論文はそれを計測する。 対象プログラムのスコア,レヴィン探索にまたがるクラス,進化的手法,擬似アニール法,およびクロスエントロピー法についてのみ学習するアルゴリズムについて,探索問題の結合幅を定義し,その幅がドメインサイズより小さいような非条件の最悪の下界を指数的に証明する。 検索に注入された構造的知識は、取り除く検索に対して1対1で1対1で取引され、その総和は、検索されたプログラムの長さを下回ることはない。 レヴィンの1973年の上限とここで証明された下限は、1つの保存された量の2つの端であり、命令セットが大きくなるにつれて互いに閉じる。 唯一の回避策は、そのスコアよりも候補者の構造を読むことであり、一般的なターゲットに対して証明される価格が不完全であることである。 この理論に基づいて構築された決定論的エンジンは、256個の基本セルオートマタの244個を含む4つの独立した集団の3,914個の配列のうち2,383個に対して、そのデータを圧縮し、目に見えない連続を予測して認定された生成プログラムを回復する。

関連論文リスト

• The Deterministic Horizon: Impossibility Results as Design Specifications for Trustworthy AI Systems [0.0]
  この論文は、好奇心から不合理性の結果を設計規則に変える。 そのフラッグシップとなる結果は、アーキテクチャだけで設定された精度の高い天井を証明している。 同じ引数がサブフィールドにまたがって再キャストされる。
  論文  参考訳（メタデータ） (2026-05-21T20:48:35Z)
• Grover Adaptive Search with Problem-Specific State Preparation [0.0345923194452408]
  我々は,バッテッチとエーデンベンツの以前の研究に基づいて,旅行販売問題のための国家準備ルーチンを構築した。 イテレーションでは、数回のイテレーションだけで妥当な近似比を達成することを目指しています。
  論文  参考訳（メタデータ） (2026-02-09T09:21:04Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  クローンゲーム解析のための新しいツールキットを提案する。 このフレームワークにより、バイナリフェーズ状態に基づいて新しいクローンゲームを分析することができる。 連成位相の変分最適境界は、ブラックホールの理想化されたモデルで衝突する情報について定量的な洞察を与えることを示す。
  論文  参考訳（メタデータ） (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)は、与えられた文字列の集合に属するすべての列から最小距離の文字列を見つけることを目的としたNPハード問題である。 本稿では,次の3段階のアルゴリズムを提案する。まず,検索領域を効果的に見つけるために,検索空間を削減するために,新しいアルファベットプルーニング手法を適用する。 第二に、解を見つけるためのビーム探索の変種を用いる。この方法は、部分解の期待距離スコアに基づいて、新たに開発された誘導関数を利用する。
  論文  参考訳（メタデータ） (2024-07-17T21:26:27Z)
• Recursive Causal Discovery [22.56309301911757]
  因果発見は、しばしば因果効果の同定と推定に向けた第一歩である。 この論文は、我々の以前の4つの出版物の上に構築され、拡張されている。 本稿では,提案アルゴリズムの統一的なフレームワークについて述べる。
  論文  参考訳（メタデータ） (2024-03-14T11:46:25Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• NAPG: Non-Autoregressive Program Generation for Hybrid Tabular-Textual Question Answering [52.10214317661547]
  現在の数値推論法はプログラムシーケンスを自己回帰的にデコードする。 プログラム生成の精度は、デコードステップがエラー伝搬によって展開されるにつれて急激に低下する。 本稿では,非自己回帰型プログラム生成フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-11-07T11:25:21Z)
• A Non-monotonic Self-terminating Language Model [62.93465126911921]
  本稿では,不完全復号アルゴリズムによる非終端列の問題に焦点をあてる。 まず、グリーディ探索、トップ$kのサンプリング、核サンプリングを含む不完全確率復号アルゴリズムを定義する。 次に,単調な終端確率の制約を緩和する非単調な自己終端言語モデルを提案する。
  論文  参考訳（メタデータ） (2022-10-03T00:28:44Z)
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination [82.52105963476703]
  統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。 1次保証は統計的およびオンライン学習において比較的よく理解されている。 三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
  論文  参考訳（メタデータ） (2021-07-05T19:20:34Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。