No Cover Image

Journal article 593 views 34 downloads

Three forms of physical measurement and their computability / Edwin, Beggs; John, Tucker

The Review of Symbolic Logic, Volume: 7, Issue: 4, Pages: 618 - 646

Swansesa University Authors: Edwin, Beggs, John, Tucker

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...

Full description

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: College of Science
Issue: 4
Start Page: 618
End Page: 646