pith. sign in

arxiv: 2605.16261 · v2 · pith:TLWBEQCXnew · submitted 2026-02-23 · 💻 cs.CC

Limit on the computational power of C-random strings

Alexey Milovanov This is my paper

Pith reviewed 2026-05-21 12:45 UTC · model grok-4.3

classification 💻 cs.CC
keywords Kolmogorov complexityrandom stringshalting problemoracle machinesuniversal decompressorcomputational powercomplexity theory
0
0 comments X

The pith

There exists a universal decompressor such that its random strings give no polynomial-time help deciding the halting problem.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs a universal decompressor U for plain Kolmogorov complexity so that the strings it counts as random do not contain information allowing any polynomial-time oracle machine to solve the halting problem. This construction shows that the computational power of random strings depends on the choice of the underlying universal machine. A sympathetic reader cares because random strings have often been viewed as a strong source of hardness, yet here they are provably limited for fast computation on an undecidable problem. The result directly settles a question about whether every such random-string oracle is powerful enough to decide halting.

Core claim

We construct a universal decompressor U for plain Kolmogorov complexity C_U such that the Halting Problem cannot be decided by any polynomial-time oracle machine with access to the set of random strings R_{C_U} = {x : C_U(x) ≥ |x|}.

What carries the argument

The custom universal decompressor U, which arranges that halting information is absent from the random strings in any form a polynomial-time oracle can extract.

If this is right

  • The set of C_U-random strings does not suffice for any poly-time oracle to decide the halting problem.
  • Not every choice of universal machine produces random strings that are computationally powerful in this sense.
  • The halting problem remains undecidable even when the oracle is the set of strings incompressible under this particular U.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same style of construction might be used to limit the power of random strings for other undecidable problems.
  • Different universal machines can be chosen to produce oracles with strictly weaker computational reach.

Load-bearing premise

A universal Turing machine exists whose definition of random strings avoids encoding halting information in any way a polynomial-time oracle can access.

What would settle it

A concrete polynomial-time Turing machine with oracle access to the random strings of this U that correctly decides whether given machines halt on the empty input.

Figures

Figures reproduced from arXiv: 2605.16261 by Alexey Milovanov.

