Recent developments on the physical limits of inference

  • David H. Wolpert (NASA Ames Research Center, USA)
A3 01 (Sophus-Lie room)


In this talk I first review the fact that all physical devices that perform observation, prediction, or recollection share an underlying mathematical structure. Devices with that structure are called ``inference devices''. I then present new existence and impossibility results concerning inference devices. These results have close connections with the mathematics of Turing Machines (TM's), e.g., some of the 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, called ``strong inference devices''. Strong inference devices can be used to define the ``inference complexity'' of an inference task, which is the analog of the Kolmogorov complexity of computing a string. 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. I present some new results bounding inference complexity. Next I present some new graph-theoretic properties that govern any set of multiple inference devices. After this I present an extension of the framework to address physical devices that are used for control. I end with an extension of the framework to address probabilistic inference.