No Cover Image

Journal article 976 views

Axiomatizing physical experiments as oracles to algorithms

E. J. Beggs, J. F. Costa, J. V. Tucker, John Tucker Orcid Logo

Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, Volume: 370, Issue: 1971, Pages: 3359 - 3384

Swansea University Author: John Tucker Orcid Logo

Full text not available from this repository: check for access using links below.

Check full text

DOI (Published version): 10.1098/rsta.2011.0427

Abstract

We developed earlier a theory of combining algorithms with physical systems, on the basis of using physical experiments as oracles to algorithms. Although our concepts and methods are general, each physical oracle requires its own analysis, on the basis of some fragment of physical theory that speci...

Full description

Published in: Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences
ISSN: 1364-503X 1471-2962
Published: London The Royal Society 2012
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa12755
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2013-07-23T12:08:42Z
last_indexed 2018-02-09T04:42:59Z
id cronfa12755
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2017-12-18T10:25:45.9942815</datestamp><bib-version>v2</bib-version><id>12755</id><entry>2012-09-19</entry><title>Axiomatizing physical experiments as oracles to algorithms</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></swanseaauthors><date>2012-09-19</date><deptcode>SCS</deptcode><abstract>We developed earlier a theory of combining algorithms with physical systems, on the basis of using physical experiments as oracles to algorithms. Although our concepts and methods are general, each physical oracle requires its own analysis, on the basis of some fragment of physical theory that specifies the equipment and its behaviour. For specific examples of physical systems (mechanical, optical, electrical), the computational power has been characterized using non-uniform complexity classes. The powers of the known examples vary according to assumptions on precision and timing but seem to lead to the same complexity classes, namely P/ log and BPP// log. In this study, we develop sets of axioms for the interface between physical equipment and algorithms that allow us to prove general characterizations, in terms of P/ log and BPP// log, for large classes of physical oracles, in a uniform way. Sufficient conditions on physical equipment are giventhat ensure a physical system satisfies the axioms.</abstract><type>Journal Article</type><journal>Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences</journal><volume>370</volume><journalNumber>1971</journalNumber><paginationStart>3359</paginationStart><paginationEnd>3384</paginationEnd><publisher>The Royal Society</publisher><placeOfPublication>London</placeOfPublication><issnPrint>1364-503X</issnPrint><issnElectronic>1471-2962</issnElectronic><keywords>Turing machines; oracles; experiments; measurement; complexity classes; computability</keywords><publishedDay>31</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2012</publishedYear><publishedDate>2012-12-31</publishedDate><doi>10.1098/rsta.2011.0427</doi><url/><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2017-12-18T10:25:45.9942815</lastEdited><Created>2012-09-19T23:51:34.7544579</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>E. J.</firstname><surname>Beggs</surname><order>1</order></author><author><firstname>J. F.</firstname><surname>Costa</surname><order>2</order></author><author><firstname>J. V.</firstname><surname>Tucker</surname><order>3</order></author><author><firstname>John</firstname><surname>Tucker</surname><orcid>0000-0003-4689-8760</orcid><order>4</order></author></authors><documents/><OutputDurs/></rfc1807>
spelling 2017-12-18T10:25:45.9942815 v2 12755 2012-09-19 Axiomatizing physical experiments as oracles to algorithms 431b3060563ed44cc68c7056ece2f85e 0000-0003-4689-8760 John Tucker John Tucker true false 2012-09-19 SCS We developed earlier a theory of combining algorithms with physical systems, on the basis of using physical experiments as oracles to algorithms. Although our concepts and methods are general, each physical oracle requires its own analysis, on the basis of some fragment of physical theory that specifies the equipment and its behaviour. For specific examples of physical systems (mechanical, optical, electrical), the computational power has been characterized using non-uniform complexity classes. The powers of the known examples vary according to assumptions on precision and timing but seem to lead to the same complexity classes, namely P/ log and BPP// log. In this study, we develop sets of axioms for the interface between physical equipment and algorithms that allow us to prove general characterizations, in terms of P/ log and BPP// log, for large classes of physical oracles, in a uniform way. Sufficient conditions on physical equipment are giventhat ensure a physical system satisfies the axioms. Journal Article Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 370 1971 3359 3384 The Royal Society London 1364-503X 1471-2962 Turing machines; oracles; experiments; measurement; complexity classes; computability 31 12 2012 2012-12-31 10.1098/rsta.2011.0427 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2017-12-18T10:25:45.9942815 2012-09-19T23:51:34.7544579 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science E. J. Beggs 1 J. F. Costa 2 J. V. Tucker 3 John Tucker 0000-0003-4689-8760 4
title Axiomatizing physical experiments as oracles to algorithms
spellingShingle Axiomatizing physical experiments as oracles to algorithms
John Tucker
title_short Axiomatizing physical experiments as oracles to algorithms
title_full Axiomatizing physical experiments as oracles to algorithms
title_fullStr Axiomatizing physical experiments as oracles to algorithms
title_full_unstemmed Axiomatizing physical experiments as oracles to algorithms
title_sort Axiomatizing physical experiments as oracles to algorithms
author_id_str_mv 431b3060563ed44cc68c7056ece2f85e
author_id_fullname_str_mv 431b3060563ed44cc68c7056ece2f85e_***_John Tucker
author John Tucker
author2 E. J. Beggs
J. F. Costa
J. V. Tucker
John Tucker
format Journal article
container_title Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences
container_volume 370
container_issue 1971
container_start_page 3359
publishDate 2012
institution Swansea University
issn 1364-503X
1471-2962
doi_str_mv 10.1098/rsta.2011.0427
publisher The Royal Society
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 - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
document_store_str 0
active_str 0
description We developed earlier a theory of combining algorithms with physical systems, on the basis of using physical experiments as oracles to algorithms. Although our concepts and methods are general, each physical oracle requires its own analysis, on the basis of some fragment of physical theory that specifies the equipment and its behaviour. For specific examples of physical systems (mechanical, optical, electrical), the computational power has been characterized using non-uniform complexity classes. The powers of the known examples vary according to assumptions on precision and timing but seem to lead to the same complexity classes, namely P/ log and BPP// log. In this study, we develop sets of axioms for the interface between physical equipment and algorithms that allow us to prove general characterizations, in terms of P/ log and BPP// log, for large classes of physical oracles, in a uniform way. Sufficient conditions on physical equipment are giventhat ensure a physical system satisfies the axioms.
published_date 2012-12-31T03:14:40Z
_version_ 1763750214634569728
score 11.014291

Similar Items