THREE FORMS OF PHYSICAL MEASUREMENT AND THEIR COMPUTABILITY

We have begun a theory of measurement in which an experimenter and his or her experimental procedure are modeled by algorithms that interact with physical equipment through a simple abstract interface. The theory is based upon using models of physical equipment as oracles to Turing machines. This al...

Full description

Saved in:
Bibliographic Details
Published in:The review of symbolic logic 2014-12, Vol.7 (4), p.618-646
Main Authors: BEGGS, EDWIN, COSTA, JOSÉ FÉLIX, TUCKER, JOHN V
Format: Article
Language:English
Subjects:
Algorithms
Complexity
Lower bounds
Polynomials
Specifications
Turing machines
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We have begun a theory of measurement in which an experimenter and his or her experimental procedure are modeled by algorithms that interact with physical equipment through a simple abstract interface. The theory is based upon using models of physical equipment as oracles to Turing machines. This allows us to investigate the computability and computational complexity of 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 measurement process and three types of measurement algorithm. We give axiomatic specifications of three forms of interfaces that enable the three types of experiment to be used as oracles to Turing machines, and lemmas that help certify an experiment satisfies the axiomatic specifications. For experiments that satisfy our axiomatic specifications, we give lower bounds on the computational power of Turing machines in polynomial time using nonuniform complexity classes. These lower bounds break the barrier defined by the Church-Turing Thesis.
ISSN:1755-0203
1755-0211
DOI:10.1017/S1755020314000240