No Cover Image

Journal article 497 views

Axiomatizing physical experiments as oracles to algorithms / E. J. Beggs; J. F. Costa; J. V. Tucker

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

Swansea University Author: Tucker, John

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!
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.
Keywords: Turing machines; oracles; experiments; measurement; complexity classes; computability
College: College of Science
Issue: 1971
Start Page: 3359
End Page: 3384