Axiomatizing physical experiments as oracles to algorithms

DOI10.1098/RSTA.2011.0427zbMath1334.68063OpenAlexW2157648736WikidataQ51353359 ScholiaQ51353359MaRDI QIDQ2941593

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

Publication date: 21 August 2015

Published in: Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1098/rsta.2011.0427

zbMATH Keywords

Turing machinesexperimentsmeasurementcomputabilitycomplexity classesoracles

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Physics (00A79)

Related Items (10)

A model of systems with modes and mode transitions ⋮ On Computability of Navier-Stokes’ Equation ⋮ AN ANALOGUE-DIGITAL CHURCH-TURING THESIS ⋮ The foundations of computation, physics and mentality: the Turing legacy ⋮ Physical oracles: the Turing machine and the Wheatstone bridge ⋮ 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 ⋮ Computability of the Solutions to Navier-Stokes Equations via Effective Approximation ⋮ THREE FORMS OF PHYSICAL MEASUREMENT AND THEIR COMPUTABILITY

Cites Work

• Physical oracles: the Turing machine and the Wheatstone bridge
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• The structure of logarithmic advice complexity classes
• Computable total functions on metric algebras, universal algebraic specifications and dynamical systems
• The impact of models of a physical oracle on computational power
• Limits to measurement in experiments governed by algorithms
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

This page was built for publication: Axiomatizing physical experiments as oracles to algorithms