Journal article 556 views 32 downloads
Three forms of physical measurement and their computability / Felix Costa; Edwin J Beggs; John Tucker
The Review of Symbolic Logic, Volume: 7, Issue: 4, Pages: 618 - 646
Swansea University Author: Tucker, John
PDF | Accepted ManuscriptDownload (510.63KB)
DOI (Published version): 10.1017/S1755020314000240
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 allow...
|Published in:||The Review of Symbolic Logic|
No Tags, Be the first to tag this record!
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.
measurement, experiment, physical oracles,Turing machines, non-uniform complexity classes
College of Science