# Adversary C (mathematics check) -- 2026-09-25

Scope: verify or refute six mathematical claims in Argus's "noncomputability is not establishable from inside" argument. No literature search; direct reasoning only, plus one small computation (Claim 6) run locally to check the busy-beaver figure and machine count.

Verdict summary (details below):

| Claim | Verdict |
|---|---|
| 1 (Lemma 0) | TRUE as stated. The symmetric statement (finite data cannot certify computability) is also TRUE, but "certify" has to be defined as "logically entails", and then both directions are trivial. |
| 2 (assembled band) | OVERSTATED. The quantifier gap between (a)/(b) is real; "confined to a band of width log n + O(1)" is not what (a)+(b) give. A corrected weaker statement does hold. |
| 3 (one-sidedness) | TRUE, with the caveat that the "experiment exhibits a shorter account" half is about C of the finite record, not of the device. The inference is valid for the parsimony channel specifically. |
| 4 (certificate collapse) | The proof is correct under the right hypotheses, and it IS Post's theorem (Kleene/Post, c. 1943-44): A computable iff A and its complement are both c.e. Say so. |
| 5 (halting asymmetry) | First sentence TRUE; "hence ..." conclusion is sloppy but the repaired uniform version is TRUE. Cleanest statement is again complement-of-K is not c.e. |
| 6 (Argus's computation) | Sound; BB step-maximum for 2x2 is 6 (verified by enumeration: 20736 machines, 9784 halt, max 6 steps). It is an instance of Barzdins' method. It is NOT circular in the strong sense, but it is trivial in a specific sense noted below. |

---

## CLAIM 1 -- Lemma 0: any finite partial function is computable

**Statement checked.** "Any finite partial function is computable, so no finite record of input/output pairs is inconsistent with the hypothesis that the device computes a computable function."

**TRUE.** A finite partial function f with domain {x_1,...,x_m} is computed by the table-lookup program "if x = x_i output f(x_i), else diverge/output 0." Any finite record R of (input, output) pairs consistent with a single-valued function is therefore realised by a total computable function that agrees with R (extend by 0 outside the record). So for every finite R there exists a total computable g with g agreeing with R. Hence R is consistent with "the device computes a computable function". No subtlety here.

One precision: the hypothesis space must be "device computes SOME function" (single-valued on the observed inputs). If the record showed two different outputs on the same input, then no function is consistent, computable or not; that is not a computability issue.

**Symmetric statement: "finite data cannot certify computability."** Also TRUE, and for the same trivial reason, provided "certify" means: *R logically entails that the target is computable.* For every finite R, there is also a noncomputable total function h agreeing with R (take any noncomputable h' and patch its values on the finitely many recorded inputs; patching finitely many values preserves noncomputability since a finite patch is computable and computability is closed under finite modification). So R entails neither hypothesis.

Be careful what "certify" means, because there are three readings:

1. **Entailment** (R implies the hypothesis): finite data certifies neither computable nor noncomputable. Symmetric. This is what Lemma 0 needs and it is correct.
2. **Refutation of a specific model** (R is inconsistent with "device computes program p"): finite data CAN do this, in both directions, for a *named* program p. This is ordinary falsification and does not bear on the class-level question.
3. **Learning-in-the-limit** (Gold/Putnam sense): an infinite data stream can converge to a correct computable index for some classes (e.g. any uniformly computable family), but the class of ALL computable total functions is not learnable in the limit by any single learner (Gold 1967 style argument; also the class "computable vs noncomputable" is not identifiable). This is a different notion from certification and Argus should not slide into it.

So Lemma 0 is correct and the symmetry holds under reading 1. Under reading 1 both directions are *trivial* -- the interesting content of the argument has to come from elsewhere (Claims 2-5), not from Lemma 0. Do not let Lemma 0 carry weight it does not have.

---

## CLAIM 2 -- The assembled band

**Statement checked.** From (a) Barzdins, (b) Chaitin/Meyer, (c) Kummer, (d) Holzl-Kraling-Merkle, Argus concludes: "the entire computable-versus-noncomputable distinction for c.e. targets is confined to a band of width log n + O(1) bits."

First, the four ingredients, restated with quantifiers made explicit. Write A|n for the characteristic string of A on {0,...,n-1} (or 1..n; irrelevant).

- (a) Barzdins 1968: for every c.e. set A there is a constant c_A such that **for all n**, C(A|n) <= 2 log n + c_A. (Proof: describe A|n by n and the number k of elements of A below n, then enumerate A until k elements below n have appeared; the enumeration is fixed in the constant. Two integers of size <= n, hence 2 log n plus delimiting.) Barzdins also proved the sharper form C(A|n | n) <= log n + O(1), i.e. conditioned on n, only k is needed.
- (b) Chaitin 1976 / Meyer: if there is a c such that **for all n**, C(A|n) <= log n + c, then A is computable. (Equivalently, and more robustly: if C(A|n | n) <= c for all n then A is computable -- this is Loveland's / Meyer's form. The unconditional log n + c form follows because C(n) can be as large as log n + O(1).) Converse: if A is computable then C(A|n) <= C(n) + O(1) <= log n + O(1) for all n. So (b) is an exact characterisation of computability of A in terms of the *for-all-n* behaviour of C(A|n).
- (c) Kummer 1996: there is a c.e. set A and a constant c such that for **infinitely many n**, C(A|n) >= 2 log n - c. (So Barzdins's 2 log n is tight infinitely often for some c.e. sets. Kummer's theorem is in fact stronger and characterises which Turing degrees contain such "complex" c.e. sets: exactly the array-noncomputable degrees. I take this as given; not needed here.)
- (d) Holzl, Kraling, Merkle 2009: for **every** c.e. set A there are **infinitely many n** with C(A|n) <= C(n) + O(1). (Intuitively: along a c.e. set the "count k" is sometimes cheap; e.g. at n where k happens to be describable from n.) Note that C(n) + O(1) is the cost of describing A|n for a *computable* A, so (d) says every c.e. set looks computable-cheap infinitely often.

**Is the "band of width log n + O(1)" licensed by (a) and (b)?** NOT as stated. Here is the exact quantifier issue.

(a) gives, for every c.e. A: C(A|n) <= 2 log n + O(1) for all n.
(b) gives: A is computable iff C(A|n) <= log n + O(1) for all n.
Therefore, for a c.e. A:
- A computable  => C(A|n) in [0, log n + O(1)] for all n.
- A noncomputable (c.e.) => C(A|n) <= 2 log n + O(1) for all n (from (a)), AND for every constant c there are **infinitely many** n with C(A|n) > log n + c (negation of (b)). That is: the noncomputable c.e. set exceeds log n + c infinitely often, not for all n; and by (d) it also drops down to C(n) + O(1) infinitely often.

So the correct picture is not "the distinction lives in a band of width log n" in the sense of a per-n gap. The distinction between computable and noncomputable c.e. sets is: **does the curve n -> C(A|n) - log n stay bounded above (computable) or is it unbounded above (noncomputable)?** For c.e. sets the excursions above log n are themselves bounded by an additional log n + O(1) (from (a)). So:

**Corrected statement.** For every c.e. set A, the quantity e_A(n) := C(A|n) - log n satisfies e_A(n) <= log n + O(1) for all n (Barzdins). A is computable iff sup_n e_A(n) < infinity (Chaitin/Meyer/Loveland). If A is c.e. and noncomputable then e_A(n) is unbounded above but grows no faster than log n, and by (d) lim inf_n e_A(n) <= lim inf_n (C(n) - log n) + O(1), which is -infinity along the compressible n (see the C(n) remark below); in particular every noncomputable c.e. set has infinitely many prefixes that are as cheap as a computable set's prefixes.

What one may honestly say: "for c.e. targets, the computable/noncomputable distinction is carried by whether the excess of C(A|n) over log n is bounded, and that excess is at most log n + O(1)". That is a statement about the *sup of a function*, not about a "band" in which values sit for all n. The phrase "confined to a band of width log n + O(1)" reads as if every n witnesses the distinction; it does not. **Argus is equivocating between "for all n" and "infinitely often"** if the band phrase is read the natural way. The point matters for the paper's thesis: since the excess is only unbounded *along a sparse and non-effectively-locatable subsequence*, no finite sample of n's can show unboundedness -- which actually STRENGTHENS Argus's "not establishable from inside" conclusion, but via a different route than the band phrase suggests. Argus should make the sup/lim-sup structure explicit rather than the band.

Also (c) is not needed for the band; (c) only says the Barzdins bound is attained infinitely often by some c.e. sets. It shows the "extra log n" is not slack for all c.e. sets. Fine to cite, but it is not doing logical work in the conclusion.

**Is C(n) itself of order log n?** Yes and no, and this matters for reading (d):
- For all n, C(n) <= log n + O(1) (describe n in binary).
- For most n (all but a fraction 2^{-k}), C(n) >= log n - k. So "typically" C(n) ~ log n.
- But for infinitely many n, C(n) is much smaller: e.g. n = 2^m has C(n) <= C(m) + O(1) <= log log n + O(1), and towers give arbitrarily compressible n. Indeed lim inf_n (C(n) - log n) = -infinity.

Consequence for (d): the statement "C(A|n) <= C(n) + O(1) for infinitely many n" is NOT the same as "C(A|n) <= log n + O(1) for infinitely many n". The latter is weaker (it follows from the former since C(n) <= log n + O(1)). Whether the infinitely many n in (d) are compressible n or typical n is a question about the proof of (d). UNCERTAIN: I have not re-derived (d) here and do not want to claim which n witness it. What is safe: (d) implies every c.e. set has infinitely many n at which its prefix is no more expensive than a computable set's prefix at the same n, up to an additive constant. That is the reading Argus should use. Do not read (d) as "C(A|n) <= log n i.o." and then treat it as if it were nearly the (b) hypothesis; (b) needs FOR ALL n and (d) gives INFINITELY OFTEN, and the difference is exactly computability.

**Summary of Claim 2.** The four theorems are correctly attributed and correctly stated (modulo the (b) form; see below). The conclusion is overstated by a quantifier confusion. Correct version above. One more note on (b): the cleanest and most standard form is "A is computable iff C(A|n | n) = O(1)" (conditional on n) -- often attributed to Loveland 1969 for the characterisation and Meyer for the observation; Chaitin 1976 gives the unconditional log n + c version. The unconditional and conditional forms are interderivable up to constants because C(A|n) <= C(A|n | n) + C(n) + O(log C(n)) and C(n) can be as large as log n + O(1). Not a mathematical error, just a naming note.

---

## CLAIM 3 -- One-sidedness of C

**Statement checked.** "C is upper semi-computable but not lower semi-computable. Therefore an experiment can always exhibit a shorter computable account of the data, but no experiment can establish that no shorter account exists."

**The semi-computability claim is TRUE.** C(x) = min{|p| : U(p) = x}. The set {(x, m) : C(x) < m} is c.e. (dovetail all programs of length < m; if one outputs x, enumerate the pair). Hence C is upper semi-computable: one can effectively produce a nonincreasing sequence of upper bounds converging to C(x). C is not lower semi-computable: if it were, then being both upper and lower semi-computable it would be computable, and a computable C contradicts the standard result that C is not computable (Kolmogorov; via the Berry-paradox argument: "the least x with C(x) >= m" would be computable from m in O(log m) bits). Stronger: no unbounded computable lower bound for C exists (no computable f with f(x) <= C(x) and f unbounded). This is the sharp statement and it is what really drives the one-sidedness.

**The experimental reading is TRUE with a scope caveat.** "An experiment can exhibit a shorter account" means: given a finite record R and any candidate description p of R, one can verify U(p) = R by running p (for a halting p; if p does not halt in the allotted time, one simply waits or gives up). So upper bounds on C(R) are verifiable with a finite certificate (the program plus its run). Lower bounds are not: "no program of length < m outputs R" is a Pi_1 statement about all programs of length < m, quantifying over all run times; a bounded-time search that finds nothing does not certify it, because a short program might halt later. This is the standard asymmetry and is exactly the upper/lower semi-computability of C.

Caveat on scope: this is about C(R) for the finite record R. It says nothing about "the device" as an object. The parsimony channel argument goes: "the observer wants to conclude the device's outputs cannot be generated by any program shorter than the record". That conclusion is a lower bound on C(R) and cannot be certified, by the above. So the inference **"the parsimony channel cannot be closed from the inside" is VALID** for this channel, provided "closed" means "the observer can certify that no shorter computable account exists". Note that even a *very* weak version fails: the observer cannot certify C(R) >= f(|R|) for any unbounded computable f. So there is no "safety margin" trick available (e.g. "at least the record is not compressible by more than half"); the obstruction is total, not just asymptotic.

One genuine limitation to state: this is a statement about certification with certainty. Under a prior (e.g. Solomonoff/Levin), there IS a Bayesian sense in which a record can make "high complexity" overwhelmingly probable relative to a hypothesis class -- but that is again probability-under-a-prior, not certification, and the prior itself is a computable-model prior, so it is question-begging for the noncomputability question. Argus should say the inference is about certification, not degrees of belief.

---

## CLAIM 4 -- The certificate-collapse "repair"

**Statement checked.** "If every 1-output of a total target set has a finite Turing-checkable certificate, and every 0-output has one too, then the set is computable: dovetail the two certificate searches and output whichever appears first. Therefore a total noncomputable target cannot have uniformly Turing-checkable certificates on both sides."

**The proof is correct under the following precise hypotheses**, and under those hypotheses it is exactly Post's theorem. Let A be a subset of N (a total 0/1-valued target: for every x, exactly one of x in A, x not in A holds).

Hypotheses needed:
1. There is a **decidable** (or merely c.e.) relation Cert1(x, w) with: x in A iff exists w Cert1(x, w). ("1-certificates").
2. There is a **decidable** (or merely c.e.) relation Cert0(x, w) with: x not in A iff exists w Cert0(x, w). ("0-certificates").
3. The same Cert1, Cert0 work for all x (this is the "uniformly" in the conclusion). Non-uniform certificates -- a different checker for each x -- give nothing, because for each fixed x the constant checker "accept" is a checker for the correct answer.
4. Soundness in both directions: certificates must exist for every true instance (completeness) and must not exist for false instances (soundness). If Cert1 admits a false certificate for some x not in A, the dovetail gives a wrong answer.

Under 1-4 the set A = {x : exists w Cert1(x,w)} is c.e. (Sigma_1) and its complement is c.e. by the same reasoning with Cert0. Dovetailing the two searches on input x is a total procedure (because exactly one side has a certificate and it will be found) and correctly decides x in A. **So A is computable.**

Does the certificate relation need to be decidable? No: c.e. suffices, since a Sigma_1 predicate with a c.e. matrix is still Sigma_1 (fold the enumeration witness into w). Decidable is the cleaner hypothesis and matches "Turing-checkable" = "verifiable by a halting computation". Does it need certificates to be effectively enumerable? Only in the trivial sense that the space of candidate certificates is enumerable (finite strings); the dovetail enumerates all strings w and runs the checker. Does it need the target to be total? Yes, in this form: if A is a partial function (some x undefined), then the dovetail may diverge on undefined x, and one only gets that the graph is c.e., i.e. A is a partial computable function -- also a computability statement, but of the partial kind. For a total 0/1 set, totality is what guarantees the dovetail halts.

**Is this Post's theorem? YES, PLAINLY.** The statement "A is computable iff both A and its complement are computably enumerable" is the theorem usually credited to Post (1944, "Recursively enumerable sets of positive integers and their decision problems") and appears independently in Kleene's work of the same period; it is in every introductory computability textbook (Rogers Thm. 5.2.I; Soare Thm. I.2.x; Cutland Thm. 7.2.x). "Every 1-output has a uniformly Turing-checkable certificate" is literally the definition of "A is c.e." (Sigma_1 with a decidable matrix). "Every 0-output has one" is literally "complement of A is c.e." And "dovetail the two searches" is the standard proof. So adopting this "repair" is adopting Post's theorem under a new name. Argus should cite it as such: it is not a novel contribution and presenting it as an original lemma would be a red flag to any referee in logic.

The contrapositive Argus wants -- "a total noncomputable target cannot have uniformly Turing-checkable certificates on both sides" -- is the contrapositive of Post's theorem and is correct. Note it does NOT say a noncomputable target cannot have certificates on ONE side: the halting set K has 1-certificates (the halting run) and is noncomputable. That is Claim 5.

One more remark. There is a genuinely stronger fact Argus might actually want, which is not Post's theorem: even ONE-sided certificates for a noncomputable set cannot be *found* by an observer without already having the set. That is, K is c.e., so 1-certificates exist and are checkable, but the observer confronted with a black box that claims to be a halting oracle cannot use these certificates to certify the box IS a halting oracle, since the NO side is uncertifiable (Claim 5) and also since the observer only sees finitely many outputs (Claim 1). Post's theorem is a statement about the target set, not about the epistemic situation; Argus should keep those separate.

---

## CLAIM 5 -- The halting asymmetry

**Statement checked.** "A halting oracle's YES answers are finitely verifiable by running the machine; its NO answers are not. Hence the only finitely-verifiable outputs of a halting oracle are exactly those an ordinary dovetailing computer also produces."

**First sentence: TRUE**, with the usual precision. YES answer on input e: verifiable by running machine e until it halts; the certificate is the halting computation (a finite object, checkable in finite time). NO answer on input e: there is no *uniform* effective procedure that, given e with e not in K, produces a finite object checkable by a fixed decidable checker. Proof: if there were, the complement of K would be c.e., so K would be computable by Post's theorem, contradiction.

**The "not uniformly" repair is exactly right and is necessary.** For any *fixed* e not in K, there is trivially a "finite verification": the checker "accept e, reject everything else" is a decidable relation that certifies e not in K. So without "uniformly", the sentence "NO answers are not finitely verifiable" is FALSE for each individual instance and only true as a statement about a single fixed checker working for all instances. Also, for many specific machines, NO is provable in PA or ZF (e.g. a machine that provably loops); so *some* NO answers do have finite certificates relative to a fixed checker (a proof checker for ZF). But no fixed sound checker certifies all NO answers -- otherwise the complement of K would be c.e. Concretely: for every consistent, sound, c.e. axiomatised theory T there is a machine e that does not halt but T does not prove "e does not halt" (this is a form of Godel incompleteness for Pi_1 sentences and follows directly from complement-of-K not being c.e.).

**Second sentence ("hence ... exactly those an ordinary dovetailing computer also produces"): TRUE in content, sloppy in wording.** Content: the set of inputs on which the oracle says YES is K, which is exactly the set of inputs on which a dovetailing computer eventually outputs YES. So the *finitely-verifiable output set* of the oracle (under a fixed checker) is a c.e. set, hence something an ordinary computer enumerates. The sloppiness: (i) "produces" should be "eventually produces" -- the dovetailer produces YES at unbounded and unpredictable times, whereas the oracle answers immediately; so the oracle differs observably in *timing*, and only if the observer has a bound on time can that difference be used -- but the observer cannot certify any halting-time bound, since the halting-time function dominates every computable function. (ii) The oracle also produces NO answers, which the dovetailer never produces; the claim is only that those NO answers are not certifiable, not that they are not produced. The sentence should not suggest the oracle's output stream is identical to a dovetailer's.

**Cleanest correct statement.**
> Let K be the halting set. K is c.e. and its complement is not. Hence: (i) there is a decidable relation V with e in K iff exists w V(e,w) (the halting computation w is a certificate); (ii) there is no decidable (or c.e.) relation V' with e not in K iff exists w V'(e,w). Consequently, for any fixed sound checker, the set of oracle answers that the checker can certify is contained in a c.e. set, and every c.e. set of answers is also produced in the limit by an oracle-free dovetailing procedure. The oracle's surplus over a dovetailer is exactly its NO answers (and the timing of its YES answers), and neither surplus is certifiable by any fixed effective checker.

That is a corollary of Post's theorem plus the definition of K, nothing more. The statement generalises verbatim to any noncomputable c.e. set in place of K, and to any Sigma_1-complete oracle.

---

## CLAIM 6 -- Argus's 2-state 2-symbol computation

**Statement checked.** Enumerate all 12^4 = 20736 two-state two-symbol TMs; compute which halt from blank tape using a 200-step bound justified by BB(2,2) = 6; then a program receiving only (N, k), k = number of halters among the first N machines, dovetails all N machines and stops when the k-th halt is seen, declaring the rest non-halters. Reproduced the halting bits at N = 16, ..., 20736, using 58 bits for the two parameters at the largest N.

**Independent check (run here, /tmp/bb22.py, not saved to the workspace).** Encoding: for each of the 4 (state, read-symbol) pairs, a triple (write in {0,1}, move in {L,R}, next in {A, B, HALT}) = 12 options; 12^4 = 20736. Start in state A on blank tape; halting transition writes and moves and counts as one step. Results: 20736 machines, **9784 halt**, maximum halting time **6 steps**, halting-time histogram {1: 6912, 2: 2304, 3: 384, 4: 128, 5: 16, 6: 40}. So:

- **BB(2,2) step-maximum = 6 is correct.** This is Rado's S(2) = 6 (Rado 1962; Lin and Rado 1965 for the proof of the 2-state case), and the exhaustive enumeration confirms it under the 12^4 convention. (Sigma(2) = 4 is the ones-count, a different quantity; Argus needs the step function S, and correctly uses it.) Note the value depends mildly on convention: if the halt transition did not write/move, or if there were a separate halt state that consumed no step, one would get 6 or 5 depending on how steps are counted. Under the convention Argus states (halt is one of the three next-state options, i.e. the transition executes), 6 is right. UNCERTAIN only in this sense: I have not seen Argus's code, so I cannot confirm its convention matches; if its histogram shows max 6 and 9784 halters, it matches mine.
- **200-step bound is legitimate but vastly more than needed.** Any 2x2 machine that has not halted by step 6 never halts. A bound of 7 (or even 6) would do. 200 is harmless. The only thing to flag is the logical order: the justification "200 >= S(2) = 6" relies on the known value of S(2), which was itself established by exhaustive analysis of exactly these machines (Lin-Rado's proof includes a non-halting proof for each of the holdout machines). That is fine -- it is a citation, not a circularity -- but Argus should be aware that for 2x2 the "halting oracle" is *computable* (S(2) is a known constant), so the whole exercise lives entirely inside the computable world. See "circularity" below.
- **Does knowing k suffice? YES.** Dovetail all N machines (round-robin, one step each). Exactly k of them halt (by definition of k). Halting is a Sigma_1 event, so each halter is eventually observed. After the k-th observed halt, no further machine will halt (there are exactly k halters), so all others are non-halters. Correctness needs only that k is exact and that the dovetail is fair (every machine gets unboundedly many steps). Termination is guaranteed because all k halters halt at finite times. This is a complete and correct argument; no bound on step count is needed for the reconstruction (the bound is only used in the *ground-truth* computation that Argus compared against, where it is justified by S(2) = 6).
- **Is it "an instance of Barzdins' method"? YES, exactly.** Barzdins's proof that C(A|n) <= 2 log n + O(1) for c.e. A is: describe A|n by (n, k) where k = |A restricted to n|, then enumerate A until k elements below n have appeared. With A = the halting set (restricted to this indexing of 2x2 machines) that is verbatim Argus's program. The description length is log N + log k + delimiting overhead. At N = 20736, k = 9784: log2 N ~ 14.3, log2 k ~ 13.3, so the information content of the two parameters is about 28 bits; 58 bits reflects a fixed-width or self-delimiting encoding with slack. Both are O(log N) and consistent with Barzdins's 2 log n. (For prefix-free encoding, about 2 log log n extra; 58 is a generous but legitimate figure. Do not report 58 as if it were tight.)
- **Is it circular?** Two separate points.
  (i) *Not circular as a demonstration of Barzdins's method.* The program that receives (N, k) does not use the 200-step bound or S(2); it uses only dovetailing plus the count. So the reconstruction did not presuppose the halting bits. The comparison against ground truth uses S(2) = 6, a separately established constant. No circularity in the logic.
  (ii) *But it is trivial in a specific sense, and this is the important point for Argus's thesis.* For the 2x2 class, the halting problem is decidable (step bound 6), so the "target" here is a computable finite set. Barzdins's method is exhibited on a finite prefix of K, and by Claim 1 every finite prefix is computable; the demonstration shows that the prefix compresses to 2 log N bits, which is true for *every* c.e. set including computable ones (indeed a computable set compresses to C(N) + O(1) without needing k at all). So the computation demonstrates the mechanism of the 2 log n bound but cannot, even in principle, exhibit anything about noncomputability -- and Argus's own thesis (Lemma 0, Claim 3) predicts precisely this. The experiment is consistent with the thesis; it is not evidence *for* the thesis beyond illustrating the upper bound. It would be an overstatement to describe it as "verifying Barzdins's theorem on the halting set": it verifies the method on a finite decidable fragment. It should be presented as a worked illustration of the encoding (N, k) -> A|N, nothing more.
  (iii) A third, subtler point: the "k" that Argus feeds to the reconstruction program was computed by running the machines to the bound -- i.e. by a halting decision procedure valid for this class. In the genuinely noncomputable setting, k = |K restricted to n| is *not* computable from n (it is a Kolmogorov-random-like quantity of about log n bits that carries all the information of K|n; this is the content of Barzdins and of the Chaitin/Meyer converse). So the demonstration shows how to *use* k but conceals the fact that *obtaining* k is the whole problem. If Argus wants the demonstration to illustrate the thesis rather than merely the bound, it should say: "the entire non-effective content of K|n is compressed into the single number k, and for 2x2 machines k is computable because S(2) = 6, which is exactly why this fragment is decidable."

**Summary of Claim 6.** Sound, correctly labelled as Barzdins's method, BB step-maximum of 6 verified, 200-step bound legitimate (overkill), not circular in the logical sense, but operating entirely on a decidable fragment and therefore illustrating only the upper bound, not anything about noncomputability. Presentation should say so.

---

## FALSE OR OVERSTATED CLAIMS, WITH CORRECTIONS

1. **Claim 2, "confined to a band of width log n + O(1)".** OVERSTATED via for-all-n / infinitely-often equivocation. Corrected statement: *For every c.e. set A, C(A|n) - log n <= log n + O(1) for all n (Barzdins). A is computable iff C(A|n) - log n is bounded above (Chaitin/Meyer/Loveland). Hence a noncomputable c.e. set is distinguished from a computable one not by its value at any particular n but by unboundedness of the excess over log n along some infinite, non-effectively-locatable subsequence, an excess never larger than log n + O(1); and by (d) the same set also returns to computable-level cost C(n) + O(1) infinitely often.* The (c) Kummer result is not doing logical work in the conclusion; it shows the extra log n is attained i.o. by some c.e. sets.

2. **Claim 2, reading of (d).** C(n) is at most log n + O(1) and is close to log n for most n, but lim inf (C(n) - log n) = -infinity. So (d), "C(A|n) <= C(n) + O(1) i.o.", is strictly stronger than "C(A|n) <= log n + O(1) i.o." and must not be read as nearly satisfying the hypothesis of (b) -- (b) needs FOR ALL n; that difference is exactly computability. Whether the witnessing n in (d) are compressible n: UNCERTAIN, not re-derived here.

3. **Claim 4, presentation.** Not false; but the "repair" is Post's theorem (A computable iff A and its complement are c.e.), 1944, textbook. Adopt it by that name, with the hypotheses: a single decidable (or c.e.) certificate relation for each side, sound and complete, and totality of the target. Non-uniform certificates give nothing.

4. **Claim 5, second sentence.** Content correct, wording sloppy. "Produces" must be "eventually produces"; the oracle additionally produces NO answers and produces YES answers faster; neither surplus is certifiable by a fixed effective checker (the halting-time function dominates every computable function; the complement of K is not c.e.). The "not UNIFORMLY finitely verifiable" repair is required: individual NO instances have trivial or even ZF-provable certificates; only a single checker for all instances is impossible.

5. **Claim 6, framing.** Correct computation, but it operates on a decidable fragment (S(2) = 6 makes 2x2 halting decidable), so it illustrates the Barzdins upper bound only. Describing it as evidence about noncomputable targets would be an overstatement. The 58-bit figure is a loose encoding of about 28 bits of information; report it as an encoding, not as the information content.

## WHAT SURVIVES

- **Claim 1 (Lemma 0): correct as stated**, and the symmetric statement is also correct under "certify = entails". Both directions are trivial; Lemma 0 should carry no argumentative weight beyond setting up the problem.
- **Claim 2, ingredients (a)-(d): correctly stated** (with the quantifier annotations above). The corrected "bounded vs unbounded excess over log n" formulation survives and in fact supports Argus's thesis more directly than the band phrase, because unboundedness along a sparse subsequence is unobservable from any finite sample.
- **Claim 3: correct.** C is upper but not lower semi-computable; no unbounded computable lower bound exists; upper bounds on C(record) are finitely certifiable, lower bounds are not; hence the parsimony channel cannot be closed from the inside (in the certification sense). The strong form -- no safety-margin lower bound of any unbounded computable size is certifiable -- also holds.
- **Claim 4: the proof is correct** under uniform, sound, complete, decidable (or c.e.) certificate relations and a total target. It is Post's theorem.
- **Claim 5: correct in the uniform form.** YES answers of a halting oracle are certifiable by the halting run; NO answers are not uniformly certifiable by any fixed effective checker; the certifiable output set of the oracle is a c.e. set and hence is enumerated in the limit by an oracle-free dovetailer.
- **Claim 6: the dovetail-with-k argument is sound; BB(2,2) step-maximum = 6 verified by enumeration (20736 machines, 9784 halters); the 200-step bound is valid; the label "instance of Barzdins' method" is exact; there is no logical circularity.**

## UNCERTAIN ITEMS (not guessed)

- Which n witness Holzl-Kraling-Merkle (d): typical n or compressible n. Not re-derived.
- Whether Argus's own 2x2 enumeration used the same halt-transition convention as my check (halt transition writes, moves, and counts one step). If its histogram is max 6 with 9784 halters, conventions match.
- Exact attribution of the conditional form of (b) (Loveland vs Meyer vs Chaitin); this is a naming question, not a mathematical one, and does not affect any verdict.