Retrodicting Chaotic Systems: An Algorithmic Information Theory Approach

The paper explicitly argues that among the m=|g^{-1}(y)| candidates, the number whose Kolmogorov complexity is below that of the true start x0 is bounded by about 2^{K(x0)} (their Eq. (15)), so the fraction 2^{K(x0)}/m → 0 as m→∞ (their Eq. (16)). This is exactly the standard prefix-free counting bound the model uses via Kraft’s inequality, instantiated with k=K(x0), and the same asymptotic conclusion follows. The paper also gives a complementary heuristic showing typical candidates have K(xi) ≳ K(m) (Eqs. (10)–(14)), which the model does not need for the vanishing-fraction claim. Hence both are correct and essentially the same proof for the core result about a vanishing fraction of candidates being simpler than x0 . The problem setup and goals—retrodict x0 from y=f^n(x0) and improve over uniform guessing—match as well .