Skip to main content
SpringerLink
Log in

Physical Oracles: The Turing Machine and the Wheatstone Bridge

  • Published:
Studia Logica Aims and scope Submit manuscript

Abstract

Earlier, we have studied computations possible by physical systems and by algorithms combined with physical systems. In particular, we have analysed the idea of using an experiment as an oracle to an abstract computational device, such as the Turing machine. The theory of composite machines of this kind can be used to understand (a) a Turing machine receiving extra computational power from a physical process, or (b) an experimenter modelled as a Turing machine performing a test of a known physical theory T.

Our earlier work was based upon experiments in Newtonian mechanics. Here we extend the scope of the theory of experimental oracles beyond Newtonian mechanics to electrical theory. First, we specify an experiment that measures resistance using a Wheatstone bridge and start to classify the computational power of this experimental oracle using non-uniform complexity classes. Secondly, we show that modelling an experimenter and experimental procedure algorithmically imposes a limit on our ability to measure resistance by the Wheatstone bridge.

The connection between the algorithm and physical test is mediated by a protocol controlling each query, especially the physical time taken by the experimenter. In our studies we find that physical experiments have an exponential time protocol; this we formulate as a general conjecture. Our theory proposes that measurability in Physics is subject to laws which are co-lateral effects of the limits of computability and computational complexity.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bachelard, Gaston, La Philosophy du Non. Pour une philosophie du nouvel esprit scientifique, Presses Universitaires de France, 1940.

  2. Bachelard, Gaston, The New Scientific Spirit, Beacon Press, 1985.

  3. Beggs, Edwin, José Félix Costa, Bruno Loff, and John V. Tucker, ‘Computational complexity with experiments as oracles’, Proceedings of the Royal Society, Series A (Mathematical, Physical and Engineering Sciences), 464 (2008), 2098, 2777–2801.

  4. Beggs, Edwin, José Félix Costa, Bruno Loff, and John V. Tucker, ‘On the complexity of measurement in classical physics’, in Manindra Agrawal, Dingzhu Du, Zhenhua Duan, and Angsheng Li, (eds.), Theory and Applications of Models of Computation (TAMC 2008), vol. 4978 of Lecture Notes in Computer Science, Springer, 2008, pp. 20–30.

  5. Beggs, Edwin, José Félix Costa, and John V. Tucker, ‘Quanta in classical mechanics: uncertainty in space, time, energy’, (2008). Accepted for presentation in Studia Logica International Conference on Logic and the Foundations of Physics: space, time and quanta (Trends in Logic VI), Belgium, Brussels, 11-12 December 2008.

  6. Beggs, Edwin, José Félix Costa, and John V. Tucker, ‘Computational Models of Measurement and Hempels Axiomatization’, in Arturo Carsetti, (ed.), Causality, Meaningful Complexity and Knowledge Construction, vol. 46 of Theory and Decision Library A, Springer, 2009, pp. 155–184.

  7. Beggs, Edwin, José Félix Costa, and John V. Tucker, ‘Physical experiments as oracles’, Bulletin of the European Association for Theoretical Computer Science, 97 (2009), 137–151. An invited paper for the “Natural Computing Column”.

  8. Beggs, Edwin, José Félix Costa, and John V. Tucker, ‘Limits to measurement in experiments governed by algorithms’, (2010), 33 pages. Submitted.

  9. Beggs Edwin, John V. Tucker: ‘Embedding infinitely parallel computation in Newtonian kinematics’. Applied Mathematics and Computation 178(1), 25–43 (2006)

    Article  Google Scholar 

  10. Beggs Edwin, John V. Tucker: ‘Can Newtonian, bounded in space, time, mass and energy compute all functions?’. Theoretical Computer Science 371(1), 4–19 (2007)

    Article  Google Scholar 

  11. Beggs, Edwin, and John V. Tucker, ‘Experimental computation of real numbers by Newtonian machines’, Proceedings of the Royal Society, Series A (Mathematical, Physical and Engineering Sciences), 463 (2007), 2082, 1541–1561.

  12. Bunge, Mario, Philosophy of Physics, Synthese Library, D. Reidel Publishing Company, 1973.

  13. Geroch Robert, James B. Hartle: ‘Computability and Physical Theories’. Foundations of Physics 16(6), 533–550 (1986)

    Article  Google Scholar 

  14. Hempel, Carl G., ‘Fundamentals of concept formation in empirical science’, International Encyclopedia of Unified Science, 2 (1952), 7.

  15. Jeans, Sir James, Physics and Philosophy, Dover, 1943, 1981.

  16. Radó Tibor: ‘On non-computable functions’. Bell System Technical Jourmal 41(3), 877–884 (1962)

    Google Scholar 

  17. Ziegler Martin: ‘Physically-relativized Church-Turing hypotheses: Physical foundations of computing and complexity theory of computational physics’. Applied Mathematics and Computation 215(4), 1431–1447 (2009)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Physical Sciences, Swansea University, Singleton Park, Swansea, SA2 8PP, Wales, United Kingdom

    Edwin J. Beggs & John V. Tucker

  2. Department of Mathematics, Instituto Superior Técnico, Universidade Técnica de Lisboa, Lisboa, Portugal

    José Félix Costa

  3. Centro de Matemática e Aplicações, Fundamentais do Complexo Interdisciplinar, Universidade de Lisboa, Lisboa, Portugal

    José Félix Costa

Authors
  1. Edwin J. Beggs
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. José Félix Costa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. John V. Tucker
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Edwin J. Beggs.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Beggs, E.J., Costa, J.F. & Tucker, J.V. Physical Oracles: The Turing Machine and the Wheatstone Bridge. Stud Logica 95, 279–300 (2010). https://doi.org/10.1007/s11225-010-9254-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11225-010-9254-6

Keywords

Search

Navigation