What an AI universality claim must say about memory and time

A language model may produce a long answer, call tools or participate in an agent workflow. But which of those systems is being described when someone calls it a universal computer? Sergey Salishev of St. Petersburg State University argues that the answer depends on explicit rules for memory, execution time and access to earlier information.

His paper, An Engineering Reading of the Bounded Halting Problem and Observable Properties of a Universal Machine, was submitted to arXiv on November 4, 2026. The landing page also lists a journal reference in Cybernetics and Physics, volume 15, issue 2, pages 234–242. This account uses arXiv version 1; its extracted manuscript retains placeholder journal-header and acceptance-date fields. The work should therefore not be described simply as an unpublished preprint, nor do those placeholders establish its review history.

A deadline changes the question

The classical halting problem asks whether an arbitrary program eventually stops, without a time limit. No algorithm can answer that correctly for every program and input. Bounded halting instead supplies a deadline: does the program stop within T computational steps? The paper's formal predicate specifically asks whether it reaches an accepting state; other outcomes count as negative.

That finite question is decidable by simulation. Salishev asks whether one exact checker can always answer substantially sooner than the execution budget it is checking. His analysis is mathematical, not an evaluation of language models or a benchmark of verification software.

The central argument places checker and checked program on the same unit-cost transition scale. An adversarial program runs the checker on its own description, then contradicts the prediction: it accepts if the checker says it will not accept, and loops if the checker says it will. If the checker finishes early enough to leave time for that final action, either prediction becomes wrong.

Under the stated embedding and overhead assumptions, the paper derives a worst-case lower bound near T, allowing a fixed additive overhead c. Consequently, for sufficiently large budgets, an exact checker cannot answer every instance within a fixed fraction of T below one—for example, half the budget. This is a claim about all inputs under a fixed computational accounting model, not a measured wall-clock limit across different hardware.

Branching is not an automatic escape

For nondeterministic computation, the question becomes whether any branch accepts within depth T. A tree can have enormous width while each branch still has a sequential depth.

The paper's extension requires a particularly strong decision contract: every branch must finish within the limit and return the same correct bit. Restricting such a checker to deterministic inputs lets one follow a fixed branch, recovering the deterministic obstruction. This does not establish the same result for ordinary nondeterministic recognition, where one accepting branch suffices. Its randomized extension likewise concerns finite implementations with probability-one correctness and positive-probability branches, not methods allowed a failure rate.

Three checks on universality claims

The second contribution is a set of necessary resource checks. Can the available configuration space grow with the requested computation? Can execution continue without a fixed response bound? Can information produced earlier remain accessible when a later step needs it?

A closed deterministic system with a fixed finite configuration set eventually halts or repeats a configuration. Its halting behavior is therefore decidable in principle, although enumerating that set may be impractical. Unlimited running time alone does not solve the storage problem: repeatedly revisiting the same state permits an endless loop, not arbitrary computation.

Applied to Transformers, the distinction is between a fixed, finite-precision model with bounded context and an idealized construction whose resources can grow. Removing a generation-length cap supplies more execution time, but text outside the accessible context is not automatically usable memory. An external transcript matters only if later computation can actually address it.

The paper separates three arrangements: fixed computational rules with extendable storage, a model family whose precision or architecture grows, and a larger system built around a fixed component. External files, interpreters or agent coordination may change the capabilities of the combined system. They do not retroactively give those capabilities to the isolated neural network.

These checks can rule out universality; passing them is not a proof of it. A constructive simulation argument is still required. Nor does the worst-case checking bound rule out faster analysis of restricted programs, useful static shortcuts, approximate predictions or tools that return “unknown.” The practical lesson is narrower: specify the system boundary and resource-growth rules before treating theoretical universality as a property of a deployed AI system.