Limits to prediction

A paper here by David Wolpert on the idea of "inference machines" -- any physical machine that would make predictions of the future -- and the inherent limits to their abilities. The abstract:

We show that physical devices that perform observation, prediction, or recollection share a mathematical structure. We call devices with that structure ``inference devices''. We present existence and impossibility results for inference devices. These results hold independent of the precise physical laws of our universe. The impossibility results establish that Laplace was wrong to claim that even in a classical, non-chaotic universe the future can be unerringly predicted. Alternatively, they can be viewed as a non-quantum mechanical ``uncertainty principle''. The mathematics of inference devices is related to the theory of Turing Machines (TM's), e.g., some impossibility results for inference devices are related to the Halting theorem for TM's. Furthermore, one can define an analog of Universal TM's (UTM's) for inference devices, which we call ``strong inference devices''. We use strong inference devices to define the ``inference complexity'' of an inference task, which is analogous to the Kolmogorov complexity of a string. A task-independent bound is derived on the difference in inference complexity of an inference task performed with two different inference devices. This is analogous to the ``encoding'' bound on the difference in Kolmogorov complexity of a string between two UTM's. However whereas the Kolmogorov complexity of a string is arbitrary up to specification of the UTM, there is no such arbitrariness in the inference complexity of an inference task. We informally discuss philosophical implications of these results, e.g., for whether the universe ``is'' a TM. We also derive some graph-theoretic properties governing sets of multiple inference devices. Next we extend the framework to address physical devices used for control, and then to address probabilistic inference.