Computational complexity with experiments as oracles
Edwin J Beggs, José Félix Costa, Bruno Loff, John Vivian Tucker · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · 2008
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.