Journal article 1243 views 97 downloads
Classifying the computational power of stochastic physical oracles
International Journal of Unconventional Computing, Volume: 14, Issue: 1, Pages: 59 - 90
Swansea University Authors:
John Tucker , Edwin Beggs
-
PDF | Accepted Manuscript
Download (420.86KB)
Abstract
Consider a computability and complexity theory in which theclassical set-theoretic oracle to a Turing machine is replaced bya physical process, and oracle queries return measurements ofphysical behaviour. The idea of such physical oracles is relevantto many disparate situations, but research has foc...
Published in: | International Journal of Unconventional Computing |
---|---|
ISSN: | 1548-7199 1548-7202 |
Published: |
2018
|
Online Access: |
Check full text
|
URI: | https://cronfa.swan.ac.uk/Record/cronfa43498 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
first_indexed |
2018-08-16T19:37:06Z |
---|---|
last_indexed |
2023-02-15T03:52:40Z |
id |
cronfa43498 |
recordtype |
SURis |
fullrecord |
<?xml version="1.0"?><rfc1807><datestamp>2023-02-14T15:56:10.2893827</datestamp><bib-version>v2</bib-version><id>43498</id><entry>2018-08-16</entry><title>Classifying the computational power of stochastic physical oracles</title><swanseaauthors><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><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></swanseaauthors><date>2018-08-16</date><deptcode>SCS</deptcode><abstract>Consider a computability and complexity theory in which theclassical set-theoretic oracle to a Turing machine is replaced bya physical process, and oracle queries return measurements ofphysical behaviour. The idea of such physical oracles is relevantto many disparate situations, but research has focussed on physicaloracles that were classic deterministic experiments whichmeasure physical quantities. In this paper, we broaden the scopeof the theory of physical oracles by tackling non-deterministicsystems. We examine examples of three types of non-determinism,namely systems that are: (1) physically nondeterministic,as in quantum phenomena; (2) physically deterministic butwhose physical theory is non-deterministic, as in statistical mechanics;and (3) physically deterministic but whose computationaltheory is non-deterministic caused by error margins. Physicaloracles that have probabilistic theories we call stochasticphysical oracles. We propose a set SPO of axioms for a basicform of stochastic oracles. We prove that Turing machinesequipped with a physical oracle satisfying the axioms SPO computeprecisely the non-uniform complexity class BPP//log* inpolynomial time. This result of BPP//log* is a computationallimit to a great range of classical and non-classical measurement,and of analogue-digital computation in polynomial time undergeneral conditions.</abstract><type>Journal Article</type><journal>International Journal of Unconventional Computing</journal><volume>14</volume><journalNumber>1</journalNumber><paginationStart>59</paginationStart><paginationEnd>90</paginationEnd><publisher/><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint>1548-7199</issnPrint><issnElectronic>1548-7202</issnElectronic><keywords/><publishedDay>1</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2018</publishedYear><publishedDate>2018-12-01</publishedDate><doi/><url>https://www.oldcitypublishing.com/journals/ijuc-home/ijuc-issue-contents/ijuc-volume-14-number-1-2018/ijuc-14-1-p-59-90/</url><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><funders/><projectreference/><lastEdited>2023-02-14T15:56:10.2893827</lastEdited><Created>2018-08-16T16:31:31.4807889</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>John</firstname><surname>Tucker</surname><orcid>0000-0003-4689-8760</orcid><order>1</order></author><author><firstname>Edwin</firstname><surname>Beggs</surname><orcid>0000-0002-3139-0983</orcid><order>2</order></author><author><firstname>Pedro</firstname><surname>Cortez</surname><order>3</order></author><author><firstname>Felix</firstname><surname>Costa</surname><order>4</order></author></authors><documents><document><filename>0043498-16082018163844.pdf</filename><originalFilename>ijuc.pdf</originalFilename><uploaded>2018-08-16T16:38:44.2130000</uploaded><type>Output</type><contentLength>395950</contentLength><contentType>application/pdf</contentType><version>Accepted Manuscript</version><cronfaStatus>true</cronfaStatus><embargoDate>2019-12-01T00:00:00.0000000</embargoDate><copyrightCorrect>true</copyrightCorrect><language>eng</language></document></documents><OutputDurs/></rfc1807> |
spelling |
2023-02-14T15:56:10.2893827 v2 43498 2018-08-16 Classifying the computational power of stochastic physical oracles 431b3060563ed44cc68c7056ece2f85e 0000-0003-4689-8760 John Tucker John Tucker true false a0062e7cf6d68f05151560cdf9d14e75 0000-0002-3139-0983 Edwin Beggs Edwin Beggs true false 2018-08-16 SCS Consider a computability and complexity theory in which theclassical set-theoretic oracle to a Turing machine is replaced bya physical process, and oracle queries return measurements ofphysical behaviour. The idea of such physical oracles is relevantto many disparate situations, but research has focussed on physicaloracles that were classic deterministic experiments whichmeasure physical quantities. In this paper, we broaden the scopeof the theory of physical oracles by tackling non-deterministicsystems. We examine examples of three types of non-determinism,namely systems that are: (1) physically nondeterministic,as in quantum phenomena; (2) physically deterministic butwhose physical theory is non-deterministic, as in statistical mechanics;and (3) physically deterministic but whose computationaltheory is non-deterministic caused by error margins. Physicaloracles that have probabilistic theories we call stochasticphysical oracles. We propose a set SPO of axioms for a basicform of stochastic oracles. We prove that Turing machinesequipped with a physical oracle satisfying the axioms SPO computeprecisely the non-uniform complexity class BPP//log* inpolynomial time. This result of BPP//log* is a computationallimit to a great range of classical and non-classical measurement,and of analogue-digital computation in polynomial time undergeneral conditions. Journal Article International Journal of Unconventional Computing 14 1 59 90 1548-7199 1548-7202 1 12 2018 2018-12-01 https://www.oldcitypublishing.com/journals/ijuc-home/ijuc-issue-contents/ijuc-volume-14-number-1-2018/ijuc-14-1-p-59-90/ COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2023-02-14T15:56:10.2893827 2018-08-16T16:31:31.4807889 Faculty of Science and Engineering School of Mathematics and Computer Science - Mathematics John Tucker 0000-0003-4689-8760 1 Edwin Beggs 0000-0002-3139-0983 2 Pedro Cortez 3 Felix Costa 4 0043498-16082018163844.pdf ijuc.pdf 2018-08-16T16:38:44.2130000 Output 395950 application/pdf Accepted Manuscript true 2019-12-01T00:00:00.0000000 true eng |
title |
Classifying the computational power of stochastic physical oracles |
spellingShingle |
Classifying the computational power of stochastic physical oracles John Tucker Edwin Beggs |
title_short |
Classifying the computational power of stochastic physical oracles |
title_full |
Classifying the computational power of stochastic physical oracles |
title_fullStr |
Classifying the computational power of stochastic physical oracles |
title_full_unstemmed |
Classifying the computational power of stochastic physical oracles |
title_sort |
Classifying the computational power of stochastic physical oracles |
author_id_str_mv |
431b3060563ed44cc68c7056ece2f85e a0062e7cf6d68f05151560cdf9d14e75 |
author_id_fullname_str_mv |
431b3060563ed44cc68c7056ece2f85e_***_John Tucker a0062e7cf6d68f05151560cdf9d14e75_***_Edwin Beggs |
author |
John Tucker Edwin Beggs |
author2 |
John Tucker Edwin Beggs Pedro Cortez Felix Costa |
format |
Journal article |
container_title |
International Journal of Unconventional Computing |
container_volume |
14 |
container_issue |
1 |
container_start_page |
59 |
publishDate |
2018 |
institution |
Swansea University |
issn |
1548-7199 1548-7202 |
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 |
https://www.oldcitypublishing.com/journals/ijuc-home/ijuc-issue-contents/ijuc-volume-14-number-1-2018/ijuc-14-1-p-59-90/ |
document_store_str |
1 |
active_str |
0 |
description |
Consider a computability and complexity theory in which theclassical set-theoretic oracle to a Turing machine is replaced bya physical process, and oracle queries return measurements ofphysical behaviour. The idea of such physical oracles is relevantto many disparate situations, but research has focussed on physicaloracles that were classic deterministic experiments whichmeasure physical quantities. In this paper, we broaden the scopeof the theory of physical oracles by tackling non-deterministicsystems. We examine examples of three types of non-determinism,namely systems that are: (1) physically nondeterministic,as in quantum phenomena; (2) physically deterministic butwhose physical theory is non-deterministic, as in statistical mechanics;and (3) physically deterministic but whose computationaltheory is non-deterministic caused by error margins. Physicaloracles that have probabilistic theories we call stochasticphysical oracles. We propose a set SPO of axioms for a basicform of stochastic oracles. We prove that Turing machinesequipped with a physical oracle satisfying the axioms SPO computeprecisely the non-uniform complexity class BPP//log* inpolynomial time. This result of BPP//log* is a computationallimit to a great range of classical and non-classical measurement,and of analogue-digital computation in polynomial time undergeneral conditions. |
published_date |
2018-12-01T03:54:42Z |
_version_ |
1763752733741940736 |
score |
11.021648 |