arxiv: 2605.02501 · v1 · submitted 2026-05-04 · 💻 cs.IT · math.IT· math.LO

Recognition: 3 theorem links

· Lean Theorem

Computability Limits of Sequential Hypothesis Testing

Amir Leshem

Authors on Pith no claims yet

Pith reviewed 2026-05-08 17:54 UTC · model grok-4.3

classification 💻 cs.IT math.ITmath.LO

keywords Cover's theoremsequential decision proceduresfinite error learninglimit computabilityΔ^0_2 setscomputable hypothesis testingeffectively presented familiesmembership test

0 comments

The pith

Subsets of the rationals admit computable sequential tests with only finitely many errors exactly when they satisfy a specific computability condition.

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

The paper starts from Cover's theorem, which shows that sequential tests can eventually identify the true mean from a countable set of candidates with only finitely many errors almost surely. It sharpens this by determining precisely which subsets of the rational numbers allow such tests to be carried out by a computable Turing machine. A sympathetic reader would care because this draws a sharp line between what can be learned through computable empirical methods that are allowed to flip their answer finitely often and what cannot, formalizing a limit on convergence to truth in probabilistic inquiry. The extension to effectively presented families shows when the general rule itself becomes computable.

Core claim

Starting from Cover's theorem guaranteeing eventual correctness for countable sets of means, the paper provides a complete necessary and sufficient characterization of the subsets of the rationals that admit a computable finite-error sequential membership test. This characterization is further extended to any effectively presented countable family of real means, which is the setting where Cover's identification rule can be implemented by a computable procedure.

What carries the argument

A computable finite-error sequential membership test: a Turing machine that, upon receiving successive data samples, outputs a sequence of decisions about whether the true mean belongs to a given subset, changing its mind only finitely many times almost surely and eventually stabilizing to the correct answer.

If this is right

If the characterization holds, then for subsets outside the identified class no computable procedure can achieve finite errors with probability one.
The results apply directly to any effectively presented family, allowing implementation of Cover's rule in a computable way precisely for those sets.
This clarifies the meaning of convergence to the truth in a precise probabilistic setting under computability constraints.
Empirical methods can succeed in eventual stabilization only up to this computability boundary.

Where Pith is reading between the lines

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

This boundary might imply that for sets that are not limit computable, any practical algorithm would require an external oracle or accept the possibility of infinitely many errors.
It connects sequential hypothesis testing to broader questions in computable analysis and algorithmic learning theory.
One could test the characterization by exhibiting a specific non-limit-computable subset of Q and attempting to construct or disprove the existence of a corresponding computable test.

Load-bearing premise

The load-bearing premise is that the family of candidate means must be effectively presented so that membership can be decided via computable means and that the decision procedures themselves must be computable Turing machines.

What would settle it

A concrete counterexample would be either a subset of the rationals that satisfies the paper's necessary and sufficient condition but for which no computable finite-error test exists, or a subset that violates the condition yet possesses such a test.

read the original abstract

Sequential hypothesis testing asks for decision rules that update as data arrive. A natural goal is \emph{eventual correctness}: the rule may change its mind early on, but it should make only finitely many wrong decisions almost surely. Starting from Cover's theorem, which guarantees such behavior for membership in a countable set of candidate means, we ask a sharper question: \emph{which sets actually admit computable sequential decision procedures with finitely many errors?} We answer this optimally by giving a complete characterization both necessary and sufficient of the subsets of $\Q$ that admit a computable finite-error sequential membership test. We further extend the characterization to any \emph{effectively presented} countable family of real means, exactly the setting in which Cover's identification rule can be implemented computably. Beyond the technical boundary, the results clarify within a precise probabilistic setting what it can mean for inquiry to ``converge to the truth,'' and they formalize a limit to which empirical methods can be expected to succeed when only eventual stabilization (rather than fixed-time guarantees) is demanded. keywords: Cover's theorem, sequential decision procedures, finite error learning, limit computability, $\Delta^0_2$ sets.

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.

Desk Editor's Note private letter to a colleague

The paper gives a clean necessary-and-sufficient characterization of which subsets of Q allow computable sequential tests with only finitely many errors almost surely, extending Cover's theorem via limit-computability.

read the letter

The main takeaway is that this work pins down exactly which subsets of the rationals support a computable procedure that eventually picks the right mean with finitely many mistakes almost surely. It does the same for effectively presented countable families of real numbers, keeping the link to Cover's identification rule intact. The characterization boils down to the limit-computable sets, or Δ⁰₂ sets in the arithmetic hierarchy. Necessity follows because any Turing machine that stabilizes almost surely on the data must produce a limit-computable indicator. Sufficiency comes from an explicit construction that waits until the empirical averages are far enough from the other candidates to guarantee no further flips. The paper does this without adding hidden uniformity assumptions or oracle access to the reals. The arguments track the probabilistic guarantees from Cover while layering on the computability constraint, and the stress-test confirms the reductions hold in both directions. One soft spot is the dependence on effective presentation of the candidate family; without it the result does not apply, which is fair but restricts the setting to enumerable lists. The constructions are non-constructive in the usual sense for Δ⁰₂ sets, so they do not immediately give fast practical algorithms. This is a niche but precise contribution at the boundary of information theory and computability. It is aimed at readers who already work on sequential decision rules or computable statistics and want a sharp boundary rather than another existence proof. The core claim is new and the reasoning is direct, so the paper deserves a serious referee even if revisions are needed on exposition or examples.

