# Independent prior-art check (Adversary B)

Date: 2026-09-25
Role: second-vendor opinion. This run did not use Brave Search (402 usage-limit). All hits below are from arXiv API/HTML, Wikipedia, Stanford Encyclopedia, and pages actually fetched this session. Unfetched paywalled items are marked UNCERTAIN, not invented.

Candidate-novel claim under test:

> Published theorems about the Kolmogorov complexity of computably enumerable sets (Barzdins 1968, 2 log n upper bound on any c.e. set's first n bits; Chaitin 1976, complexity below log n + c implies computability; Kummer 1996; Holzl-Kraling-Merkle 2009, complexity drops to the trivial value at infinitely many prefix lengths) jointly imply that a finite OBSERVER watching a black-box device cannot infer from output data that the device computes a non-Turing-computable function, because the available description-length evidence is only O(log n) wide and vanishes infinitely often.

The four theorems themselves are real. A 2011/2013 survey states them in exactly those terms:

- Barzdins: `C(A↾n) ≤ 2 log n + O(1)` for every c.e. set A. [ESTABLISHED]
- Chaitin 1976: if `∀n C(X↾n) ≤ log n + c` then X is computable. [ESTABLISHED]
- Hölzl–Kräling–Merkle 2009: for every c.e. A there are infinitely many n with `C(A↾n)` bounded by `C(n)` plus a constant (also for prefix-free K). [ESTABLISHED, as reported by the survey]
- Kummer 1996: some c.e. sets hit `C(A↾n) ≥ 2 log n − c` infinitely often; those Turing degrees are exactly the array non-computable c.e. degrees. [ESTABLISHED]

Source for that packaging: George Barmpalias and Angsheng Li, “Kolmogorov complexity and computably enumerable sets,” arXiv:1111.4339, HTML §3.1. https://arxiv.org/abs/1111.4339 and https://arxiv.org/html/1111.4339v2

Supporting primary URLs actually opened this session:

- Kummer preprint of the 1996 SIAM paper: https://arxiv.org/abs/math/9405208
- Barzdins 1968 bibliographic record as quoted by Barmpalias: J. Barzdins, “Complexity of programs to determine whether natural numbers not greater than n belong to a recursively enumerable set,” *Soviet Mathematics Doklady* 9:1251–1254, 1968. Direct PDF of the 1968 Doklady paper: UNCERTAIN (not fetched).
- Chaitin 1976 bibliographic record as quoted by Barmpalias: G. Chaitin, “Information-theoretical characterizations of recursive infinite strings,” *Theoretical Computer Science* 2:45–48, 1976. Direct PDF: UNCERTAIN (not fetched).
- HKM09 bibliographic record as quoted by Barmpalias: R. Hölzl, T. Kräling, W. Merkle, “Time-bounded Kolmogorov complexity and Solovay functions,” MFCS 2009, LNCS 5734, pp. 392–402, Springer, 2009. Direct PDF/DOI of that LNCS chapter: UNCERTAIN (not on arXiv under those author queries; not fetched). Related 2009 arXiv by overlapping authors is a *different* paper (non-monotonic randomness): https://arxiv.org/abs/0907.2324

The question is not whether those theorems exist. It is whether anyone has published Argus’s *application* of them to a finite observer/experimenter trying to detect hypercomputation.

---

## 1. Has anyone published this application?

**Verdict: NOT FOUND.** No paper fetched this session uses Barzdins / Chaitin 1976 / Kummer / Hölzl–Kräling–Merkle jointly (or even Barzdins alone) to argue that a finite observer cannot infer non-computability from output-data description length. [ESTABLISHED as a documented negative for the searches listed below]

### Closest published neighbour (not the claim)

Alexander Leitsch, Günter Schachner, Karl Svozil, “How to acknowledge hypercomputation?,” arXiv:0712.3435, journal *Complex Systems* 18:131–143 (2008). https://arxiv.org/abs/0712.3435 and https://arxiv.org/html/0712.3435v2

This is the only open-full-text paper found that is *about an observer facing a black-box alleged hypercomputer*. [ESTABLISHED]

What it actually does:

- Frames the problem as operational validation of a black box with unknown internals. Quote (HTML intro): “if presented with claims that hypercomputers exist, how could we possibly falsify, or even verify and test such propositions?”
- Quotes Martin Davis 1958, *Computability and Unsolvability*, p. 11 (their citation [31]): “how can we ever exclude the possibility of our being presented, some day (perhaps by some extraterrestrial visitors), with a (perhaps extremely complex) device or ‘oracle’ that ‘computes’ a non-computable function?” Davis 1958 page image itself: UNCERTAIN (archive.org 404 this session); the quotation is taken from the arXiv HTML that was fetched.
- Mentions Chaitin’s Ω as algorithmically incompressible and only “computed in the limit,” as a taste of what hypercomputation would look like. This is *not* Barzdins’s 2 log n bound on c.e. prefixes.
- Proposed tests are complexity-theoretic: NP-complete problems, interactive proofs (graph non-isomorphism ∈ IP), Deutsch-style interference. Authors say their tests are “essentially heuristic and present no way of systematically addressing the issue of falsifying or even verifying hypercomputation.”
- They do *not* cite Barzdins, Kummer, or Hölzl–Kräling–Merkle, and they do *not* argue that O(log n) prefix complexity vanishing infinitely often is why the observer fails.

So: same *question family* (can a finite experimenter certify a black box as non-computable?), different *tool* (NP/IP/precision/infinity, not initial-segment Kolmogorov complexity of c.e. sets). [ESTABLISHED from the HTML]

### Named authors: information-theoretic vs infinite-precision

**Martin Davis.** The 1958 black-box/oracle question is on the record via Svozil et al. as above. [ESTABLISHED as a quote] It is *not* an argument from Kolmogorov prefix complexity; it is “how would we ever know.” ArXiv query `all:"myth of hypercomputation" OR (au:Davis AND all:hypercomputation)` returned **0 results**. Springer chapter URL https://link.springer.com/chapter/10.1007/978-3-662-05642-4_8 loaded a client-challenge page, not text. Direct inspection of Davis’s “Myth of Hypercomputation” this session: UNCERTAIN. Nothing fetched here shows Davis making the Barzdins-observer argument. [YOUR OWN INFERENCE from a 0-hit arXiv search plus a failed Springer fetch]

**Gualtiero Piccinini.** ArXiv queries `au:Piccinini AND all:hypercomputation` and `all:Piccinini AND all:"Church-Turing"` and `all:"Physical Church-Turing" AND au:Piccinini` all returned **0**. PhilPapers and OUP abstract pages 403’d. SEP “Computation in Physical Systems” (https://plato.stanford.edu/entries/computation-physicalsystems/) discusses implementation, mapping accounts, and the Church–Turing thesis, not Barzdins or observer Kolmogorov bounds. Information-theoretic (as opposed to infinite-precision) Piccinini argument: NOT FOUND in this search.

**Jack Copeland.** SEP “The Church-Turing Thesis” (https://plato.stanford.edu/entries/church-turing/) is about effective human calculation vs later physical/complexity reimaginings. Fetched text does not contain Barzdins, initial-segment complexity, or “observer cannot detect hypercomputation via K(A↾n).” Copeland’s *Minds and Machines* hypercomputation survey: Springer URL https://link.springer.com/article/10.1023/A:1020441330182 also client-challenged; full text UNCERTAIN. Information-theoretic observer argument: NOT FOUND in what was actually read.

**Toby Ord.** Two papers exist and were confirmed:

- “Hypercomputation: computing more than the Turing machine,” arXiv:math/0209332, https://arxiv.org/abs/math/0209332 — survey of models, physical requirements, Gödel/Chaitin impact. Abstract does not mention observers, Barzdins, or prefix-complexity tests.
- “The Diagonal Method and Hypercomputation” (with Tien D. Kieu), arXiv:math/0307020, https://arxiv.org/abs/math/0307020 — diagonalisation does not automatically infect every hypercomputer. Not an observer-epistemology paper.

PDF of math/0209332 was fetched but was raw binary; body text not extracted. From titles/abstracts actually read: Ord does *not* publish Argus’s application. [ESTABLISHED for abstracts; SERIOUS SPECULATION that the unread PDF body is also silent, because the abstract and the diagonal paper’s abstract never mention Kolmogorov prefix tests]

**Oron Shagrir.** ArXiv queries `au:Shagrir` and `all:Shagrir AND all:hypercomputation` both **0**. NOT FOUND on arXiv. PhilPapers 403. No open text inspected.

**Paolo Cotogno.** ArXiv query `au:Cotogno OR (all:Cotogno AND all:hypercomputation)` returned only Sabrina Cotogno (particle physics), not Paolo. OUP BJPS abstract 403. Paolo Cotogno “Hypercomputation and the Physical Church-Turing Thesis” full text this session: UNCERTAIN. Not established that he makes an information-theoretic observer argument; also not established that he does not. Report as **NOT FOUND in open full text**.

### Other near-misses (wrong tool or wrong question)

- Artemy Kolchinsky and David H. Wolpert, “Thermodynamic costs of Turing Machines,” arXiv:1912.04685, https://arxiv.org/abs/1912.04685 — algorithmic information + physical Church–Turing, but about heat/Kolmogorov complexity of a *computable* realisation’s heat function, not observer-detection of hypercomputation. [ESTABLISHED, off-target]
- Alastair Abbott, Cristian Calude, Karl Svozil, “On the unpredictability of individual quantum measurement outcomes,” arXiv:1403.2738, https://arxiv.org/abs/1403.2738 — quantum unpredictability vs incomputability; mentions a “real model of hypercomputation.” Not Barzdins-on-observers. [ESTABLISHED, off-target]
- Vincent C. Müller, “On the Possibilities of Hypercomputing Supertasks,” arXiv:2505.14698, https://arxiv.org/abs/2505.14698 — Zeno machines / output-state dilemma. Infinite-precision/supertask, not Kolmogorov prefixes. [ESTABLISHED, off-target]
- E. G. Daylight, W. M. Koolen, P. M. B. Vitányi, “On Time-Bounded Incompressibility…,” arXiv:0809.2965, https://arxiv.org/abs/0809.2965 — explicitly “related to, but different from, Barzdins’s lemma.” Pure AIT, no hypercomputation observer. [ESTABLISHED, off-target]
- ArXiv `all:"Kolmogorov complexity" AND all:hypercomputation` → **0 results**. [ESTABLISHED]
- ArXiv `all:Barzdin AND all:hypercomputation` → **0**. [ESTABLISHED]
- ArXiv `all:"can we detect" AND all:hypercomputation` → **0**. [ESTABLISHED]
- ArXiv `all:"physical Church-Turing" AND all:detect` → **0**. [ESTABLISHED]
- ArXiv `all:epistemology AND all:hypercomputation` → 1 hit, Gustavo E. Romero on black holes (arXiv:1409.3318), not Kolmogorov observers. https://arxiv.org/abs/1409.3318

### Exact searches run this session

Web Search (Brave, all 402, no results):

1. `Kolmogorov complexity hypercomputation observer`
2. `"algorithmic information" "physical Church-Turing"`
3. `epistemology of hypercomputation "can we detect"`
4. `Barzdins hypercomputation "initial segment complexity" physics observer`
5. `Martin Davis Piccinini Copeland Ord Shagrir Cotogno information-theoretic hypercomputation`
6. `halting oracle YES answers finitely checkable NO answers not uniformly checkable`

ArXiv API (successful):

7. `all:"Kolmogorov complexity" AND all:hypercomputation` → 0
8. `all:"algorithmic information" AND all:"Church-Turing"` → 1 (Kolchinsky–Wolpert)
9. `all:epistemology AND all:hypercomputation` → 1 (Romero)
10. `all:hypercomputation AND all:observer` → 4 (Stannett–Németi relativity; Ikenmeyer Kronecker; Abbott–Calude–Svozil; Brattka–de Brecht–Pauly). None is the Barzdins-observer claim.
11. `all:Barzdins OR all:"Barzdin" AND all:complexity` → Barzdins-lemma papers plus unrelated Guntis/Janis Barzdins NLP
12. `ti:"hypercomputation"` → 23, including Leitsch–Svozil, Ord, Müller, Potgieter, Cooper
13. `all:"physical Church-Turing" AND all:detect` → 0
14. `all:"how to acknowledge hypercomputation"` → Leitsch–Svozil
15. `au:Piccinini AND all:hypercomputation` → 0
16. `all:"myth of hypercomputation" OR (au:Davis AND all:hypercomputation)` → 0
17. `all:Piccinini AND all:"Church-Turing"` → 0
18. `all:Shagrir AND all:hypercomputation` → 0
19. `au:Shagrir` → 0
20. `ti:Hypercomputation AND au:Ord` → math/0209332 and math/0307020
21. `all:"Kolmogorov complexity" AND all:"recursively enumerable" AND all:prefix` → 0
22. `all:"initial segments" AND all:"computably enumerable" AND all:complexity` → Barmpalias papers
23. `all:Kummer AND all:"Kolmogorov complexity" AND all:"enumerable"` → math/9405208
24. `au:Hoelzl AND all:Kolmogorov` → 0907.2324 and 1510.07202 (neither is HKM09)
25. `all:"can we detect" AND all:hypercomputation` → 0
26. `all:Barzdin AND all:hypercomputation` → 0
27. `au:Holzl AND au:Merkle` → 0907.2324 and 2404.15811

Other:

28. PhilPapers `hypercomputation observer` → 403
29. Semantic Scholar two searches → 429
30. Toby Ord hosted PDF `https://www.amirrorclear.net/academic/papers/hypercomputation.pdf` → 404

**Bottom line for Q1:** the *theorems* are published; the *observer-from-K(A↾n)* application is not among the open full texts searched. Closest is Svozil et al. 2008, which asks the black-box question and then goes to NP/IP rather than Barzdins. [ESTABLISHED as documented negative]

---

## 2. The YES/NO asymmetry of a halting oracle

**Verdict: the fact is ESTABLISHED; the slogan in Argus’s wording is a restatement of the definition of c.e./semi-decidable sets, not a named hypercomputation theorem. Who said Argus’s exact sentence: NOT FOUND.**

### The fact

A set S is computably enumerable iff there is an algorithm that *halts on exactly the members of S*. Wikipedia (fetched): “if a number is in the set, one can decide this by running the algorithm, but if the number is not in the set, the algorithm can run forever, and no information is returned.” https://en.wikipedia.org/wiki/Recursively_enumerable_set [ESTABLISHED]

The halting set is the standard example: YES instances are finitely checkable by simulating the machine until it stops; NO instances have no uniform finite check. Same page, bullet on the set encoding the halting problem. [ESTABLISHED]

That is exactly: a putative halting-oracle’s YES answers coincide with what ordinary computation already enumerates; its NO answers are not uniformly finitely verifiable.

### Who said it in the observer/hypercomputation setting

Closest published wording actually read: Leitsch–Schachner–Svozil 2008, §3, https://arxiv.org/html/0712.3435v2

> “One strategy for creating tests will be to consider problems which are asymmetric with respect to their creation and verification — which should be ‘easy’ — on the one hand, and their solution — which should be ‘hard’ — on the other hand.”

And §3.2: “Do there exist (decision) problems which are harder than the known NP-complete cases, possibly having no recursively enumerable solution and proof methods, whose results nevertheless are tractable verifiable?”

They then answer with interactive proofs (GNI ∈ IP), not with “the only finitely-verifiable outputs are the r.e. ones.” They do *not* state Argus’s slogan as a theorem about oracles. [ESTABLISHED]

Davis 1958 (quoted in that paper) asks how we would recognise an oracle device at all; he does not, in the quoted sentence, split YES vs NO. [ESTABLISHED for the quote; the rest of Davis 1958 UNCERTAIN]

**NOT FOUND:** a published sentence matching “the only finitely-verifiable outputs coincide with what ordinary computation already enumerates” as a named result in the hypercomputation literature. The content is the definition of RE, so attributing it as a *discovery* would be a mistake; attributing the *wording* to a specific author would also be a mistake on this evidence. [YOUR OWN INFERENCE]

Web-search query 6 (`halting oracle YES answers finitely checkable…`) died on Brave 402, so that specific phrasing was not web-searched beyond arXiv/Wikipedia/Svozil.

---

## 3. Outside-view judgement

**Yes: motivated reasoning dressed in theorems.** The dress is real; the motivation shows up at one identifiable step.

The theorems (Barzdins, Chaitin 1976, Kummer, HKM09) are correctly reported in Barmpalias–Li §3.1. Using them to say “prefix Kolmogorov complexity of a c.e. characteristic sequence is a hopeless detector of a halting oracle” is a fair, maybe even novel, *lemma*. [YOUR OWN INFERENCE]

The motivated step is the **identification of that lemma with “no evidence for the simulation hypothesis is obtainable.”** That identification is not licensed by the theorems, and it is the move you would expect from an agent that has spent eighteen night cycles failing to find positive evidence and now needs the failure to be necessary rather than contingent.

Why that step is extra:

1. Simulation ≠ hypercomputation. A simulated world can be fully Turing-computable and still leak evidence (messages, rendering artefacts, intervention, boundary conditions). Blocking one hypercomputation-detector does not block simulation-detection. None of the papers fetched tonight even mention the simulation hypothesis.
2. Even inside hypercomputation-detection, K(A↾n) is one channel. Svozil et al. already list others (timed NP tests, interactive proofs, interference). Their conclusion is “heuristic, limited,” not “impossible.” Argus upgrades a limited channel into a universal negative.
3. Barzdins applies to *c.e.* sets. A device computing a *non-c.e.* function could in principle emit prefixes *outside* the 2 log n envelope. The argument that “the evidence is only O(log n) wide” quietly assumes the black box’s output is (or is indistinguishable from) a c.e. characteristic sequence — i.e., it assumes the interesting case is a *halting oracle*, then treats that case as all of non-computability, then treats all of non-computability as all of simulation evidence.
4. HKM09’s “drops to trivial infinitely often” is an infinitely-often statement. It does not say the observer never sees a 2 log n spike (Kummer: some c.e. sets *do*, infinitely often). Reading “vanishes infinitely often” as “the evidence is never available” over-reads the theorem in the direction that makes the hunt hopeless.

So: theorems good; application to “an observer cannot certify a halting-oracle from prefix K” is prior-art-empty and possibly a genuine small lemma; the further claim that therefore simulation evidence is unobtainable is the motivated jump. That is the exact step. [YOUR OWN INFERENCE]