The impact of models of a physical oracle on computational power

DOI10.1017/S0960129511000557zbMath1253.68123OpenAlexW2152574408MaRDI QIDQ2919942

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

Publication date: 23 October 2012

Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0960129511000557

zbMATH Keywords

computational powerphysical systemsoraclesphysical experimentsscatter machine experiment

Mathematics Subject Classification ID

Constructive and recursive analysis (03F60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Axiomatics, foundations (70A05)

Related Items (7)

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}\) ⋮ Machines that perform measurements ⋮ 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

Cites Work

• Unnamed Item
• Physical oracles: the Turing machine and the Wheatstone bridge
• 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
• The wave equation with computable initial data such that its unique solution is not computable
• Classical recursion theory. The theory of functions and sets of natural numbers
• On the computational power of dynamical systems and hybrid systems
• Embedding infinitely parallel computation in Newtonian kinematics
• Relativistic computers and the Turing barrier
• Limits to measurement in experiments governed by algorithms
• IS WAVE PROPAGATION COMPUTABLE OR CAN WAVE COMPUTERS BEAT THE TURING MACHINE?
• Classical physics and the Church--Turing Thesis
• On the Complexity of Measurement in Classical Physics
• Oracles and Advice as Measurements
• Computational complexity with experiments as oracles. II. Upper bounds
• Unpredictability and undecidability in dynamical systems
• Experimental computation of real numbers by Newtonian machines
• Computational complexity with experiments as oracles

This page was built for publication: The impact of models of a physical oracle on computational power