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.
Similar content being viewed by others
References
Bachelard, Gaston, La Philosophy du Non. Pour une philosophie du nouvel esprit scientifique, Presses Universitaires de France, 1940.
Bachelard, Gaston, The New Scientific Spirit, Beacon Press, 1985.
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.
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.
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.
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.
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”.
Beggs, Edwin, José Félix Costa, and John V. Tucker, ‘Limits to measurement in experiments governed by algorithms’, (2010), 33 pages. Submitted.
Beggs Edwin, John V. Tucker: ‘Embedding infinitely parallel computation in Newtonian kinematics’. Applied Mathematics and Computation 178(1), 25–43 (2006)
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)
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.
Bunge, Mario, Philosophy of Physics, Synthese Library, D. Reidel Publishing Company, 1973.
Geroch Robert, James B. Hartle: ‘Computability and Physical Theories’. Foundations of Physics 16(6), 533–550 (1986)
Hempel, Carl G., ‘Fundamentals of concept formation in empirical science’, International Encyclopedia of Unified Science, 2 (1952), 7.
Jeans, Sir James, Physics and Philosophy, Dover, 1943, 1981.
Radó Tibor: ‘On non-computable functions’. Bell System Technical Jourmal 41(3), 877–884 (1962)
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)
Author information
Authors and Affiliations
Corresponding author
Rights 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
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11225-010-9254-6