Journal article 1414 views
Computational complexity with experiments as oracles
Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, Volume: 464, Issue: 2098, Pages: 2777 - 2801
Swansea University Authors: Edwin Beggs , John Tucker
Full text not available from this repository: check for access using links below.
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...
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 |