No Cover Image

Journal article 1333 views 115 downloads

Classifying the computational power of stochastic physical oracles

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

International Journal of Unconventional Computing, Volume: 14, Issue: 1, Pages: 59 - 90

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

Check full text

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

Full description

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

Similar Items