Three forms of physical measurement and their computability - Edwin Beggs (The Review of Symbolic Logic, 2014)
We have begun a theory of measurement in which an experimenter and his or herexperimental procedure are modeled by algorithms that interact with physical equipment through asimple abstract interface. The theory is based upon using models of physical equipment as oraclesto Turing machines. This allows us to investigate the computability and computational complexityof measurement processes. We examine eight different experiments that make measurements and,by introducing the idea of an observable indicator, we identify three distinct forms of measurementprocess and three types of measurement algorithm. We give axiomatic specifications of three formsof interfaces that enable the three types of experiment to be used as oracles to Turing machines, andlemmas that help certify an experiment satisfies the axiomatic specifications. For experiments thatsatisfy our axiomatic specifications, we give lower bounds on the computational power of Turingmachines in polynomial time using nonuniform complexity classes. These lower bounds break thebarrier defined by the Church-Turing Thesis.