Physical oracles: the Turing machine and the Wheatstone bridge
From MaRDI portal
Publication:609645
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
Turing machinetheory of measurementexperimental procedurephysical oraclephysically measurable numbersWheatstone bridge
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
