Computational complexity with experiments as oracles

• Type: Article in International Scientific Journal
• Date: 2008

Authors

Beggs, E (Author) Other; Costa, JF (Author) Other; Loff, B (Author) Other; Tucker, JV (Author) Other

Journal

Title: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences

Vol. 464

Pages: 2777-2801

ISSN: 1364-5021

Publisher: The Royal Society

Indexing

ISI Web of Knowledge - 22 Citations

Scopus - 25 Citations

Other information

Authenticus ID: P-003-VJA

DOI: 10.1098/rspa.2008.0085

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 25