Computational capabilities of physical systems

In this paper strong limits on the accuracy of real-world physical computation are established. To derive these results a non-Turing Machine (TM) formulation of physical computa- tion is used. First it is proven that there cannot be a physical computer C to which one can pose any and all computational tasks concerning the physical universe. Next it is proven that no physi- cal computer C can correctly carry out every computational task in the subset of such tasks that could potentially be posed to C. This means in particular that there cannot be a physical computer that can be assured of correctly "processinginformation faster than the universe does".Because this result holds independent of how or if the computer is physically coupled to the rest of the uni- verse, it also means that there cannot exist an infallible, general-purpose observation apparatus, nor an infallible, general-purpose control apparatus. These results do not rely on systems that are infinite, and/or non-classical, and/or obey chaotic dynamics. They also hold even if one could use an infinitely fast, infinitely dense computer, with computational powers greater than that of a Tur- ing Machine (TM). After deriving these results analogues of the TM Halting theorem are derived for the novel kind of computer considered in this paper, as are results concerning the (im)possibil- ity of certain kinds of error-correcting codes. In addition, an analogue of algorithmic information complexity, "predictioncomplexity",is elaborated. A task-independent bound is derived on how much the prediction complexity of a computational task can differ for two different reference uni- versal physical computers used to solve that task. This is analogous to the "encoding" bound gov- erning how much the algorithm information complexity of a TM calculation can differ for two