Journal article 1226 views
Computational complexity with experiments as oracles
,
José Félix Costa,
Bruno Loff,
John Tucker
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 |