Computational complexity with experiments as oracles

We discuss combining physical experiments with machine computations and introduce a form of analogue-digital (AD) Turing machine. We examine in detail a case study where an experimental procedure based on Newtonian kinematics is combined with a class of Turing machines. Three forms of AD machine are...

Full description

Saved in:
Bibliographic Details
Published in:Proceedings of the Royal Society. A, Mathematical, physical, and engineering sciences Mathematical, physical, and engineering sciences, 2008-10, Vol.464 (2098), p.2777-2801
Main Authors: Beggs, Edwin, Costa, José Félix, Loff, Bruno, Tucker, John V
Format: Article
Language:English
Subjects:
Algorithmic Procedure
Algorithms
Analogue-Digital Computation
Cannons
Determinism
Dyadics
Experimental Procedure
Machinery
Non-Uniform Complexity
Oracles
Physical theory
Polynomials
Turing machines
Turing Machines With Oracles
Vertices
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We discuss combining physical experiments with machine computations and introduce a form of analogue-digital (AD) Turing machine. We examine in detail a case study where an experimental procedure based on Newtonian kinematics is combined with a class of Turing machines. Three forms of AD machine are studied, in which physical parameters can be set exactly and approximately. Using non-uniform complexity theory, and some probability, we prove theorems that show that these machines can compute more than classical Turing machines.
ISSN:1364-5021
1471-2946
DOI:10.1098/rspa.2008.0085