Referee Report

0 major / 2 minor

Summary. The paper provides a necessary-and-sufficient characterization of subsets of the rationals Q that admit computable sequential membership tests with only finitely many errors almost surely. It extends the result to any effectively presented countable family of real means, precisely the setting where Cover's identification rule is computably implementable. The characterization is obtained by reducing the problem to limit-computable (Δ⁰₂) sets via almost-sure stabilization of empirical means, with necessity extracted from any stabilizing Turing machine and sufficiency via an explicit construction that waits for sufficient separation in the averages.

Significance. If the central claim holds, the work is significant because it supplies both directions of the characterization with explicit constructions and a direct reduction that avoids hidden assumptions on uniform convergence rates or oracle access to real data. This clarifies the precise boundary between what computable empirical procedures can achieve under eventual-correctness criteria and what they cannot, while preserving the link to Cover's theorem exactly when the family is effectively presented. The paper thereby formalizes computability limits on inquiry that is allowed to change its mind finitely often but must stabilize almost surely.

minor comments (2)

[Abstract] Abstract: the claim of a 'complete characterization' would be more informative if the abstract briefly named the class (limit-computable / Δ⁰₂ sets) rather than deferring the statement entirely to the body.
The notation for the sequential decision procedures and the effective presentation of the mean family is introduced gradually; a short preliminary subsection collecting the relevant computability definitions would improve readability for readers outside the intersection of computability theory and statistics.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, including the summary of the necessary-and-sufficient characterization for subsets of Q and the extension to effectively presented families of real means. We appreciate the recommendation for minor revision and will incorporate any editorial or minor clarifications in the revised version. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation begins from Cover's external theorem on eventual correctness for countable candidate means and reduces the computability question to the standard notion of limit-computable sets (Δ⁰₂) by analyzing almost-sure stabilization of empirical averages. Necessity follows directly from any Turing machine that stabilizes with finitely many errors; sufficiency is shown by an explicit construction that waits for empirical separation. No equation or central claim reduces by definition to a fitted parameter, self-citation, or ansatz imported from the authors' prior work; the characterization is self-contained against external computability benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Review performed on abstract only; no free parameters, invented entities, or ad-hoc axioms are visible. The work relies on standard computability notions and the prior Cover's theorem.

axioms (2)

domain assumption Cover's theorem guaranteeing eventual correctness for membership in a countable set of candidate means
Explicitly invoked as the starting point for the sharper computability question.
standard math Standard results from computability theory on limit-computable sets and the class Delta^0_2
Referenced via keywords and the characterization of admissible sets.

pith-pipeline@v0.9.0 · 5502 in / 1493 out tokens · 85377 ms · 2026-05-08T17:54:00.234840+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

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

No RS analogue — RS cost J(x)=½(x+x⁻¹)−1 is ratio-symmetric, not LIL-shaped Cost.FunctionalEquation.washburn_uniqueness_aczel (no contact) unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

δ_n := max{(1+α)√(2 s²_n log log n / n), 2^{-n}} ... LIL plus Borel–Cantelli

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

15 extracted references

[1]

2000 , series =

Weihrauch, Klaus , title =. 2000 , series =

2000
[2]

New Computational Paradigms: Changing Conceptions of What is Computable , editor =

Brattka, Vasco and Hertling, Peter and Weihrauch, Klaus , title =. New Computational Paradigms: Changing Conceptions of What is Computable , editor =. 2008 , pages =

2008
[3]

and Richards, J

Pour-El, Marian B. and Richards, J. Ian , title =. 1989 , series =

1989
[4]

Shoenfield , title =

Joseph R. Shoenfield , title =. 1993 , doi =

1993
[5]

and Richards, J

Pour-El, Marian B. and Richards, J. Ian , title =. 2017 , series =

2017
[6]

The Annals of Statistics , volume =

Dembo, Amir and Peres, Yuval , title =. The Annals of Statistics , volume =
[7]

and Zeitouni, Ofer , title =

Kulkarni, Sanjeev R. and Zeitouni, Ofer , title =. Statistics & Probability Letters , volume =
[8]

, title =

Ermakov, M. , title =. Journal of Mathematical Sciences , volume =. 2017 , note =

2017
[9]

, title =

Cover, Thomas M. , title =. The Annals of Statistics , volume =
[10]

, title =

Shoenfield, Joseph R. , title =
[11]

and Nerman, Olle , title =

Koplowitz, Jack and Steif, Jeffrey E. and Nerman, Olle , title =. Scandinavian Journal of Statistics , volume =
[12]

The Journal of Symbolic Logic , volume =

Putnam, Hilary , title =. The Journal of Symbolic Logic , volume =
[13]

Mark , title =

Gold, E. Mark , title =. Information and Control , volume =
[14]

and Royer, James S

Jain, Sanjay and Osherson, Daniel N. and Royer, James S. and Sharma, Arun , title =
[15]

, title =

Terwijn, Sebastiaan A. , title =. Logic Colloquium 2002 , series =

2002