Uncomputably noisy ergodic limits (Q1762356)

Improving on a result of V'yugin, the author constructs a computable shift-invariant measure on \(2^{\mathbb{N}}\) and a simple function \(f\) with the property that there is no computable bound on the complexity of the limit of the ergodic averages \(A_{n}f\). In other words, he shows that there is no computable bound on how complex a simple function needs to be to approximate the limit to within a given \(\varepsilon >0\).