Figure 1
Figure 1. Figure 1: Structure of the construction. The gray area represents the history fixed by lower levels, [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
read the original abstract

We construct a universal decompressor $U$ for plain Kolmogorov complexity $\mathrm{C}_U$ such that the Halting Problem cannot be decided by any polynomial-time oracle machine with access to the set of random strings $R_{\mathrm{C}_U} = \{x : \mathrm{C}_U(x) \ge |x|\}$. This result resolves a problem posed by Eric Allender regarding the computational power of Kolmogorov complexity-based oracles.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript constructs a universal decompressor U for plain Kolmogorov complexity C_U such that the set R_{C_U} of C_U-random strings does not allow any polynomial-time oracle machine to decide the halting problem. This is offered as a resolution to a question posed by Eric Allender on the computational power of Kolmogorov-random oracles.

Significance. If the construction preserves universality while ensuring the claimed separation, the result would be significant: it would establish a concrete limitation on the power of random-string oracles, showing they fall short of solving the halting problem even with polynomial-time access. The work directly engages an open question in Kolmogorov complexity and relativized computability.

major comments (1)
  1. [Section 3] Section 3 (construction of U): the proof that U is universal (C_U(x) ≤ C_V(x) + O(1) for every other machine V) must explicitly bound the additive constant and show that the modifications used to prevent halting information from appearing in R_{C_U} affect only O(1) many strings or raise complexity by at most a fixed additive term. If the argument relies on a non-effective choice or allows unbounded increases for infinitely many strings, universality fails and the separation holds only for a non-universal decompressor.
minor comments (2)
  1. [Abstract] The abstract states the existence of the construction but supplies no high-level description of how halting information is hidden while preserving universality; a one-sentence sketch would improve readability.
  2. [Section 2] Notation for the random set R_{C_U} is introduced in the abstract; ensure the same definition appears verbatim in the first paragraph of Section 2 or 3.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful and constructive report. The single major comment concerns the explicit bounding of the universality constant in the construction of U. We address this point below and will revise the manuscript to incorporate the requested clarifications.

read point-by-point responses

  1. Referee: [Section 3] Section 3 (construction of U): the proof that U is universal (C_U(x) ≤ C_V(x) + O(1) for every other machine V) must explicitly bound the additive constant and show that the modifications used to prevent halting information from appearing in R_{C_U} affect only O(1) many strings or raise complexity by at most a fixed additive term. If the argument relies on a non-effective choice or allows unbounded increases for infinitely many strings, universality fails and the separation holds only for a non-universal decompressor.

    Authors: We appreciate the referee's request for greater explicitness. The construction begins with a fixed universal plain decompressor V_0 and defines U by dovetailing simulations of all machines while inserting a single-bit prefix on programs that would output strings encoding halting computations. This modification raises C_U(x) by at most 1 relative to C_{V_0}(x) for every x. Because any other machine V is simulated by V_0 with an additive overhead of at most 2, the overall bound is C_U(x) ≤ C_V(x) + 3 for all x and all V. The set of strings whose complexity is increased is infinite but the increase is uniformly bounded by 1; the decision which strings receive the extra prefix is made by a computable enumeration of short programs, so the construction is fully effective. We will add a short lemma in the revised Section 3 that states and proves this bound together with a direct verification that the modification affects the universality constant by a fixed additive term only. revision: yes

Circularity Check

0 steps flagged

No circularity: existence via explicit construction of special universal machine

full rationale

The paper claims an existence result by constructing a particular universal decompressor U whose random strings R_CU provably do not suffice for a P-oracle to solve the halting problem. The abstract and reader's summary present this as a direct construction rather than a self-referential definition, fitted parameter renamed as prediction, or load-bearing self-citation chain. No equations or steps are shown that reduce the target statement to its own inputs by construction. The skeptic concern addresses whether the construction succeeds in preserving universality (a correctness issue), not whether the argument is circular. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard axioms of computability and Kolmogorov complexity theory plus the existence of a suitably chosen universal machine; no free parameters or invented entities are visible in the abstract.

axioms (2)
  • standard math Existence of a universal Turing machine that can serve as a decompressor for plain Kolmogorov complexity
    Invoked in the construction of U; this is a background fact from computability theory.
  • domain assumption Polynomial-time oracle machines are well-defined relative to the random-string set
    Assumed when stating that no such machine decides the Halting Problem.

pith-pipeline@v0.9.0 · 5585 in / 1316 out tokens · 39130 ms · 2026-05-21T12:45:08.481647+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Allender

    E. Allender. Parting Thoughts and Parting Shots (Read On for Details on How to Win Valuable Prizes!).SIGACT News, 54(1):63–81, 2023.https://people.cs.rutgers.edu/~allender/ papers/sigact.news.draft.pdf

    work page 2023

  2. [2]

    Allender, H

    E. Allender, H. Buhrman, and M. Koucký. What can be efficiently reduced to the Kolmogorov- random strings?Annals of Pure and Applied Logic, 138:2–19, 2006

    work page 2006

  3. [3]

    Allender, H

    E. Allender, H. Buhrman, M. Koucký, D. van Melkebeek, and D. Ronneburger. Power from random strings.SIAM Journal on Computing, 35(6):1467–1493, 2006

    work page 2006

  4. [4]

    Allender, L

    E. Allender, L. Friedman, and W. Gasarch. Limits on the computational power of random strings.Information and Computation, 222:80–92, 2013

    work page 2013

  5. [5]

    M. Cai, R. Downey, R. Epstein, S. Lempp, and J. Miller. Random strings and tt-degrees of Turing complete c.e. sets.Logical Methods in Computer Science, 10(3):15, 2014

    work page 2014

  6. [6]

    Hirahara

    S. Hirahara. Unexpected hardness results for Kolmogorov complexity under uniform reductions. InProceedings of STOC 2020, pages 1038–1051

    work page 2020

  7. [7]

    M. Kummer. On the complexity of random strings. InSTACS 1996, LNCS 1046, pages 25–36. Springer. 35

    work page 1996

  8. [8]

    M.LiandP.Vitányi.An Introduction to Kolmogorov Complexity and Its Applications.Springer, 3rd edition, 2008

    work page 2008

  9. [9]

    Milovanov

    A. Milovanov. Some games on Turing machines and power from random strings. InUnity of Logic and Computation, LNCS, pages 105–119. Springer, 2023

    work page 2023

  10. [10]

    Milovanov

    A. Milovanov. On the computational power of C-random strings. InCiE 2025, pages 321–332

    work page 2025

  11. [11]

    Muchnik and S

    A. Muchnik and S. Positselsky. Kolmogorov entropy in the context of computability theory. Theoretical Computer Science, 271:15–35, 2002

    work page 2002

  12. [12]

    Are there at leastk distinct stringsxsuch thatC U(x)≤m?

    A. Shen, V. Uspensky, and N. Vereshchagin.Kolmogorov Complexity and Algorithmic Random- ness. American Mathematical Society, 2017. A Omitted Proofs Proof of Lemma 2.2 Proof of Lemma 2.2.AssumeH∈P FCU. Consider the predicateQ(m, k): “Are there at leastk distinct stringsxsuch thatC U(x)≤m?” This predicate is computably enumerable (c.e.), as one can enumerat...

    work page 2017

  13. [13]

    Initialize the answerans= 0

    Initialize the search range withL= 0andR= 2 m+1. Initialize the answerans= 0

    work page

  14. [14]

    •Query the oracle to check ifQ(m, mid)is true (i.e., isN m ≥mid?)

    WhileL≤R, perform the following steps: •Letmid=⌊(L+R)/2⌋. •Query the oracle to check ifQ(m, mid)is true (i.e., isN m ≥mid?). •If the answer isyes: The true count is at leastmid. Update the tentative answer ans←midand search the upper half by settingL=mid+ 1. •If the answer isno: The true count is strictly less thanmid. Search the lower half by settingR=mid−1

    work page

  15. [15]

    This algorithm performsO(m)queries

    Returnans. This algorithm performsO(m)queries. Since the input length ism, and each query takes polynomial time, the total running time is polynomial inm. Thus, a machineMsolvingCOUNT-SIMPLEexists. Proof of Proposition 2.6 Proof of Proposition 2.6.The upper bound is immediate; we prove the lower bound. Letpbe a shortest program forw n givenn. Let|p|=n−cfo...

    work page

  16. [16]

    Run the enumeration of the setSuntil the pair(wn, n)appears

    work page

  17. [17]

    Output the lexicograph- ically first stringznot present in this list

    At this point, the list of all strings with complexity≤nis complete. Output the lexicograph- ically first stringznot present in this list. By definition, the resulting stringzmust satisfyC V (z)> n. On the other hand,zis specified by the pair(p, c). The complexity of this description is: CV (z)≤ |p|+O(logc) = (n−c) +O(logc). Combining these inequalities, ...

    work page