19 documents found, page 1 of 2

On discovering scientific laws

Classifying the computational power of stochastic physical oracles

Consider a computability and complexity theory in which the classical set-theoretic oracle to a Turing machine is replaced by a physical process, and oracle queries return measurements of physical behaviour. The idea of such physical oracles is relevant to many disparate situations, but research has focussed on physical oracles that were classic deterministic experiments which measure physical quantities. In th...

Solving Smullyan puzzles with formal systems

The unity of science as seen through the universal computer

Computations with oracles that measure vanishing quantities

A hierarchy for BPP//log* based on counting calls to an oracle

Algorithms whose computations involve making physical measurements can be modelled by Turing machines with oracles that are physical systems and oracle queries that obtain data from observation and measurement. The computational power of many of these physical oracles has been established using non-uniform complexity classes; in particular, for large classes of deterministic physical oracles, with fixed error m...

The Physics of the Halting Problem

An Analogue-digital Model of Computation: Turing Machines with Physical Oracles

We introduce an abstract analogue-digital model of computation that couples Turing machines to oracles that are physical processes. Since any oracle has the potential to boost the computational power of a Turing machine, the effect on the power of the Turing machine of adding a physical process raises interesting questions. Do physical processes add significantly to the power of Turing machines; can they break ...

Three forms of physical measurement and their computability

An analog-digital Church-Turing thesis