Journal article 1287 views 183 downloads
Three forms of physical measurement and their computability
Felix Costa,
Edwin Beggs 
,
John Tucker
,
John Tucker
The Review of Symbolic Logic, Volume: 7, Issue: 4, Pages: 618 - 646
Swansea University Authors:
Edwin Beggs , John Tucker
-
PDF | Accepted Manuscript
Download (510.63KB)
DOI (Published version): 10.1017/S1755020314000240
Abstract
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 |
|---|---|
| Published: |
2014
|
| Online Access: |
http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=9461557&fileId=S1755020314000240 |
| URI: | https://cronfa.swan.ac.uk/Record/cronfa21456 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Abstract: |
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. |
|---|---|
| Keywords: |
measurement, experiment, physical oracles,Turing machines, non-uniform complexity classes |
| College: |
Faculty of Science and Engineering |
| Issue: |
4 |
| Start Page: |
618 |
| End Page: |
646 |