The Optimal Causal Linear Predictor is Not Turing Computable

This article shows that the minimum mean square error (MMSE) for predicting a stationary stochastic time series from its past observations is not generally Turing computable, even if the spectral density of the stochastic process is differentiable with a computable first derivative. Thus there are spectral densities with the property that for any approximation sequence that converges to the MMSE there does not exist an algorithmic stopping criterion that guarantees that the computed approximation is sufficiently close to the true value of the MMSE. Furthermore, it is shown that under the same conditions on the spectral density, the coefficients of the optimal prediction filter are not generally Turing computable. In such cases and for any sequence of computable finite-impulse response approximations of the optimal prediction filter there exists no algorithmic stopping criterion that is able to guarantee a desired approximation error.