Journal article 376 views 65 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
PDF | Accepted ManuscriptDownload (688.17KB)
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...
|Published in:||Mathematical Structures in Computer Science|
Check full text
No Tags, Be the first to tag this record!
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.
computational theory of measurement, vanishing experiments, physical oracles,
College of Science