The Computational Boundary of Inference: Capability Internalization, Training, and the Turing Jump

• URL: http://arxiv.org/abs/2605.27381v1
• Date: Thu, 09 Apr 2026 22:56:56 GMT
• Title: The Computational Boundary of Inference: Capability Internalization, Training, and the Turing Jump
• Abstract summary: This paper gives a formal separation result in classical computability theory.<n>We prove that finite internal self-modification remains inside $mathcalC(A)$, while stabilized revision is governed by the jump $A'$ via the relativized limit lemma.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Claims about recursive self-improvement in AI often slide from repeated internal revision to the possibility of qualitatively stronger capability without clearly distinguishing the underlying computational regimes. This paper gives a formal separation result in classical computability theory that blocks that move under a precise modeling assumption. For an oracle $A$, let $\mathcal{C}(A)=\{B : B \leq_T A\}$ be the corresponding computational layer. We prove that finite internal self-modification remains inside $\mathcal{C}(A)$, while stabilized revision is governed instead by the jump $A'$ via the relativized limit lemma. Together with a local closure versus escape theorem, this yields a clean formal separation between within-layer iteration and ascent to a stronger relative level. The point is not that stronger layers never arise, but that they are not explained by finite repetition inside one already settled layer. The resulting separation gives a computability-theoretic limit on a broad class of recursive-improvement narratives in which repeated internal updating is treated as sufficient for qualitative capability ascent.

Related papers

• The Semantic Elevation Operator and the Closure of the Undecidable Class under Preservation [0.0]
  Self-modifying systems require analysing not whether a property holds now, but whether it is preserved when the system rewrites itself.<n>We formalise this transition through a semantic elevation operator, which turns the static question "does x satisfy P?" into the dynamic question "is P preserved after x is transformed by?"<n>We prove that when is intensional, the elevated property remains undecidable even though it breaks the extensionality that Rice's theorem requires.
  arXiv  Detail & Related papers  (2026-09-10T09:56:17Z)
• Think Wider: Mitigating Latent Rank Collapse in Implicit Chain-of-Thought Reasoning [3.216436532980238]
  Chain-of-thought (CoT) reasoning improves the reasoning ability of large language models by introducing intermediate computation.<n>However, explicit rationales increase decoding length, latency, and context cost.<n>Implicit CoT offers a more efficient alternative by moving intermediate reasoning into continuous latent states.
  arXiv  Detail & Related papers  (2026-09-07T12:18:51Z)
• Simplex Relaxation for Discrete Diffusion [58.33696160279345]
  We introduce Simplax, an exact Dirichlet--categorical augmentation that couples each corrupted categorical state with an auxiliary simplex-valued variable.<n>Simplax improves the generative perplexity--entropy tradeoff on unconditional OpenWebText generation.
  arXiv  Detail & Related papers  (2026-08-11T07:58:17Z)
• A Compositional Theory of Causally Masked Transformers [50.88598486616582]
  We develop a formalization that derives expressivity directly from the model's implemented dynamics.<n>Each attention head updates its own state independently within a layer.<n>A modified form of soft attention supports irreversible, checklist-like state.
  arXiv  Detail & Related papers  (2026-07-29T14:47:19Z)
• Generative Recursive Reasoning [67.22973831501257]
  Generative Recursive reAsoning Models (GRAM) is a framework that turns latent reasoning into probabilistic multi-trajectory.<n>GRAM supports conditional reasoning via $p_(y mid x)$ and, with fixed or absent inputs, unconditional generation via $p_(x)$.
  arXiv  Detail & Related papers  (2026-05-19T05:20:56Z)
• Strategic PAC Learnability via Geometric Definability [69.34283267701421]
  Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision.<n>A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations.<n>We introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over $mathbbR_mathttexp$.<n>We prove that learnability is preserved, with sample complexity controlled by the complexity
  arXiv  Detail & Related papers  (2026-05-13T12:21:56Z)
• Exact Structural Abstraction and Tractability Limits [0.0]
  Exact correctness depends only on the induced classes $s sim_R simation' iff mathrmAdm_R(s)$.<n>Decision, search, approximation, statistical, randomized horizon, and distributional guarantees all reduce to this same quotient-recovery problem.
  arXiv  Detail & Related papers  (2026-04-08T17:59:47Z)
• Circuit Complexity of Hierarchical Knowledge Tracing and Implications for Log-Precision Transformers [2.688207424884465]
  Empirically, transformer encoders trained on recursion-invariant trees converge to permutation-invariant shortcuts.<n>These findings motivate structure-aware objectives and iterative mechanisms for prerequisite-sensitive knowledge tracing on deep hierarchies.
  arXiv  Detail & Related papers  (2026-03-25T01:10:42Z)
• Latent Chain-of-Thought? Decoding the Depth-Recurrent Transformer [0.8738725605667471]
  Chain-of-thought (CoT) reasoning has enabled transformer-based language models to excel at complex mathematics and multi-step planning.<n>In standard decoder-only architectures, these reasoning steps are externalized in natural language, improving interpretability at the cost of efficiency.<n>We investigate whether such reasoning structures emerge in Huginn-3.5B, a depth-recurrent Transformer that reuses layers at inference time without increasing parameter count.
  arXiv  Detail & Related papers  (2025-07-02T23:35:21Z)
• Efficient Computation of Counterfactual Bounds [44.4263314637532]
  We compute exact counterfactual bounds via algorithms for credal nets on a subclass of structural causal models. We evaluate their accuracy by providing credible intervals on the quality of the approximation.
  arXiv  Detail & Related papers  (2023-07-17T07:59:47Z)
• Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
  We show that Adam converges to $epsilon$-stationary points with $O(epsilon-4)$ gradient complexity under far more realistic conditions. We also propose a variance-reduced version of Adam with an accelerated gradient complexity of $O(epsilon-3)$.
  arXiv  Detail & Related papers  (2023-04-27T06:27:37Z)
• A Formal Hierarchy of RNN Architectures [88.38859874233944]
  hierarchy is based on two formal properties: space, which measures the RNN's memory, and rational recurrence, defined as whether the recurrent update can be described by a weighted finite-state machine. We show how these models' expressive capacity is expanded by stacking multiple layers or composing them with different pooling functions. We hypothesize that the practical learnable capacity of unsaturated RNNs obeys a similar hierarchy.
  arXiv  Detail & Related papers  (2020-04-18T00:57:54Z)

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.