Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-19T12:19:05.021Z Has data issue: false hasContentIssue false
  • English
  • Français

Limits to measurement in experiments governed by algorithms†

Published online by Cambridge University Press:  08 November 2010

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:
Instituto Superior Técnico, Technical University of Lisbon, 1049-001 Lisboa, Portugal and Centro de Matemática e Aplicações Fundamentais, University of Lisbon, 1649-003 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

We pose the following question: If a physical experiment were to be completely controlled by an algorithm, what effect would the algorithm have on the physical measurements made possible by the experiment?

In a programme to study the nature of computation possible by physical systems, and by algorithms coupled with physical systems, we have begun to analyse:

  1. (i) the algorithmic nature of experimental procedures; and

  2. (ii) the idea of using a physical experiment as an oracle to Turing Machines.

To answer the question, we will extend our theory of experimental oracles so that we can use Turing machines to model the experimental procedures that govern the conduct of physical experiments. First, we specify an experiment that measures mass via collisions in Newtonian dynamics and examine its properties in preparation for its use as an oracle. We begin the classification of the computational power of polynomial time Turing machines with this experimental oracle using non-uniform complexity classes. Second, we show that modelling an experimenter and experimental procedure algorithmically imposes a limit on what can be measured using equipment. Indeed, the theorems suggest a new form of uncertainty principle for our knowledge of physical quantities measured in simple physical experiments. We argue that the results established here are representative of a huge class of experiments.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 20 , Special Issue 6: Quantum Algorithms , December 2010 , pp. 1019 - 1050
Copyright
Copyright © Cambridge University Press 2010

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

Bachelard, G. (1934) Le nouvel esprit scientifique. (English translation: Goldhammer, A. (1985) The New Scientific Spirit, Beacon Press.)Google Scholar
Bachelard, G. (1940) La Philosophy du Non. Pour une philosophie du nouvel esprit scientifique, Presses Universitaires de France.Google Scholar
Balcázar, J. L. and Hermo, M. (1998) The structure of logarithmic advice complexity classes. Theoretical Computer Science 207 (1)217–244.CrossRefGoogle Scholar
Balcázar, J. L., Días, J. and Gabarró, J. (1988) Structural Complexity I, Springer-Verlag (2nd Edition 1995).CrossRefGoogle Scholar
Balcázar, J. L., Días, J. and Gabarró, J. (1990) Structural Complexity II, Springer-Verlag.CrossRefGoogle Scholar
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.CrossRefGoogle 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. and Tucker, J. V. (2008) Programming experimental procedures for Newtonian kinematic machines. In: Beckmann, A., Dimitracopoulos, C. and Löwe, B. (eds.) Proceedings of the 4th conference on Computability in Europe: Logic and Theory of Algorithms. Springer-Verlag Lecture Notes in Computer Science 5028 52–66.CrossRefGoogle Scholar
Beggs, E., Costa, J. F., Loff, B. and Tucker, J. V. (2008a) On the Complexity of Measurement in Classical Physics. Theory and Applications of Models of Computation (TAMC 2008), Xi'an, China. Springer-Verlag Lecture Notes in Computer Science 4978 20–30.CrossRefGoogle 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.) Proceedings UC 2008 – 7th International Conference on Unconventional Computation. Springer-Verlag Lecture Notes in Computer Science 5204 33–50.CrossRefGoogle Scholar
Beggs, E., Costa, J. F., Loff, B. and Tucker, J. V. (2009a) 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. (2009b) Unifying science through computation: Reflections on computability and physics. New Approaches to the Unity of Science, Vol. II: Special Sciences and the Unity of Science – Logic, Epistemology, and the Unity of Science, Springer-Verlag (in press).Google Scholar
Beggs, E., Costa, J. F. and Tucker, J. V. (2009c) Comparing complexity classes relative to physical oracles (technical report).Google Scholar
Beggs, E., Costa, J. F. and Tucker, J. V. (2009d) Computational Models of Measurement and Hempel's Axiomatization. In: Carsetti, A. (ed.) Causality, Meaningful Complexity and Embodied Cognition. Theory and Decision Library A 46, Springer-Verlag 155–184.Google Scholar
Beggs, E., Costa, J. F. and Tucker, J. V. (2009e) The impact of limits of computation on a physical experiment (technical report).Google Scholar
Beggs, E., Costa, J. F. and Tucker, J. V. (2010) Physical oracles: The Turing machine and the Wheatstone bridge. In: Aerts, D., Smets, S. and Van Bendegem, J. P. (eds.) The contributions of Logic to the Foundations of Physics. Studia Logica 95 217–292.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
Brady, A. H. (1994) The busy beaver game and the meaning of life. In: Herken, R. (ed.) The Universal Turing Machine: A Half-Century Survey, 2nd Edition, Springer-Verlag 237–254.Google Scholar
Cooper, S. B. (2004) Computability Theory, Chapman and Hall.Google Scholar
Eddington, A. S. (1933) The Expanding Universe, Cambridge University Press.Google Scholar
Froda, A. (1959) La finitude en mécanique classique, ses axiomes et leurs implications. In: Henkin, L., Suppes, P. and Tarski, A. (eds.) The Axiomatic Method, with Special Reference to Geometry and Physics, Studies in Logic and the Foundations of Mathematics, North-Holland.Google Scholar
Hamming, R. W. (1989) Digital Filters, (2nd Edition)Prentice-Hall.Google Scholar
Hempel, C. G. (1952) Fundamentals of Concept Formation in Empirical Science. International Encyclopedia of Unified Science, 2 (7) University of Chicago Press.Google Scholar
Krantz, D. H., Suppes, P., Luce, R. D. and Tversky, A. (2009) Foundations of Measurement, Dover.Google Scholar
Popper, K. R. (1950) Indeterminism in quantum physics and in classical physics. The British Journal for the Philosophy of Science 1 (2)117–133.CrossRefGoogle Scholar
Popper, K. R. (1950) Indeterminism in quantum physics and in classical physics (Part II). The British Journal for the Philosophy of Science 1 (3)173–195.CrossRefGoogle Scholar
Radó, T. (1962) On non-computable functions. Bell System Tech. J. 41 (3)877–884.CrossRefGoogle Scholar
Siegelmann, H. (1999) Neural Networks and Analog Computation: Beyond the Turing Limit, Birkhäuser.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