I show that physical devices that perform observation, prediction, or recollection share an underlying mathematical structure. I call devices with that structure ``inference devices\'\'. I present a set of existence and impossibility results concerning inference devices. These results hold independent of the precise physical laws governing our universe. In a limited sense, the impossibility results establish that Laplace was wrong to claim that even in a classical, non-chaotic universe the future can be unerringly predicted, given sufficient knowledge of the present. Alternatively, these impossibility results can be viewed as a non-quantum mechanical ``uncertainty principle\'\'. Next I explore the close connections between the mathematics of inference devices and of Turing Machines. I end by informally discussing the philosophical implications of these results, e.g., for whether the universe ``is\'\' a computer.