Journal article 1474 views 222 downloads
Three forms of physical measurement and their computability
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 |
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>MACS</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;aid=9461557&amp;fileId=S1755020314000240</url><notes/><college>COLLEGE NANME</college><department>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</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 MACS 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&aid=9461557&fileId=S1755020314000240 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS 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&aid=9461557&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-09T12:45:44Z |
_version_ |
1821409588936704000 |
score |
11.080252 |