論文の概要: An Engineering Reading of the Bounded Halting Problem and Observable Properties of a Universal Machine

• arxiv url: http://arxiv.org/abs/2611.06303v1
• Date: Wed, 04 Nov 2026 10:36:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 03:25:58.061094
• Title: An Engineering Reading of the Bounded Halting Problem and Observable Properties of a Universal Machine
• Title（参考訳）: 境界ハルティング問題の工学的読解とユニバーサルマシンの可観測特性
• Abstract要約: 停止問題は、プログラムが最終的に停止するかどうかを、制限のないリソースで問う。 本稿ではその2つの用途について研究する。 機械学習システムでは、リソース成長が普遍性の主張であり、それがデプロイされたモデルに失敗するかどうかを識別する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The halting problem asks whether a program eventually halts, with unrestricted resources. Engineering systems instead certify bounded halting: given a program, an input, and a step budget T, decide whether the program halts within T steps. This paper studies two of its uses. First, it defines an exact finite-budget problem, placing the simulated program and the checker on the same unit-cost timescale, so the checker can be embedded in an adversarial program. A diagonal argument with explicit additive overhead shows that no fixed deterministic checker decides every instance within any fixed fraction of T below one, for large T. In the nondeterministic case, T bounds the branch depth allowed for a stable observable decision. Second, bounded-halting instances give adversarial tests for finitary universality, since a universal model must support arbitrary finite computations as T grows. The tests check resource growth with T, the absence of a fixed deliberation bound, and later access to intermediate data. They separate a fixed model with extendable external resources, a model family that grows with T, and a larger system built around a fixed component. For machine-learning systems, this identifies the resource growth a universality claim assumes and whether it fails for deployed models.
• Abstract（参考訳）: 停止問題は、プログラムが最終的に停止するかどうかを無制限のリソースで問う。 プログラム、入力、ステップ予算Tが与えられた場合、プログラムがTステップ内で停止するかどうかを決定する。 本稿ではその2つの用途について研究する。 まず、シミュレーションプログラムとチェッカーを同じ単位コストのタイムスケールに配置し、そのチェッカーを逆プログラムに埋め込むという、正確な有限予算問題を定義する。 明示的な加法的オーバーヘッドを持つ対角論証は、大きな T に対して、固定決定論的チェッカーが 1 以下の任意の T の固定分数内のすべてのインスタンスを決定しないことを示し、非決定論的の場合、T は安定な可観測的決定のために許される分岐深さを制限している。 第2に、有界なハルティングのインスタンスは、T が成長するにつれて普遍モデルが任意の有限計算をサポートする必要があるため、有限普遍性に対する逆検定を与える。 テストは、Tによるリソース成長、固定された熟考境界の欠如、そして後に中間データへのアクセスをチェックする。 それらは、拡張可能な外部リソースを持つ固定モデルと、Tで成長するモデルファミリと、固定コンポーネントを中心に構築されたより大きなシステムとを分離する。 機械学習システムでは、リソース成長が普遍性の主張であり、それがデプロイされたモデルに失敗するかどうかを識別する。

関連論文リスト

• Harnessing LLMs as Agents: What Does It Cost? [34.501638251435715]
  言語モデルエージェントは、コンテキスト、永続メモリ、検証、繰り返し実行を管理するハーネスにますます依存している。 本稿では,言語モデルエージェントマシン(Language Model Agent Machine,LAM)を紹介する。
  論文  参考訳（メタデータ） (2026-10-01T21:05:49Z)
• Coupled Scaling: A Representational Accessibility Framework for Neural Scaling Laws [2.345146665577353]
  本稿では,有限予算スケーリングがタスク構造とアーキテクチャ最適化システムへのアクセス可能な幾何学との関係に依存するフレームワークであるCoupled Scalingを紹介する。 固定カーネルは、損失適合とは独立に定義されたタスク重み付きスペクトル測度の近ゼロテールからトレーニング時間指数を導出する。
  論文  参考訳（メタデータ） (2026-09-03T08:32:46Z)
• Search as Computation Allocation [52.080489413778]
  多くのアルゴリズムは、決定を返す前に内部リソースを使い、その端末出力の品質によってのみ評価される。 終端計算割当問題などの手順を定式化する。 ベルマン方程式は、固定予算の下での最適割り当て、価格計算、正確な認証を特徴付ける。
  論文  参考訳（メタデータ） (2026-07-30T08:45:14Z)
• When Does Recurrence Become an Algorithm? Convergence Selection in Weight-Tied Looped Transformers [17.78341274611665]
  重み付きループ変換器 -- 1ブロック適用T倍 -- はアルゴリズムを実装しているのか? 本研究は,集団語問題における制御人口の4つの結果から回答する。
  論文  参考訳（メタデータ） (2026-07-22T16:04:31Z)
• Generative Recursive Reasoning [67.22973831501257]
  Generative Recursive ReAsoning Models (GRAM) は、潜在的推論を確率論的多軌道に変換するフレームワークである。 GRAMは$p_(y mid x)$で条件推論をサポートし、固定または欠落した入力では$p_(x)$で条件生成を行う。
  論文  参考訳（メタデータ） (2026-05-19T05:20:56Z)
• Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing [52.124267908936396]
  このモデルは、$M$armと$K$playで構成されている。 各アームには複数の能力があり、各ユニットの能力は報酬関数に関連付けられている。 複数のプレーがアームキャパシティを競う場合、アームキャパシティは第1の優先重みで割り当てられる。
  論文  参考訳（メタデータ） (2025-12-25T11:19:09Z)
• Tractable Offline Learning of Regular Decision Processes [50.11277112628193]
  この研究は、正則決定過程(RDP)と呼ばれる非マルコフ環境のクラスにおけるオフライン強化学習(RL)を研究する。 インスは、未来の観測と過去の相互作用からの報酬の未知の依存を実験的に捉えることができる。 多くのアルゴリズムは、まずこの未知の依存関係を自動学習技術を用いて再構築する。
  論文  参考訳（メタデータ） (2024-09-04T14:26:58Z)
• Counterfactual inference in sequential experiments [17.817769460838665]
  複数の単位に複数の時間点に対する処理を割り当てるシーケンシャルな設計実験のアフタースタディ統計的推測を考察する。 我々のゴールは、最小限のスケールで、カウンターファクト平均に対する推論保証を提供することです。 我々は,いくつかのシミュレーションと,モバイル医療臨床試験HeartStepsのデータを含むケーススタディを通して,我々の理論を解説する。
  論文  参考訳（メタデータ） (2022-02-14T17:24:27Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  マルコフ決定過程(CMDP)に対するオンライン学習の検討 本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。 我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
  論文  参考訳（メタデータ） (2020-03-02T05:02:23Z)

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

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