arXiv cs.AI: Sergey Salishev on bounded halting and universal machines

arXiv cs.AI: Sergey Salishev on bounded halting and universal machines

In his paper, Sergey Salishev frames bounded halting—the question of whether a program halts within a specified step budget—as an engineering problem. He defines an exact finite-budget setting where the simulated program and checker share a unit-cost timescale, allowing the checker to be embedded in an adversarial program. Salishev says a diagonal argument with explicit additive overhead shows that no fixed deterministic checker decides every instance within any fixed fraction of the budget below one, for large budgets. In the nondeterministic case, the budget limits branch depth for a stable observable decision. The paper also uses bounded-halting instances as adversarial tests for finitary universality: a model’s ability to support arbitrary finite computations as the budget grows. The tests examine resource growth, whether there is a fixed deliberation bound, and later access to intermediate data. They distinguish a fixed model with extendable external resources, a model family that grows with the budget, and a larger system built around a fixed component. For machine-learning systems, Salishev says the analysis identifies the resource growth a universality claim assumes and whether it fails for deployed models. The supplied abstract describes these claims but does not provide the proof details.

Publication: 732b84a5-5c4e-4f1c-8b03-1a046ecd51fe

attribution — pass: The reading correctly credits the paper to Sergey Salishev on arXiv and frames the findings as his claims ("Salishev says"). It does not present them as established fact.

Authors:Sergey Salishev

summary — uncertain: The summary closely follows the abstract, but its central passages stay opaque to a non-specialist. It never explains the unbounded halting problem. Terms like 'unit-cost timescale', 'diagonal argument with explicit additive overhead', 'deterministic checker' and 'stable observable decision' are left unexplained; they should be kept exactly but given term-library tooltips. The key result is also not put plainly: roughly, no fixed checker can reliably decide every case while using a fixed fraction of T below one, for large T. Smallest repair: one plain-language framing sentence on why bounded halting tests universality claims for ML models, plus tooltips. The question itself is reasonable.

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.

date — pass: The originalPublished date of 2026-11-04 matches the v1 submission date on the arXiv page. The journal reference does not indicate an earlier first publication within the evidence.

[Submitted on 4 Nov 2026]

support — pass: Each claim matches the abstract and carries a verbatim excerpt. The limitation correctly notes that proof details are absent. The question about separating a deployed model's limits from those of a surrounding system follows from the source's own three-way distinction and assumes no unsupported benefits or costs.

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.

media — pass: The selected media is the verified direct arXiv abstract page for this paper. It is the most direct access point to the source.