Oracles that measure thresholds: the Turing machine and the broken balance
Edwin J Beggs, José Félix Costa, Diogo Poças, John Vivian Tucker · Journal of Logic and Computation · 2013
What can algorithms compute with the help of information provided by an oracle that is a physical system? We have developed a theory that combines Turing machines with experiments that perform physical measurements in which queries are governed by subtle timing protocols and provide the equipment with numerical data with (i) infinite precision, (ii) finite but unbounded precision or (iii) finite but fixed precision. Here, we consider the measurement of physical quantities that are thresholds, whose values are obtained by a sequence of approximate measurements that converge either from above or from below. The thresholds may be authentic physical properties or artefacts of the methods and equipment that performs the measurement. Using a canonical example of a threshold oracle, the broken beam balance for measuring mass, we develop methods to cope with thresholds and classify the computational power in polynomial time of this physical oracle using non-uniform complexity classes. Surprisingly, new complexity classes arise illuminating the influence of the operation of the equipment. All classes break the Turing Barrier.