{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:27:39Z","timestamp":1759638459594},"reference-count":31,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2012,9,6]],"date-time":"2012-09-06T00:00:00Z","timestamp":1346889600000},"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":[[2012,10]]},"abstract":"<jats:p>Using physical experiments as oracles for algorithms, we can characterise the computational power of classes of physical systems. Here we show that two different physical models of the apparatus for a single experiment can have different computational power. The experiment is the<jats:italic>scatter machine experiment<\/jats:italic>(SME), which was first presented in Beggs and Tucker (2007b). Our first physical model contained a wedge with a sharp vertex that made the experiment non-deterministic with constant runtime. We showed that Turing machines with polynomial time and an oracle based on a sharp wedge computed the non-uniform complexity class<jats:italic>P<\/jats:italic>\/<jats:italic>poly<\/jats:italic>. Here we reconsider the experiment with a refined physical model where the sharp vertex of the wedge is replaced by<jats:italic>any<\/jats:italic>suitable smooth curve with vertex at the same point. These smooth models of the experimental apparatus are deterministic. We show that<jats:italic>no matter what shape is chosen for the apparatus<\/jats:italic>:<jats:list list-type=\"number\"><jats:list-item><jats:label>(i)<\/jats:label><jats:p>the time of detection of the scattered particles increases at least exponentially with the size of the query; and<\/jats:p><\/jats:list-item><jats:list-item><jats:label>(ii)<\/jats:label><jats:p>Turing machines with polynomial time and an oracle based on a smooth wedge compute the non-uniform complexity class<jats:italic>P<\/jats:italic>\/<jats:italic>log<\/jats:italic>* \u2acb<jats:italic>P<\/jats:italic>\/<jats:italic>poly<\/jats:italic>.<\/jats:p><\/jats:list-item><\/jats:list>We discuss evidence that many experiments that measure quantities have exponential runtimes and a computational power of<jats:italic>P<\/jats:italic>\/<jats:italic>log<\/jats:italic>*.<\/jats:p>","DOI":"10.1017\/s0960129511000557","type":"journal-article","created":{"date-parts":[[2012,9,6]],"date-time":"2012-09-06T11:32:55Z","timestamp":1346931175000},"page":"853-879","source":"Crossref","is-referenced-by-count":13,"title":["The impact of models of a physical oracle on computational power"],"prefix":"10.1017","volume":"22","author":[{"given":"EDWIN J.","family":"BEGGS","sequence":"first","affiliation":[]},{"given":"JOS\u00c9 F\u00c9LIX","family":"COSTA","sequence":"additional","affiliation":[]},{"given":"JOHN V.","family":"TUCKER","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2012,9,6]]},"reference":[{"key":"S0960129511000557_ref22","doi-asserted-by":"publisher","DOI":"10.2307\/2273108"},{"key":"S0960129511000557_ref5","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2008.0085"},{"key":"S0960129511000557_ref29","doi-asserted-by":"publisher","DOI":"10.1112\/S0024611502013643"},{"key":"S0960129511000557_ref26","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198519737.001.0001","volume-title":"The Emperor's New Mind","author":"Penrose","year":"1989"},{"key":"S0960129511000557_ref23","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.64.2354"},{"key":"S0960129511000557_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85194-3_6"},{"key":"S0960129511000557_ref20","article-title":"Fundamentals of concept formation in empirical science","volume":"2","author":"Hempel","year":"1952","journal-title":"International Encyclopedia of Unified Science"},{"key":"S0960129511000557_ref25","volume-title":"Classical Recursion Theory, Studies in Logic and the Foundations of Mathematics","author":"Odifreddi","year":"1989"},{"key":"S0960129511000557_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.10.010"},{"key":"S0960129511000557_ref7","unstructured":"Beggs E. , Costa J. F. and Tucker J. V. (2008d) Quanta in classical mechanics: uncertainty in space, time, energy. In Proceedings of the Studia Logica International Conference on Logic and the Foundations of Physics: space, time and quanta (Trends in Logic VI)), Belgium, Brussels, 11-12 December."},{"key":"S0960129511000557_ref11","first-page":"155","volume-title":"Causality, Meaningful Complexity and Knowledge Construction","author":"Beggs","year":"2009"},{"key":"S0960129511000557_ref9","first-page":"137","article-title":"Physical experiments as oracles","volume":"97","author":"Beggs","year":"2009","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"S0960129511000557_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(81)90001-3"},{"key":"S0960129511000557_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2005.09.068"},{"key":"S0960129511000557_ref3","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2007.1835"},{"key":"S0960129511000557_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79228-4_2"},{"key":"S0960129511000557_ref13","first-page":"62","volume-title":"Programs, Proofs, Processes, 6th Conference on Computability in Europe, CiE 2010","author":"Beggs","year":"2010"},{"key":"S0960129511000557_ref8","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2008.0412"},{"key":"S0960129511000557_ref10","unstructured":"Beggs E. , Costa J. F. and Tucker J. V. (2009b) Physical oracles. Technical Report, Department of Computer Science, University of Swansea."},{"key":"S0960129511000557_ref14","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129510000356"},{"key":"S0960129511000557_ref15","doi-asserted-by":"crossref","unstructured":"Beggs E. , Costa J. F. and Tucker J. V. (2012a) Axiomatising physical experiments as oracles to algorithms. (In preparation.)","DOI":"10.1098\/rsta.2011.0427"},{"key":"S0960129511000557_ref17","volume-title":"An Account of the Principles of Measurement and Calculation","author":"Campbell","year":"1928"},{"key":"S0960129511000557_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00086-2"},{"key":"S0960129511000557_ref18","volume-title":"Philosophical Foundations of Physics","author":"Carnap","year":"1966"},{"key":"S0960129511000557_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01886519"},{"key":"S0960129511000557_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s11225-010-9254-6"},{"key":"S0960129511000557_ref21","first-page":"9","article-title":"A notion of mechanistic theory","volume":"47","author":"Kreisel","year":"1974","journal-title":"Synthese"},{"key":"S0960129511000557_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2005.09.075"},{"key":"S0960129511000557_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0707-8"},{"key":"S0960129511000557_ref30","doi-asserted-by":"publisher","DOI":"10.1145\/602382.602411"},{"key":"S0960129511000557_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2009.04.062"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129511000557","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,28]],"date-time":"2022-01-28T10:34:08Z","timestamp":1643366048000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129511000557\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,6]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["S0960129511000557"],"URL":"https:\/\/doi.org\/10.1017\/s0960129511000557","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9,6]]}}}