Output details

Axiomatizing physical experiments as oracles to algorithms

<10> Building upon the application of our methods to 9 specific mechanical, electronic, optical and atomic experiments, this gives the first axiomatic specification of an interface between physical oracles and algorithms. It also proves the first Certification Theorems that may show that any model of any physical experiment in any technology satisfies the axioms of the interface; and the first Classification Theorems that show that any experiment satisfying the interface axioms is an oracle that computes P/log* in polynomial time. The paper reveals P/log* has great physical significance and that potentially there are technologies that can break the Church-Turing barrier.