No Cover Image

Journal article 1839 views

Computational complexity with experiments as oracles

Edwin Beggs Orcid Logo, José Félix Costa, Bruno Loff, John Tucker Orcid Logo

Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, Volume: 464, Issue: 2098, Pages: 2777 - 2801

Swansea University Authors: Edwin Beggs Orcid Logo, 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/rspa.2008.0085

Abstract

We discuss combining physical experiments with machine computations and introduce a form of analogue–digital (AD) Turing machine. We examine in detail a case study where an experimental procedure based on Newtonian kinematics is combined with a class of Turing machines. Three forms of AD machine are...

Full description

Published in: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
ISSN: 1471-2946
Published: London The Royal Society 2008
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa7205
first_indexed 2013-07-23T11:57:35Z
last_indexed 2018-02-09T04:35:07Z
id cronfa7205
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2015-10-15T10:30:07.0465773</datestamp><bib-version>v2</bib-version><id>7205</id><entry>2012-02-23</entry><title>Computational complexity with experiments as oracles</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>2012-02-23</date><deptcode>MACS</deptcode><abstract>We discuss combining physical experiments with machine computations and introduce a form of analogue&#x2013;digital (AD) Turing machine. We examine in detail a case study where an experimental procedure based on Newtonian kinematics is combined with a class of Turing machines. Three forms of AD machine are studied, in which physical parameters can be set exactly and approximately. Using non-uniform complexity theory, and some probability, we prove theorems that show that these machines can compute more than classical Turing machines.</abstract><type>Journal Article</type><journal>Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences</journal><volume>464</volume><journalNumber>2098</journalNumber><paginationStart>2777</paginationStart><paginationEnd>2801</paginationEnd><publisher>The Royal Society</publisher><placeOfPublication>London</placeOfPublication><issnPrint>1471-2946</issnPrint><issnElectronic/><keywords>algorithmic procedure; experimental procedure; Turing machines with oracles; analogue&#x2013;digital computation; non-uniform complexity</keywords><publishedDay>31</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2008</publishedYear><publishedDate>2008-12-31</publishedDate><doi>10.1098/rspa.2008.0085</doi><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/><lastEdited>2015-10-15T10:30:07.0465773</lastEdited><Created>2012-02-23T17:01:48.0000000</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>Edwin</firstname><surname>Beggs</surname><orcid>0000-0002-3139-0983</orcid><order>1</order></author><author><firstname>Jos&#xE9; F&#xE9;lix</firstname><surname>Costa</surname><order>2</order></author><author><firstname>Bruno</firstname><surname>Loff</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 2015-10-15T10:30:07.0465773 v2 7205 2012-02-23 Computational complexity with experiments as oracles a0062e7cf6d68f05151560cdf9d14e75 0000-0002-3139-0983 Edwin Beggs Edwin Beggs true false 431b3060563ed44cc68c7056ece2f85e 0000-0003-4689-8760 John Tucker John Tucker true false 2012-02-23 MACS We discuss combining physical experiments with machine computations and introduce a form of analogue–digital (AD) Turing machine. We examine in detail a case study where an experimental procedure based on Newtonian kinematics is combined with a class of Turing machines. Three forms of AD machine are studied, in which physical parameters can be set exactly and approximately. Using non-uniform complexity theory, and some probability, we prove theorems that show that these machines can compute more than classical Turing machines. Journal Article Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 464 2098 2777 2801 The Royal Society London 1471-2946 algorithmic procedure; experimental procedure; Turing machines with oracles; analogue–digital computation; non-uniform complexity 31 12 2008 2008-12-31 10.1098/rspa.2008.0085 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University 2015-10-15T10:30:07.0465773 2012-02-23T17:01:48.0000000 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Edwin Beggs 0000-0002-3139-0983 1 José Félix Costa 2 Bruno Loff 3 John Tucker 0000-0003-4689-8760 4
title Computational complexity with experiments as oracles
spellingShingle Computational complexity with experiments as oracles
Edwin Beggs
John Tucker
title_short Computational complexity with experiments as oracles
title_full Computational complexity with experiments as oracles
title_fullStr Computational complexity with experiments as oracles
title_full_unstemmed Computational complexity with experiments as oracles
title_sort Computational complexity with experiments as oracles
author_id_str_mv a0062e7cf6d68f05151560cdf9d14e75
431b3060563ed44cc68c7056ece2f85e
author_id_fullname_str_mv a0062e7cf6d68f05151560cdf9d14e75_***_Edwin Beggs
431b3060563ed44cc68c7056ece2f85e_***_John Tucker
author Edwin Beggs
John Tucker
author2 Edwin Beggs
José Félix Costa
Bruno Loff
John Tucker
format Journal article
container_title Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
container_volume 464
container_issue 2098
container_start_page 2777
publishDate 2008
institution Swansea University
issn 1471-2946
doi_str_mv 10.1098/rspa.2008.0085
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 discuss combining physical experiments with machine computations and introduce a form of analogue–digital (AD) Turing machine. We examine in detail a case study where an experimental procedure based on Newtonian kinematics is combined with a class of Turing machines. Three forms of AD machine are studied, in which physical parameters can be set exactly and approximately. Using non-uniform complexity theory, and some probability, we prove theorems that show that these machines can compute more than classical Turing machines.
published_date 2008-12-31T10:11:44Z
_version_ 1850662720487030784
score 11.088971

Similar Items