{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T10:17:42Z","timestamp":1648808262818},"reference-count":34,"publisher":"Cambridge University Press (CUP)","issue":"8","license":[{"start":{"date-parts":[[2016,6,23]],"date-time":"2016-06-23T00:00:00Z","timestamp":1466640000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2017,12]]},"abstract":"<jats:p>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 <jats:italic>Reviews of Symbolic Logic<\/jats:italic><jats:bold>7<\/jats:bold>(4) 618\u2013646), we observed that measurement can be viewed as a process of comparing a rational number <jats:italic>z<\/jats:italic> \u2013 a test quantity \u2013 with a real number <jats:italic>y<\/jats:italic> \u2013 an unknown quantity; each oracle call performs such a comparison. Experiments can then be classified into three categories, that correspond with being able to return test results\n<jats:disp-formula-group><jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0960129516000219_eqnU1\" \/><jats:tex-math>\n$$\\begin{eqnarray*}\nz &lt; y\\text{ or }z &gt; y\\text{ or }\\textit{timeout},\\\\\nz &lt; y\\text{ or }\\textit{timeout},\\\\\nz \\neq y\\text{ or }\\textit{timeout}.\n\\end{eqnarray*}\n$$<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula><\/jats:disp-formula-group>\nThese categories are called <jats:italic>two-sided<\/jats:italic>, <jats:italic>threshold<\/jats:italic> and <jats:italic>vanishing experiments<\/jats:italic>, respectively. The iterative process of comparing generates a real number <jats:italic>y<\/jats:italic>. The computational power of two-sided and threshold experiments were analysed in several papers, including Beggs et al. (2008 <jats:italic>Proceedings of the Royal Society, Series A (Mathematical, Physical and Engineering Sciences)<\/jats:italic><jats:bold>464<\/jats:bold> (2098) 2777\u20132801), Beggs et al. (2009 <jats:italic>Proceedings of the Royal Society, Series A (Mathematical, Physical and Engineering Sciences)<\/jats:italic><jats:bold>465<\/jats:bold> (2105) 1453\u20131465), Beggs et al. (2013a <jats:italic>Unconventional Computation and Natural Computation (UCNC 2013)<\/jats:italic>, Springer-Verlag 6\u201318), Beggs et al. (2010b <jats:italic>Mathematical Structures in Computer Science<\/jats:italic><jats:bold>20<\/jats:bold> (06) 1019\u20131050) and Beggs et al. (2014 <jats:italic>Reviews of Symbolic Logic<\/jats:italic>, 7 (4):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\u2013Turing barrier.<\/jats:p>","DOI":"10.1017\/s0960129516000219","type":"journal-article","created":{"date-parts":[[2016,6,23]],"date-time":"2016-06-23T09:55:57Z","timestamp":1466675757000},"page":"1315-1363","source":"Crossref","is-referenced-by-count":2,"title":["Computations with oracles that measure vanishing quantities"],"prefix":"10.1017","volume":"27","author":[{"given":"EDWIN","family":"BEGGS","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JOS\u00c9 F\u00c9LIX","family":"COSTA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DIOGO","family":"PO\u00c7AS","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JOHN V.","family":"TUCKER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2016,6,23]]},"reference":[{"key":"S0960129516000219_ref16","volume-title":"Hybrid Computation","author":"Bekey","year":"1968"},{"key":"S0960129516000219_ref22","unstructured":"Krantz D.H. , Suppes P. , DuncanAAAALuce R. and Tversky A. (1990). Foundations of Measurement, vol. 1 (1971), vol. 2 (1989) and vol. 3 (1990), Academic Press."},{"key":"S0960129516000219_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S1755020314000240"},{"key":"S0960129516000219_ref6","first-page":"155","volume-title":"Causality, Meaningful Complexity and Knowledge Construction","author":"Beggs","year":"2010"},{"key":"S0960129516000219_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-75357-2"},{"key":"S0960129516000219_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01886519"},{"key":"S0960129516000219_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129510000356"},{"key":"S0960129516000219_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/BF00484949"},{"key":"S0960129516000219_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.10.010"},{"key":"S0960129516000219_ref10","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.2011.0427"},{"key":"S0960129516000219_ref34","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2009.04.062"},{"key":"S0960129516000219_ref24","first-page":"1280","article-title":"Representing measurement results","volume":"15","author":"Pauly","year":"2009","journal-title":"Journal of Universal Computer Science"},{"key":"S0960129516000219_ref19","volume-title":"Philosophical Foundations of Physics","author":"Carnap","year":"1966"},{"key":"S0960129516000219_ref9","first-page":"62","volume-title":"Physics and Computation, PandC 2010","author":"Beggs","year":"2010"},{"key":"S0960129516000219_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2005.09.068"},{"key":"S0960129516000219_ref2","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2008.0085"},{"key":"S0960129516000219_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56999-9"},{"key":"S0960129516000219_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00086-2"},{"key":"S0960129516000219_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(81)90001-3"},{"key":"S0960129516000219_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129511000557"},{"key":"S0960129516000219_ref32","doi-asserted-by":"publisher","DOI":"10.1112\/S0024611502013643"},{"key":"S0960129516000219_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39074-6_3"},{"key":"S0960129516000219_ref3","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2008.0412"},{"key":"S0960129516000219_ref5","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/ext047"},{"key":"S0960129516000219_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90178-3"},{"key":"S0960129516000219_ref26","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1974-0347575-8"},{"key":"S0960129516000219_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.07.001"},{"key":"S0960129516000219_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s11225-010-9254-6"},{"key":"S0960129516000219_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(79)90021-4"},{"key":"S0960129516000219_ref21","volume-title":"International Encyclopedia of Unified Science","author":"Hempel","year":"1952"},{"key":"S0960129516000219_ref25","first-page":"139","article-title":"Relative computability and uniform continuity of relations","volume":"5","author":"Pauly","year":"2013","journal-title":"Journal of Logic and Analysis"},{"key":"S0960129516000219_ref17","volume-title":"Principles of Optics. Electromagnetic Theory of Propagation, Interference and Diffraction of Light","author":"Born","year":"1964"},{"key":"S0960129516000219_ref15","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2007.1835"},{"key":"S0960129516000219_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21717-7"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129516000219","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,15]],"date-time":"2019-04-15T22:19:08Z","timestamp":1555366748000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129516000219\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,23]]},"references-count":34,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["S0960129516000219"],"URL":"https:\/\/doi.org\/10.1017\/s0960129516000219","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,23]]}}}