← Back to arXiv
arXivLogicarXiv:2608.05443

Sequential-Innovation Reducibility and the Innovation Spectrum

The paper introduces a new way of classifying infinite binary sequences (endless strings of 0s and 1s) based on how well they can be predicted step by step. When you try to forecast each new bit in a sequence using only what came before, you inevitably make some errors. These errors form a new sequence called the "innovation sequence," and the paper studies what information is encoded in those error patterns. The central idea is that the collection of all possible innovation sequences a predictor can generate from a given sequence reveals something fundamental about that sequence's structure, which the authors call its "innovation spectrum."

From this, the authors define a new notion of "reducibility," a way of saying that one sequence is no more complex than another. In computability theory, reducibility relations organize sequences into a hierarchy based on how much information one contains about another. The new reducibility introduced here turns out to be finer than a classical notion called truth-table reducibility, meaning it makes distinctions that classical methods miss. When the authors map out the overall structure, they find it splits into two distinct regions: one that mirrors the classical hierarchy closely (the "truth-table spine"), and one made up of sequences that are essentially resistant to having any large predictable patterns extracted from them (the "reservoir-immune" region).

The paper then establishes several important properties of this new landscape. Reservoir immunity, the property of resisting large-scale predictable extraction, is preserved when you pass to innovation sequences, and the two regions can be connected through specific constructions. A particularly notable result is that the well-studied class of Martin-Lof random sequences, which represent the gold standard of "patternless" sequences, sits inside the reservoir-immune region but does not exhaust it. Overall, the work reveals a new geometric picture of how infinite sequences are organized when the lens is causal predictability rather than traditional computation-based comparison.

Read original →