Journal article 1333 views 115 downloads
Classifying the computational power of stochastic physical oracles
John Tucker 
,
Edwin Beggs ,
Pedro Cortez,
Felix Costa
,
Edwin Beggs ,
Pedro Cortez,
Felix Costa
International Journal of Unconventional Computing, Volume: 14, Issue: 1, Pages: 59 - 90
Swansea University Authors:
John Tucker , Edwin Beggs
-
PDF | Accepted Manuscript
Download (420.86KB)
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...
| 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!
|
| 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. |
|---|---|
| College: |
Faculty of Science and Engineering |
| Issue: |
1 |
| Start Page: |
59 |
| End Page: |
90 |