Physical oracles: the Turing machine and the Wheatstone bridge

DOI10.1007/s11225-010-9254-6zbMath1233.03018OpenAlexW2067890769MaRDI QIDQ609645

Edwin J. Beggs, J. V. Tucker, Costa, José Félix

Publication date: 1 December 2010

Published in: Studia Logica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11225-010-9254-6

zbMATH Keywords

Turing machinetheory of measurementexperimental procedurephysical oraclephysically measurable numbersWheatstone bridge

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Physics (00A79) Turing machines and related notions (03D10) Logic in the philosophy of science (03A10)

Related Items

The impact of models of a physical oracle on computational power, AN ANALOGUE-DIGITAL CHURCH-TURING THESIS, Axiomatizing physical experiments as oracles to algorithms, The ARNN model relativises \(\mathrm{P}=\mathrm{NP}\) and \(\mathrm{P}\neq \mathrm{NP}\), Computations with oracles that measure vanishing quantities, The Power of Machines That Control Experiments, A Hierarchy for $$ BPP //\log \!\star $$ B P P / / log ⋆ Based on Counting Calls to an Oracle, Limits to measurement in experiments governed by algorithms

Cites Work

• Unnamed Item
• Can Newtonian systems, bounded in space, time, mass and energy compute all functions?
• Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics
• Embedding infinitely parallel computation in Newtonian kinematics
• Axiomatizing physical experiments as oracles to algorithms
• Limits to measurement in experiments governed by algorithms
• On the Complexity of Measurement in Classical Physics
• Experimental computation of real numbers by Newtonian machines
• Computational complexity with experiments as oracles
• Newton and the science of to-day