No Cover Image

Journal article 192 views 1 download

Classifying the computational power of stochastic physical oracles / Edwin, Beggs; John, Tucker

International Journal of Unconventional Computing, Volume: 14, Issue: 1, Pages: 59 - 90

Swansesa University Authors: Edwin, Beggs, John, Tucker

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...

Full description

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: College of Science
Issue: 1
Start Page: 59
End Page: 90