No Cover Image

Journal article 1337 views 200 downloads

Three forms of physical measurement and their computability

Felix Costa, Edwin Beggs Orcid Logo, John Tucker Orcid Logo

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

Swansea University Authors: Edwin Beggs Orcid Logo, John Tucker Orcid Logo

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!
first_indexed 2015-05-17T02:02:56Z
last_indexed 2023-01-31T03:27:43Z
id cronfa21456
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2023-01-30T14:53:59.0054785</datestamp><bib-version>v2</bib-version><id>21456</id><entry>2015-05-16</entry><title>Three forms of physical measurement and their computability</title><swanseaauthors><author><sid>a0062e7cf6d68f05151560cdf9d14e75</sid><ORCID>0000-0002-3139-0983</ORCID><firstname>Edwin</firstname><surname>Beggs</surname><name>Edwin Beggs</name><active>true</active><ethesisStudent>false</ethesisStudent></author><author><sid>431b3060563ed44cc68c7056ece2f85e</sid><ORCID>0000-0003-4689-8760</ORCID><firstname>John</firstname><surname>Tucker</surname><name>John Tucker</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2015-05-16</date><deptcode>SMA</deptcode><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.</abstract><type>Journal Article</type><journal>The Review of Symbolic Logic</journal><volume>7</volume><journalNumber>4</journalNumber><paginationStart>618</paginationStart><paginationEnd>646</paginationEnd><publisher/><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint/><issnElectronic/><keywords>measurement, experiment, physical oracles,Turing machines, non-uniform complexity classes</keywords><publishedDay>9</publishedDay><publishedMonth>9</publishedMonth><publishedYear>2014</publishedYear><publishedDate>2014-09-09</publishedDate><doi>10.1017/S1755020314000240</doi><url>http://journals.cambridge.org/action/displayAbstract?fromPage=online&amp;amp;aid=9461557&amp;amp;fileId=S1755020314000240</url><notes/><college>COLLEGE NANME</college><department>Mathematics</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SMA</DepartmentCode><institution>Swansea University</institution><apcterm/><funders/><projectreference/><lastEdited>2023-01-30T14:53:59.0054785</lastEdited><Created>2015-05-16T16:25:12.1271702</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Mathematics</level></path><authors><author><firstname>Felix</firstname><surname>Costa</surname><order>1</order></author><author><firstname>Edwin</firstname><surname>Beggs</surname><orcid>0000-0002-3139-0983</orcid><order>2</order></author><author><firstname>John</firstname><surname>Tucker</surname><orcid>0000-0003-4689-8760</orcid><order>3</order></author></authors><documents><document><filename>0021456-31102016103554.pdf</filename><originalFilename>ThreeFormsOfPhysicalMeasurementAndTheirComputability.pdf</originalFilename><uploaded>2016-10-31T10:35:54.4030000</uploaded><type>Output</type><contentLength>487874</contentLength><contentType>application/pdf</contentType><version>Accepted Manuscript</version><cronfaStatus>true</cronfaStatus><embargoDate>2014-09-09T00:00:00.0000000</embargoDate><copyrightCorrect>true</copyrightCorrect></document></documents><OutputDurs/></rfc1807>
spelling 2023-01-30T14:53:59.0054785 v2 21456 2015-05-16 Three forms of physical measurement and their computability a0062e7cf6d68f05151560cdf9d14e75 0000-0002-3139-0983 Edwin Beggs Edwin Beggs true false 431b3060563ed44cc68c7056ece2f85e 0000-0003-4689-8760 John Tucker John Tucker true false 2015-05-16 SMA 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. Journal Article The Review of Symbolic Logic 7 4 618 646 measurement, experiment, physical oracles,Turing machines, non-uniform complexity classes 9 9 2014 2014-09-09 10.1017/S1755020314000240 http://journals.cambridge.org/action/displayAbstract?fromPage=online&amp;aid=9461557&amp;fileId=S1755020314000240 COLLEGE NANME Mathematics COLLEGE CODE SMA Swansea University 2023-01-30T14:53:59.0054785 2015-05-16T16:25:12.1271702 Faculty of Science and Engineering School of Mathematics and Computer Science - Mathematics Felix Costa 1 Edwin Beggs 0000-0002-3139-0983 2 John Tucker 0000-0003-4689-8760 3 0021456-31102016103554.pdf ThreeFormsOfPhysicalMeasurementAndTheirComputability.pdf 2016-10-31T10:35:54.4030000 Output 487874 application/pdf Accepted Manuscript true 2014-09-09T00:00:00.0000000 true
title Three forms of physical measurement and their computability
spellingShingle Three forms of physical measurement and their computability
Edwin Beggs
John Tucker
title_short Three forms of physical measurement and their computability
title_full Three forms of physical measurement and their computability
title_fullStr Three forms of physical measurement and their computability
title_full_unstemmed Three forms of physical measurement and their computability
title_sort Three forms of physical measurement and their computability
author_id_str_mv a0062e7cf6d68f05151560cdf9d14e75
431b3060563ed44cc68c7056ece2f85e
author_id_fullname_str_mv a0062e7cf6d68f05151560cdf9d14e75_***_Edwin Beggs
431b3060563ed44cc68c7056ece2f85e_***_John Tucker
author Edwin Beggs
John Tucker
author2 Felix Costa
Edwin Beggs
John Tucker
format Journal article
container_title The Review of Symbolic Logic
container_volume 7
container_issue 4
container_start_page 618
publishDate 2014
institution Swansea University
doi_str_mv 10.1017/S1755020314000240
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Mathematics{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Mathematics
url http://journals.cambridge.org/action/displayAbstract?fromPage=online&amp;aid=9461557&amp;fileId=S1755020314000240
document_store_str 1
active_str 0
description 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.
published_date 2014-09-09T03:25:27Z
_version_ 1763750893600112640
score 11.014291

Similar Items