Physical Oracles: The Turing Machine and the Wheatstone Bridge
作者： Edwin J. Beggs , José Félix Costa , John V. Tucker
DOI: 10.1007/S11225-010-9254-6
关键词:
摘要: Earlier, we have studied computations possible by physical systems and algorithms combined with systems. In particular, analysed the idea of using an experiment as oracle to abstract computational device, such Turing machine. The theory composite machines this kind can be used understand (a) a machine receiving extra power from process, or (b) experimenter modelled performing test known T. Our earlier work was based upon experiments in Newtonian mechanics. Here extend scope experimental oracles beyond mechanics electrical theory. First, specify that measures resistance Wheatstone bridge start classify non-uniform complexity classes. Secondly, show modelling procedure algorithmically imposes limit on our ability measure bridge. The connection between algorithm is mediated protocol controlling each query, especially time taken experimenter. studies find exponential protocol; formulate general conjecture. Our proposes measurability Physics subject laws which are co-lateral effects limits computability complexity.
swan.ac.uk
springer.com
core.ac.uk
philpapers.org
jstor.org 
sci-hub.se 参考文章(15)
Gaston Bachelard, The new scientific spirit ,(1984)
Carl Gustav Hempel, Fundamentals of Concept Formation in Empirical Science ,(1952)
Martin Ziegler, Physically-relativized Church-Turing Hypotheses: Physical foundations of computing and complexity theory of computational physics Applied Mathematics and Computation. ,vol. 215, pp. 1431- 1447 ,(2009) , 10.1016/J.AMC.2009.04.062
John Tucker, EJ Beggs, JF Costa, B Loff, JV Tucker, On the complexity of measurement in classical physics theory and applications of models of computation. pp. 20- 30 ,(2008) , 10.1007/978-3-540-79228-4_2
EDWIN J. BEGGS, JOSÉ FÉLIX COSTA, JOHN V. TUCKER, Limits to measurement in experiments governed by algorithms Mathematical Structures in Computer Science. ,vol. 20, pp. 1019- 1050 ,(2010) , 10.1017/S0960129510000356
T. Rado, On Non-Computable Functions Bell System Technical Journal. ,vol. 41, pp. 877- 884 ,(1962) , 10.1002/J.1538-7305.1962.TB00480.X
Edwin J. Beggs, John V. Tucker, Can Newtonian systems, bounded in space, time, mass and energy compute all functions? Theoretical Computer Science. ,vol. 371, pp. 4- 19 ,(2007) , 10.1016/J.TCS.2006.10.010
Robert Geroch, James B. Hartle, Computability and physical theories Foundations of Physics. ,vol. 16, pp. 533- 550 ,(1986) , 10.1007/BF01886519
E.J Beggs, J.V Tucker, Experimental computation of real numbers by Newtonian machines Proceedings of The Royal Society A: Mathematical, Physical and Engineering Sciences. ,vol. 463, pp. 1541- 1561 ,(2007) , 10.1098/RSPA.2007.1835
Edwin Beggs, José Félix Costa, John V. Tucker, Computational Models of Measurement and Hempel’s Axiomatization Springer, Dordrecht. pp. 155- 183 ,(2010) , 10.1007/978-90-481-3529-5_9