No Cover Image

Journal article 1414 views

Computational complexity with experiments as oracles

Edwin Beggs Orcid Logo, José Félix Costa, Bruno Loff, John Tucker Orcid Logo

Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, Volume: 464, Issue: 2098, Pages: 2777 - 2801

Swansea University Authors: Edwin Beggs Orcid Logo, John Tucker Orcid Logo

Full text not available from this repository: check for access using links below.

Check full text

DOI (Published version): 10.1098/rspa.2008.0085

Abstract

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

Published in: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
ISSN: 1471-2946
Published: London The Royal Society 2008
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa7205
Tags: Add Tag
No Tags, Be the first to tag this record!
Abstract: 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.
Keywords: algorithmic procedure; experimental procedure; Turing machines with oracles; analogue–digital computation; non-uniform complexity
College: Faculty of Science and Engineering
Issue: 2098
Start Page: 2777
End Page: 2801