World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

The Power of Machines That Control Experiments

    https://doi.org/10.1142/S0129054122500010Cited by:0 (Source: Crossref)

    We consider the experimenter (e.g. the experimental physicist) as a Turing machine — the digital component — and the experiment of measurement — the analog component — as an oracle to the Turing machine. The algorithm running in the machine abstracts the experimental method of measurement (encoding the recursive structure of experimental actions) chosen by the experimenter. In this paper we prove that the central analogue-digital complexity classes P, P/poly and P/polyREC can be characterized in terms of protocols to perform measurements controlled by standard Turing machines.

    Communicated by Martin Kutrib

    References

    • 1. J. Alírio, J. F. Costa and L. Fonseca, Scatter machines bounded in space, in Handbook of Unconventional Computing, Volume 1 (Theory), ed. A. Adamatzky, Chapter 3 (World Scientific, Singapore, 2021), pp. 59–97. LinkGoogle Scholar
    • 2. T. Ambaram, E. Beggs, J. F. Costa, D. Poças and J. V. Tucker, An analogue-digital model of computation: Turing machines with physical oracles, in Advances in Unconventional Computing, Volume 1 (Theory), ed. A. Adamatzky, Emergence, Complexity and Computation , Vol. 22 (Springer, 2016), pp. 73–115. Google Scholar
    • 3. J. L. Balcázar, J. Días and J. Gabarró, Structural Complexity I, 2nd edn. (Springer-Verlag, 1988, 1995). CrossrefGoogle Scholar
    • 4. E. Beggs, J. F. Costa, B. Loff and J. V. Tucker, Computational complexity with experiments as oracles, Proc. Royal Society, Series A (Mathematical, Physical and Engineering Sciences) 464(2098) (2008) 2777–2801. CrossrefGoogle Scholar
    • 5. E. Beggs, J. F. Costa, B. Loff and J. V. Tucker, Computational complexity with experiments as oracles II. Upper bounds, Proc. Royal Society, Series A (Mathematical, Physical and Engineering Sciences) 465(2105) (2009) 1453–1465. CrossrefGoogle Scholar
    • 6. E. Beggs, J. F. Costa, D. Poças and J. V. Tucker, On the power of threshold measurements as oracles, in Unconventional Computation and Natural Computation (UCNC 2013), eds. G. MauriA. DennunzioL. ManzoniE. Porreca, Lecture Notes in Computer Science, Vol. 7956 (Springer, 2013), pp. 6–18. CrossrefGoogle Scholar
    • 7. E. Beggs, J. F. Costa, D. Poças and J. V. Tucker, Oracles that measure thresholds: The Turing machine and the broken balance, J. Logic Comput. 23(6) (2013) 1155–1181. Crossref, Web of ScienceGoogle Scholar
    • 8. E. Beggs, J. F. Costa, D. Poças and J. V. Tucker, An analogue-digital Church–Turing thesis, Int. J. Found. Comput. Sci. 25(4) (2014) 373–389. Link, Web of ScienceGoogle Scholar
    • 9. E. Beggs, J. F. Costa, D. Poças and J. V. Tucker, Computations with oracles that measure vanishing quantities, Math. Struct. Comput. Sci. 23(6) (2017) 1155–1181. Google Scholar
    • 10. E. Beggs, P. Cortez, J. F. Costa and J. V. Tucker, A hierarchy for BPP//log* based on counting calls to an oracle, in Emergent Computation (Festschrift for Selim Akl), ed. A. Adamatzky, Emergence, Complexity and Computation, Vol. 21 (Springer, 2016), pp. 39–56. Google Scholar
    • 11. E. Beggs, P. Cortez, J. F. Costa and J. V. Tucker, Classifying the computational power of stochastic physical oracles, Int. J. Unconvent. Comput. 14(1) (2018) 59–90. Web of ScienceGoogle Scholar
    • 12. E. Beggs, J. F. Costa and J. V. Tucker, Computational models of measurement and Hempel’s axiomatization, in Causality, Meaningful Complexity and Knowledge Construction, ed. A. Carsetti, Theory and Decision Library A, Vol. 46 (Springer, 2010), pp. 155–184. Google Scholar
    • 13. E. Beggs, J. F. Costa and J. V. Tucker, Physical oracles: The Turing machine and the Wheatstone bridge, Studia Logica 95(1–2) (2010) 279–300. Crossref, Web of ScienceGoogle Scholar
    • 14. E. Beggs, J. F. Costa and J. V. Tucker, Limits to measurement in experiments governed by algorithms, Math. Struct. Comput. Sci. 20(6) (2010) 1019–1050. Crossref, Web of ScienceGoogle Scholar
    • 15. E. Beggs, J. F. Costa and J. V. Tucker, The Turing machine and the uncertainty in the measurement process, in Physics and Computation, P&C 2010, ed. H. Guerra, CMATI — Centre for Applied Mathematics and Information Technology (University of Azores, 2010), pp. 62–72. Google Scholar
    • 16. E. Beggs, J. F. Costa and J. V. Tucker, The impact of models of a physical oracle on computational power, Math. Struct. Comput. Sci. 22(5) (2012) 853–879. Crossref, Web of ScienceGoogle Scholar
    • 17. E. Beggs, J. F. Costa and J. V. Tucker, Axiomatising physical experiments as oracles to algorithms, Philosoph. Trans. Roy. Soc. Series A (Math. Phys. Engin. Sci.) 370(12) (2012) 3359–3384. Google Scholar
    • 18. E. Beggs, J. F. Costa and J. V. Tucker, Three forms of physical measurement and their computability, Rev. Symbol. Logic 7(4) (2014) 618–646. Crossref, Web of ScienceGoogle Scholar
    • 19. G. A. Bekey and W. J. Karplus, Hybrid Computation (John Wiley & Sons, Inc., 1968). Google Scholar
    • 20. M. Davis, The myth of hypercomputation, in Alan Turing : The Life and Legacy of a Great Thinker, ed. C. Teuscher (Springer, 2006), pp. 195–212. Google Scholar
    • 21. M. Davis, Why there is no such discipline as hypercomputation, Appl. Math. Comput. 178(1) (2006) 4–7. Crossref, Web of ScienceGoogle Scholar
    • 22. R. Carnap, Philosophical Foundations of Physics (Basic Books, 1966). Google Scholar
    • 23. R. Geroch and J. B. Hartle, Computability and physical theories, Foundations of Physics 16(6) (1986) 533–550. Crossref, Web of ScienceGoogle Scholar
    • 24. C. G. Hempel, Fundamentals of concept formation in empirical science, Int. Encyclopedia of Unified Science 2(7) (1952). Google Scholar
    • 25. H. T. Siegelmann, Computation beyond the Turing limit, Science (1995) 545–548. Crossref, Web of ScienceGoogle Scholar
    • 26. H. T. Siegelmann, Neural Networks and Analog Computation : Beyond the Turing Limit (Birkhäuser, 1999). CrossrefGoogle Scholar
    • 27. H. T. Siegelmann and E. D. Sontag, Analog computation via neural networks, Theoret. Comput. Sci. 131(2) (1994) 331–360. Crossref, Web of ScienceGoogle Scholar
    • 28. H. T. Siegelmann and E. D. Sontag, On the computational power of neural networks, J. Comp. Syst. Sci. 50(1) (1995) 132–150. Crossref, Web of ScienceGoogle Scholar
    • 29. D. H. Krantz, P. Suppes, R. Duncan Luce and A. Tversky, Foundations of Measurement (Dover, 2009). Google Scholar
    • 30. J. von Neumann, Probabilistic logics and the synpaper of reliable organisms from unreliable components, in Automata Studies (Princeton University Press, 1956), pp. 43–98. CrossrefGoogle Scholar
    • 31. A. Steven Younger, E. Redd, H. Siegelmann and C. Bell, A physical machine based on a super-Turing computational model (2017). Google Scholar
    Remember to check out the Most Cited Articles!

    Check out these Handbooks in Computer Science