Axiomatizing physical experiments as oracles to algorithms

作者：Beggs Edwin J; Costa Jose Felix; Tucker John V^*

来源：Philosophical Transactions of the Royal Society A-Mathematical Physical and Engineering Sciences, 2012, 370(1971): 3359-3384.

DOI：10.1098/rsta.2011.0427

• Turing machines
• oracles
• experiments
• measurement
• complexity classes
• computability

We developed earlier a theory of combining algorithms with physical systems, on the basis of using physical experiments as oracles to algorithms. Although our concepts and methods are general, each physical oracle requires its own analysis, on the basis of some fragment of physical theory that specifies the equipment and its behaviour. For specific examples of physical systems (mechanical, optical, electrical), the computational power has been characterized using non-uniform complexity classes. The powers of the known examples vary according to assumptions on precision and timing but seem to lead to the same complexity classes, namely P/log star and BPP//log star. In this study, we develop sets of axioms for the interface between physical equipment and algorithms that allow us to prove general characterizations, in terms of P/log star and BPP//log star, for large classes of physical oracles, in a uniform way. Sufficient conditions on physical equipment are given that ensure a physical system satisfies the axioms.

• 出版日期2012-7-28