Journal article 1092 views
Axiomatizing physical experiments as oracles to algorithms
Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, Volume: 370, Issue: 1971, Pages: 3359 - 3384
Swansea University Author:
John Tucker
Full text not available from this repository: check for access using links below.
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...
| 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: |
Faculty of Science and Engineering |
| Issue: |
1971 |
| Start Page: |
3359 |
| End Page: |
3384 |