Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-28T22:43:28.952Z Has data issue: false hasContentIssue false
  • English
  • Français

The impact of models of a physical oracle on computational power†

Published online by Cambridge University Press:  06 September 2012

EDWIN J. BEGGS ,
JOSÉ FÉLIX COSTA  and
JOHN V. TUCKER
EDWIN J. BEGGS
Affiliation:
School of Physical Sciences, Swansea University, Singleton Park, Swansea, SA2 8PP, Wales, United Kingdom Email: [email protected]; [email protected]
JOSÉ FÉLIX COSTA
Affiliation:
Centro de Matemática e Aplicações Fundamentais, University of Lisbon, 1649-003 Lisboa, Portugal and Instituto Superior Técnico, Technical University of Lisbon, 1049-001 Lisboa, Portugal Email: [email protected]
JOHN V. TUCKER
Affiliation:
School of Physical Sciences, Swansea University, Singleton Park, Swansea, SA2 8PP, Wales, United Kingdom Email: [email protected]; [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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 scatter machine experiment (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 P/poly. Here we reconsider the experiment with a refined physical model where the sharp vertex of the wedge is replaced by any suitable smooth curve with vertex at the same point. These smooth models of the experimental apparatus are deterministic. We show that no matter what shape is chosen for the apparatus:

  1. (i) the time of detection of the scattered particles increases at least exponentially with the size of the query; and

  2. (ii) Turing machines with polynomial time and an oracle based on a smooth wedge compute the non-uniform complexity class P/log* ⫋ P/poly.

We discuss evidence that many experiments that measure quantities have exponential runtimes and a computational power of P/log*.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 22 , Special Issue 5: Computability of the Physical , October 2012 , pp. 853 - 879
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Beggs, E. and Tucker, J. V. (2006) Embedding infinitely parallel computation in Newtonian kinematics. Applied Mathematics and Computation 178 (1)25–43.CrossRefGoogle Scholar
Beggs, E. and Tucker, J. V. (2007a) Can Newtonian systems, bounded in space, time, mass and energy compute all functions? Theoretical Computer Science 371 (1)4–19.Google Scholar
Beggs, E. and Tucker, J. V. (2007b) Experimental computation of real numbers by Newtonian machines. Proceedings of the Royal Society, Series A (Mathematical, Physical and Engineering Sciences) 463 (2082)1541–1561.Google Scholar
Beggs, E., Costa, J. F., Loff, B. and Tucker, J. V. (2008a) On the complexity of measurement in classical physics. In: Agrawal, M., Du, D., Duan, Z. and Li, A. (eds.) Theory and Applications of Models of Computation (TAMC 2008). Springer-Verlag Lecture Notes in Computer Science 4978 20–30.Google Scholar
Beggs, E., Costa, J. F., Loff, B. and Tucker, J. V. (2008b) Computational complexity with experiments as oracles. Proceedings of the Royal Society, Series A (Mathematical, Physical and Engineering Sciences) 464 (2098)2777–2801.Google Scholar
Beggs, E., Costa, J. F., Loff, B. and Tucker, J. V. (2008c) Oracles and advice as measurements. In: Calude, C. S., Costa, J. F., Freund, R., Oswald, M. and Rozenberg, G. (eds.) Unconventional Computation (UC 2008). Springer-Verlag Lecture Notes in Computer Science 5204 33–50.Google Scholar
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.Google Scholar
Beggs, E., Costa, J. F., Loff, B. and Tucker, J. V. (2008e) Computational complexity with experiments as oracles II. Upper bounds. Proceedings of the Royal Society, Series A (Mathematical, Physical and Engineering Sciences) 465 (2105)1453–1465.Google Scholar
Beggs, E., Costa, J. F. and Tucker, J. V. (2009a) Physical experiments as oracles. Bulletin of the European Association for Theoretical Computer Science 97 137–151. (An invited paper for the ‘Natural Computing Column’.)Google Scholar
Beggs, E., Costa, J. F. and Tucker, J. V. (2009b) Physical oracles. Technical Report, Department of Computer Science, University of Swansea.Google Scholar
Beggs, E., Costa, J. F. and Tucker, J. V. (2009c) Computational Models of Measurement and Hempel's Axiomatization. In: Carsetti, A. (ed.) Causality, Meaningful Complexity and Knowledge Construction, Theory and Decision Library A 46, Springer-Verlag 155–184.Google Scholar
Beggs, E., Costa, J. F. and Tucker, J. V. (2010a) Physical oracles: The Turing machine and the Wheatstone bridge. In: Aerts, D., Smets, S. and Van Bendegem, J. P. (eds.) Special issue: The contributions of Logic to the Foundations of Physics. Studia Logica 95 271–292.Google Scholar
Beggs, E., Costa, J. F. and Tucker, J. V. (2010b) Comparing complexity classes relative to physical oracles. In: Ferreira, F., Guerra, H., Mayordomo, E. and Rasga, J. (eds.) Programs, Proofs, Processes, 6th Conference on Computability in Europe, CiE 2010, CMATI – Centre for Applied Mathematics and Information Technology, University of Azores 62–72.Google Scholar
Beggs, E., Costa, J. F. and Tucker, J. V. (2010c) Limits to measurement in experiments governed by algorithms. Mathematical Structures in Computer Science 20 1019–1050.Google Scholar
Beggs, E., Costa, J. F. and Tucker, J. V. (2012a) Axiomatising physical experiments as oracles to algorithms. (In preparation.)CrossRefGoogle Scholar
Bournez, O. and Cosnard, M. (1996) On the computational power of dynamical systems and hybrid systems. Theoretical Computer Science 168 (2)417–459.CrossRefGoogle Scholar
Campbell, N. R. (1928) An Account of the Principles of Measurement and Calculation, Longmans, Green and co.Google Scholar
Carnap, R. (1966) Philosophical Foundations of Physics, Basic Books.Google Scholar
Geroch, R. and Hartle, J. B. (1986) Computability and Physical Theories. Foundations of Physics 16 (6)533–550.CrossRefGoogle Scholar
Hempel, C. G. (1952) Fundamentals of concept formation in empirical science. International Encyclopedia of Unified Science 2 (7).Google Scholar
Kreisel, G. (1974) A notion of mechanistic theory. Synthese 47 9–24.Google Scholar
Kreisel, G. (1982) Review of Pour-El and Richards. Journal of Symbolic Logic 47 (4)900–902.CrossRefGoogle Scholar
Moore, C. (1990) Unpredictability and undecidability in dynamical systems. Physical Review Letters 64 (20)2354–2357.CrossRefGoogle ScholarPubMed
Németi, I. and Dávid, G. (2006) Relativistic computers and the Turing barrier. Applied Mathematics and Computation 178 (1)118–142.CrossRefGoogle Scholar
Odifreddi, P. (1989) Classical Recursion Theory, Studies in Logic and the Foundations of Mathematics 125, North Holland.Google Scholar
Penrose, R (1989) The Emperor's New Mind, Oxford University Press.Google Scholar
Pour-El, M. and Richards, I. (1981) The wave equation with computable initial data such that its unique solution is not computable. Advances in Mathematics 39 (4)215–239.Google Scholar
Siegelmann, H. T. (1999) Neural Networks and Analog Computation: Beyond the Turing Limit, Birkhäuser.Google Scholar
Weihrauch, K. and Zhong, N. (2002) Is wave propagation computable or can wave computers beat the Turing machine? Proceedings of the London Mathematical Society 85 (2)312–332.Google Scholar
Yao, A. C.-C. (2003) Classical physics and the Church–Turing thesis. Journal of the ACM 50 (1)100–105.CrossRefGoogle Scholar
Ziegler, M. (2009) Physically-relativized Church–Turing hypotheses: Physical foundations of computing and complexity theory of computational physics. Applied Mathematics and Computation 215 (4)1431–1447.CrossRefGoogle Scholar