No Cover Image

Journal article 350 views 61 downloads

Computations with oracles that measure vanishing quantities / EDWIN BEGGS; JOSÉ FÉLIX COSTA; DIOGO POÇAS; JOHN V. TUCKER

Mathematical Structures in Computer Science, Pages: 1 - 49

Swansea University Author: Tucker, John

Abstract

We consider computation with real numbers that arise through a process of physical measurement. We have developed a theory in which physical experiments that measure quantities can be used as oracles to algorithms and we have begun to classify the computational power of various forms of experiment u...

Full description

Published in: Mathematical Structures in Computer Science
ISSN: 0960-1295 1469-8072
Published: 2016
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa30884
Tags: Add Tag
No Tags, Be the first to tag this record!
Abstract: We consider computation with real numbers that arise through a process of physical measurement. We have developed a theory in which physical experiments that measure quantities can be used as oracles to algorithms and we have begun to classify the computational power of various forms of experiment using non-uniform complexity classes. Earlier, in Beggs et al. (2014 Reviews of Symbolic Logic 7(4) (2014) 618–646), we observed that measurement can be viewed as a process of comparing a rational number z – a test quantity – with a real number y – an unknown quantity; each oracle call performs such a comparison. Experiments can then be classified into three categories called two-sided, threshold and vanishing experiments, respectively. The iterative process of comparing generates a real number y. The computational power of two-sided and threshold experiments were analysed in several papers, e.g., Beggs et al., Proceedings of the Royal Society, Series A (Mathematical, Physical and Engineering Sciences) 464 (2008) 2777–2801; Beggs et al., Proceedings of the Royal Society, Series A (Mathematical, Physical and Engineering Sciences) 465 (2105) 1453–1465; Beggs et al., Mathematical Structures in Computer Science 20 (06) (2010) 1019–1050; and Beggs et al., Reviews of Symbolic Logic, 7 (4) (2014):618-646. In this paper, we attack the subtle problem of measuring physical quantities that vanish in some experimental conditions (e.g., Brewster's angle in optics). We analyse in detail a simple generic vanishing experiment for measuring mass and develop general techniques based on parallel experiments, statistical analysis and timing notions that enable us to prove lower and upper bounds for its computational power in different variants. We end with a comparison of various results for all three forms of experiments and a suitable postulate for computation involving analogue inputs that breaks the Church–Turing barrier.
Keywords: computational theory of measurement, vanishing experiments, physical oracles,
College: College of Science
Start Page: 1
End Page: 49