## Abstract

We developed earlier a theory of combining algorithms with physical systems, on the basis of using physical experiments as oracles to algorithms. Although our concepts and methods are general, each physical oracle requires its own analysis, on the basis of some fragment of physical theory that specifies the equipment and its behaviour. For specific examples of physical systems (mechanical, optical, electrical), the computational power has been characterized using non-uniform complexity classes. The powers of the known examples vary according to assumptions on precision and timing but seem to lead to the same complexity classes, namely and . In this study, we develop sets of axioms for the interface between physical equipment and algorithms that allow us to prove general characterizations, in terms of and , for large classes of physical oracles, in a uniform way. Sufficient conditions on physical equipment are given that ensure a physical system satisfies the axioms.

## 1. Introduction

### (a) Oracles

In computability theory, the basic operations of algorithmic models—Turing machines, register machines, recursion schemes, etc.—may be extended with sets, or functions, called ‘oracles’. For example, in Post's standard abstraction of Turing's original conception [1], any set *S* can be used as an oracle in an algorithm as follows: from time to time, in the course of a computation, an algorithm produces a datum *x*, asks ‘Is *x*∈*S*?’ and receives an exact answer ‘yes’ or ‘no’ in a single step of the computation.^{1}

Adding an oracle increases the computational power of an algorithm. The idea of coupling an oracle to an algorithm is surprisingly subtle and mathematically fruitful. The idea of Turing reduction led Emil Post to a theory of relative computation and the classification of degrees of algorithmic unsolvability.^{2} The theory of Turing degrees of unsolvability, such as those below 0′,0′′,…,0^{ω}, map much of what is non-computable and have highly important applications to decision problems in logic, mathematics and programming.^{3}

The notion of oracle has been just as influential in complexity theory. The notions of reduction and degrees led to the use of oracles to create the *polynomial time hierarchy* in 1972.^{4} Early on, in 1975, came the Baker–Gill–Solovay theorems [9] that showed that the *P*=*NP* question relativizes both positively and negatively and therefore that any proof technique that is unaffected by the addition of an oracle will fail to answer the *P*=*NP* question.^{5}

Perhaps what is not clear from the mathematical theory is that adding an oracle to an algorithm is a computational idea that occurs *naturally*. One simple, yet seemingly familiar example is introducing randomness by tossing a coin at various stages in a computation. Properly described, this is using an experiment as an oracle. In the theory of probabilistic Turing machines and complexity classes, such as *BPP*, randomness is defined by a mathematical oracle (cf. §7.4 of Balcázar *et al.* [10]).

### (b) Physical oracles

Imagine a computation that *from time to time* requires us to consult some external physical device, say, to read some data, make some measurement, choose randomly, guess information, etc. We can view this external interaction as follows: the algorithm formulates a request, query or command, presents it to the device, waits some time for the device to answer and resumes the computation. The device is likely to function within error bounds; so precision is a factor in computation.

In Beggs *et al*. [11], we introduced the idea of taking a physical experiment that measures a physical quantity as a new form of oracle to a Turing machine. We focused on modelling the structure and operation of these hybrid computational models and, in particular, the question:

*What can be computed by algorithms boosted by oracles that are physical systems?*

In Beggs *et al*. [11], we chose a particular mechanical experiment first studied in Beggs & Tucker [12], the scatter machine experiment (SME), studied the hybrid systems made by combining deterministic Turing machines with the SME and answered the question using non-uniform complexity theory [11,13]. In subsequent work, we studied several other examples of experiments as oracles, including the collider machine experiment (CME) [14] and the Wheatstone bridge [15].^{6}

The computational power of the physical oracles we have studied varies according to assumptions on precision and timing. Furthermore, we have constructed different models of a single physical experiment (actually the original SME) and shown that they can have different computational attributes, such as runtimes, and different computational powers [18]. The questions arise:

*How varied are the attributes, such as runtimes, of physical experiments?*

*How varied are the computational powers of algorithms when boosted by physical oracles?*

Given the potentially infinite diversity of physical experiments—and the variation in modelling each one of those experiments—one might expect answers to be infinitely diverse. However, our case studies of different mechanical, electrical and optical experiments as oracles lead us to similar runtimes and to similar complexity classes, especially and , depending on assumptions about the precision of equipment. Indeed, in Beggs *et al*. [14], we made a conjecture about the runtimes of experiments, namely: *normally, runtime is exponential in the accuracy of measurement*. To begin to classify experimentation for computational purposes, taxonomies for equipment and procedures are needed.

In this study, we address the classification and ‘stability’ of models of computation with physical oracles. We develop three sets of axioms for experimental measurement that allow us (i) to explore variations in equipment and behaviour and their effects on the quantity measured and (ii) to prove general characterization theorems of the power of experiments as oracles. The axioms specify the *interface* between physical equipment and algorithms. The theorems establish the scope and limits of large classes of physical oracles, in a uniform way, in terms of and . We also give sufficient conditions on physical equipment that ensure that a physical system satisfies the axioms (theorem 3.2).

### (c) Results

The physical oracles are experiments that measure physical quantities represented by real numbers *x*∈(0,1). The axioms define those features of the experiment and its behaviour that the algorithms may use and depend upon. The axioms for the interface focus on two properties: the time taken to obtain a measurement and the precision of the measurement.

First, we consider physical experiments with deterministic behaviour.

Let be a class of functions of the form that we will use to bound the runtime of the experiment as a function of its precision. We give axioms for any physical experiment that measures *x*∈(0,1), which defines a class of physical oracles. We have found the most important class of bounds to be that of all exponentials of linear functions,
(i.e. *g*(*n*)∈2^{Θ(n)}). Hence, the most important class of oracles is *E*(ExpLin).

The first main theorem is this (theorem 4.7).

### Theorem A

*Given a decision problem A in* *, there is a real value x∈(0,1), so that any physical oracle in class E(ExpLin) measuring x can be used to decide A in polynomial time. Conversely, any decision problem A that can be solved in polynomial time by a Turing machine with an oracle in class E(ExpLin) is also in* .

Next, we consider non-deterministic behaviour of the physical experiment, which can arise for all sorts of reasons, most simply precision. Our axioms involve probability distributions and lead to a new class Iid(*δ*) of physical oracles, where Iid stands for *independent identically distributed*. The second main theorem is this (theorem 5.3).

### Theorem B

*Given a decision problem A in* , *there is a real value x∈(0,1) so that any oracle in class Iid(δ) measuring x∈(δ,1−δ) can be used by a Turing machine to decide A in polynomial time. Conversely, any decision problem that can be solved in polynomial time by a Turing machine with an oracle in class* Iid*(δ) is in* *.*

The structure of the paper is this. In §2, we describe carefully the characteristics of experiments and our line of thought summarized earlier. In §3, we give the first set of axioms and prove a sufficiency condition for experiments to satisfy the axioms. In §4, we prove the lower bound for the first theorem and on altering an axiom on repeatability we prove the upper bound completing the proof of theorem A. In §5, we give a much simplified set of axioms with a probability distribution for the repeatability and prove theorem B. In §6, we reflect on the results.

This study is a part of our programme on the physical foundations of computation; primarily, it concerns [11,13–15,18]. Some knowledge of non-uniform complexity classes is needed.

## 2. Experiments and interfaces

### (a) Algorithms and experiments

The basic structure of an algorithm combined with an experiment as oracle is depicted in figure 1. The experiment consists of various components:
The equipment is modelled, based on some fragment of the physical theory *T*. The algorithm is modelled by a Turing machine, which is suited to complexity considerations. In this context, here is a working definition of physical oracles.

### Definition 2.1

A physical oracle is a physical device or system with an interface that accepts queries and returns an answer. For an oracle to a Turing machine, the query would be written on a query tape. A time limit may be assigned to such a query, after which the result ‘time out’ is returned if no other result is obtained in this time.

Now, in developing a theory of algorithms and experiments, we note two methodological principles. The equipment involved in making any measurement is potentially diverse. It is made by different manufacturers and according to somewhat abstract specifications of its type and characteristics.

*Variation of equipment*. Given any experiment to measure a quantity, its experimental procedure can be applied to a variety of forms of physical equipment to obtain the same measurements with few possible changes to performance.

This complementary idea is very important in theoretical practice:

*Invariance of models of equipment*. Given any experiment, there is a portfolio of theoretical models for the equipment and its behaviour, employing different physical assumptions, that can be used with the experimental procedure to reason about the experiment.

Indeed, we do not need to know the complete description of the equipment but only what properties are needed to reason correctly about the experimental procedure. We need a specification of the equipment that characterizes the interface.

A strong demonstration of this principle can be found in the different models of the wedge in the SME; in particular, in Beggs *et al*. [18], a simple experimental procedure is applied to two distinct models of the simple wedge having markedly different computational properties.

### (b) Experiments that measure: six characteristics

Here are the properties that seem to be essential characteristics of the experiments that we have used as oracles so far.

—

*Real values.*A physical parameter represented by a real number is being measured—position, inertial mass, location, resistance, mass of an electric particle, temperature, optical angles, etc.—

*Queries.*Each query expresses a rational, even dyadic, number that is a possible approximate value of the parameter being measured. This test value is then compared with the actual ‘physical’ value in an experiment. The experiment ultimately implements a decision procedure, such as < or >, on physical parameters, possibly leaving equality undecided.—

*Finite output.*Only qualitative output is allowed in a single experiment:*right*or*left*,*yes*or*no*,*north*or*south*, etc.; or a trivalent output, adding the response*time out*.—

*Protocol timer.*The protocol between the Turing machine and the experimental apparatus measures the time needed for the experiment to deliver an answer in reasonable cases. It does not guarantee that the experiment will return an answer within the protocol time, and in that case*time out*is returned.—

*Sufficiency of the protocol.*Enough experiments are completed within the protocol timer to give results that can be used to give more physical information.—

*Repeatability.*The extent to which identical queries give the same results.

We must also address the problem of the precision of the experiment. For simplicity of explanation, we localize the imprecision in the experiment. Suppose that an experiment to measure a mass *x* compares it with a test mass *y* on a balance, and outputs *x*>*y* or *x*<*y*, the value *x*=*y* leading to the experiment running out of time. The value of *y* is specified on the query tape, the experiment is performed and the result returned to the Turing machine. However, we need to consider the *error in making* a test mass from the instructions on the query tape, and look at the three most obvious possibilities.

—

*No error.*The test value*y*is exactly the value given on the query tape. More generally, the experiment is carried out exactly as specified on the query tape.—

*Arbitrary precision.*The value on the query tape comes with a specified error, and the test value*y*(or the experiment in general) is set up to within that error margin.—

*Fixed precision.*There is an error margin that it is impossible to improve on—no matter how hard we try,*y*cannot be prepared more accurately than in a certain interval around the value specified on the query tape.

The no error case is an interesting idealization, but is of little practical value. However, the arbitrary precision case has, in many experiments, identical computational power. To practically implement arbitrary precision would, at the very least, take more time for a smaller error margin, but accounting for this additional time is part of the function of the protocol.

The fixed precision case seems doomed from the start—surely there is only a finite amount of information that could be extracted from such an experiment and so could be appended as part of the program. However, we now turn to probability: we repeat the experiment many times and extract statistical data. To do this requires (more or less) assumptions about independence and identical distribution of repeats of the experiment. If this sounds unlikely in practice, remember that we, according to current understanding of quantum theory, do have a source of ‘real randomness’ that we can use to ‘kick’ the apparatus between experiments. Indeed, in practice, the quantum nature of the world we live in is quite likely to randomize the experimental setup to some extent, whether we want this or not.

It is a striking fact that in many experiments, this fixed precision statistical approach can have computational power identical to that of the no error case. Probabilistic Turing machines clocked in polynomial time give *BPP* as a probabilistic complexity class. If we add a physical oracle of type *E*(ExpLin), we then get . But, by theorem B, this is the same as we get from the oracle Iid(*δ*).

### (c) The interface and its protocol

In contrast to the complexity of the equipment inside the physical oracle, the *interface protocol*, which is all the Turing machine sees, could hardly be simpler. There is a query tape, and when the Turing machine enters the query state, it rests while the experiment proceeds. When the result is returned, the Turing machine resumes its calculation. In fact, there are only three differences between the protocols for standard oracles and physical oracles as far as the Turing machine is concerned.

—

*Runtimes*. The time taken by the physical oracle to reply is rarely one or a constant number of cycles; it varies. It will be convenient for us to assume that the time taken is a function of the length of the query. Thus, a polynomial function of the length gives a*polynomial protocol*, and an exponential function of the length gives an*exponential protocol*. For simplicity, the result is returned only at the end of the time limit given by the protocol, even if the experiment was finished much more quickly.—

*Timeouts*. To keep things simple, we consider only two outcomes for an experiment:*yes*and*no*. However, an experiment takes time to perform, which may depend on the detail of the result being sought or the experiment may not be completed in any finite time (e.g. comparing two masses on a balance when the masses are actually equal). To stop the Turing machine waiting indefinitely for a result that may never come, we impose time limits on the experiments for which we need another outcome*time out*for an experiment that was terminated before an answer was obtained.—

*Non-determinism*. In the probabilistic case, identical queries may produce different results. This is not new, as coin-tossing oracles have been used for a long time.

### (d) Timing

As experimental scientists will only too readily testify, experiments and observations are prone to errors and entail costs. We focus on only one of these costs, the time taken. In previous papers analysing physical experiments, we were led to a conjecture relating the accuracy of a measurement to the time taken to perform the measurement. These experiments had the form of comparing a test value *y* with the real world value *x* of a physical quantity, this comparison taking experimental time
2.1
Here, *n*,*q*≥1 and *A*,*B*>0 are constants determined by the experiment. Now, the two inequalities in (2.1) have a different status. They were arrived at by considering models of experiments that omitted many unrealistic features (such as infinitely sharp points), but were still idealized. The lower bound for the experimental time can be considered much more definite—it is extremely difficult to see how to get around such a bound, even allowing for idealized thought experiments. The upper bound is, in reality as opposed to thought experiments, much more questionable, but is a reasonable working hypothesis.

Some experiments can take a long time or even fail to return a result. The time that the machine is allowed to wait for the results of the experimental procedure should not be unlimited. We wish to place bounds on execution times of Turing machines. To control the physical oracle, the protocol will be equipped with a special *protocol clock*, based on a time constructible function. A function is said to be time constructible if there exists a Turing machine that, for all inputs of size *n*, halts exactly in *T*(*n*) steps. Let be a Turing machine, equipped with oracle tape and oracle . Let be the Turing machine that witnesses the runtime of computations as a function of the size of the input *w*, i.e. a system clock, and let be the Turing machine that witnesses the protocol time as a function of the size of the query *z*, i.e. a query timer. A Turing machine, with an internal system clock and a timing clock for running the experiment that controls the apparatus and returns results may then be specified. Assuming that all the transitions of the composite Turing machine can be made to happen in the physical time unit, we have the connection between machine time and physical time.

However, we should be aware that such a composite Turing machine does not measure time! Indeed, an experiment to measure time with *n* bits of precision (e.g. the period of an orbital motion) takes time at least exponential on *n*, in agreement with our theory. The former machine time is a *more or less time*, an order of magnitude of time. And, because our experiments can be performed in time of exponential order, some exponential of the class will do!

Our experiments are fundamental measurements, centred only on observable events occurring in the physical apparatus; they do not depend on precise measurements of time, nor are they a result of operations between values of measurables. In fundamental measurement, the value is not obtained as a result of (say, arithmetical) operations on other measurements (e.g. using time to get more accuracy). These measurements are said to be derived because their procedures rest on *a priori* theories relating the measurables.

The reader may wonder from where formula (2.1) comes. To provide a general idea on how time varies with the required precision, just consider a balance with two pans for the purpose of measuring mass, and a toolbox of standards *m*_{2} designed to measure mass *m*_{1} with some precision. The relevant events referred to earlier are, in this case, ‘right/left pan up/down’. To detect an event, the experimenter has to wait some time, for the acceleration of a pan is proportional to |*m*_{1}−*m*_{2}| and the time needed to detect a downward movement of, let us say, 1 mm is proportional to 1/|*m*_{1}−*m*_{2}|^{1/2}. Thus, if the difference of the masses in binary is 2^{−an}, for some constant *a*, for a precision of *n* bits, the time elapsed is proportional to 2^{bn}, for some constant *b*, that is exponential on the number of bits of precision. This calculation gives a lower bound on the time. An upper bound can then be fixed for values of the mass that, in this paper, codes for advice functions. Other experiments, being more or less sophisticated, reveal the same timing law (2.1). Thus, it became a conjecture that we discuss in detail in Beggs *et al.* [19].

## 3. Implementing the axioms for

Here, we take the description in §2*b*, and interpret it in detail for a particular case, called . Here, is a class of functions, where each is a function .

### Definition 3.1

The following axioms define the class of *physical oracles* .

—

*Real values.*The experiment is designed to find a physical parameter*x*∈(0,1).—

*Queries.*Each query string is interpreted as a binary string of 0s and 1s,*y*_{1}*y*_{2}⋯*y*_{k}, giving a dyadic rational*y*=0⋅*y*_{1}*y*_{2}⋯*y*_{k}.—

*Finite output.*The result is either*y*<*x*,*y*>*x*(correctly assigned) or*time out*.—

*Protocol timer.*There is a so that the time taken for any query of length*k*is bounded by*g*(*k*).—

*Sufficiency of the protocol.*If |*x*−*y*|>2^{−k}for the dyadic rational*y*=0⋅*y*_{1}*y*_{2}…*y*_{k}, then the result is not*time out*.

These axioms for are sufficient to prove various complexity results for a Turing machine using a physical oracle from , and we shall do this in §4. But are there really physical experiments implementing this specification? The answer is yes: first, we shall describe the common properties of the experiments that show that they implement the axioms, and then give a list of some of the experiments.

The experiments are designed to measure a physical parameter *x*, which, for convenience, we shall take to be in the interval (0,1). A test value *y* is compared with the value of *x* in the experiment, and we get the results *y*<*x* or *y*>*x*. The time taken for this experiment is just that given in (2.1), which we repeat:
3.1
for some rationals *A*,*B*>0 and integers *n*,*q*≥1. Now one can see why there is no *x*=*y* result, as if we put *x*=*y* in the formula for the time, the result is infinite.

But now we must consider the whole system behind the physical oracle. The experimenters receive a message from the protocol, and must set up the experiment, perform the experiment and report the answer back to the protocol. The experimenters have to set up the test value *y*=0⋅*y*_{1}*y*_{2}⋯*y*_{k} for the experiment, and this will take time. It may also entail error: that is, the actual value of the test variable in the experiment *y*′ may not be exactly the requested value *y*=0⋅*y*_{1}*y*_{2}⋯*y*_{k}. We shall suppose that we either have no error, or arbitrarily small error, i.e. that the experiment can be set up to any desired finite accuracy.

But can the oracle return the wrong answer: because of the error in setting up the test value, the reported answer might be *y*>*x*, whereas in reality *y*<*x*? We can eliminate this possibility by making the experimental time work in our favour, by ensuring that all experiments that might report incorrect results instead report *time out*. If we have such a possible incorrectness, then *x* must lie between *y* and *y*′, so
Now, by (3.1),
If the experimenters impose a time limit on the experiment, then an incorrect case must *time out* if
3.2

Now we address the sufficiency of the protocol. If |*x*−*y*|>2^{−k}, and supposing that |*y*−*y*′|≤2^{−k−1}, then we have |*x*−*y*|>2^{−k−1}. Now, by (3.1),
Thus, the experiment cannot *time out* if
3.3
We set the time limit on the experiment to be 2^{n(k+1)}*B*, and in that case, we require |*y*−*y*′|≤2^{−k−1} and (3.2) for correctness, and that now gives

It will be convenient (by taking more accuracy than we actually need) to give a fixed integer *r*≥1 (determined by *A*,*B*,*n*,*q*) so that 2^{−r(k+1)} is less than the above minimum. Now, if we specify accuracy |*y*−*y*′|<2^{−r(k+1)}, then we get correctness of the answer and sufficiency for the experiment.

But how long does this whole process take? We have a time limit for the experiment, but how long does it take to set up the experiment? We assume that the time taken to set up the experiment with the actual test value *y*′ to within an error |*y*−*y*′|<2^{−s} of the query value *y*=0⋅*y*_{1}*y*_{2}⋯*y*_{k} is
3.4
for some rational *E*>0 and integer *p*≥1. Thus, we can set up the experiment for our specified accuracy |*y*−*y*′|<2^{−r(k+1)} in time
The total time for the whole procedure, the value that we can give to the protocol timer, is
3.5
Alternatively, we can take a single exponential 2^{u(k+1)} bounding this whole expression. We have then proved the following theorem.

### Theorem 3.2 (interface verification test 1)

*Suppose we are given an experimental procedure to measure x∈(0,1) in the following manner. Suppose there are rationals A,B,E>0 and integers n,q,p≥1 so that*

—

*Given y=0⋅y*_{1}*y*_{2}*⋯y*_{k}*we can set up the experiment with a test value**with |y−y′|<2*^{−s}*in time**.*—

*We can run the experiment to determine whether x<y′ or x>y′ in time*

*Then, there is a physical oracle to a Turing machine using the experiment that obeys the axioms for E*(ExpLin).

Here is a list of some published experiments that obey the experimental time constraint in theorem 3.2.

—

*The collider machine.*This is designed to measure the inertial mass*x*of a particle in classical mechanics. A particle of mass*y*is prepared and collided with the original particle [14].—

*The Wheatstone bridge.*This is designed to measure an electrical resistance*x*. A resistance*y*is prepared and compared with the original resistance [15].—

*The general scatter machine.*This is designed to measure a position*x*on an interval, by comparing it with a dyadic position*y*[18].

## 4. The computational power of *E*(ExpLin)

**(ExpLin)**

*E*### (a) The non-uniform complexity class *P*/log★

These complexity classes are based on *advice functions*. We assume that there is a single algorithm for inputs of every size, which is aided by certain information, called *advice*, which may vary for inputs of different sizes. The advice is obtained via a function . For each input *w*, it is combined 〈*w*,*f*(|*w*|)〉 by means of a pairing function 〈⋅,⋅〉:*Σ**×*Σ**→*Σ**. This function and its inverses (⋅)_{1} and (⋅)_{2} are computable in linear time.^{7}

### Definition 4.1

Let be a class of sets and a class of functions. The advice class is the class of sets *A* for which there exists and some such that, for every *w*∈*Σ**, *w*∈*A* if and only if 〈*w*,*f*(|*w*|)〉∈*B*.

The set is called the *advice class* and *f* is called the *advice function*. Examples for are *P* and *BPP*.

We will consider two instances for the class is the class of functions with polynomial size values, i.e. *poly* is the class of functions such that, for some polynomial *p*, |*f*(*n*)|∈*O*(*p*(*n*)); is the class of functions such that . We will also need prefix non-uniform complexity classes. For these classes, we may use only prefix functions, i.e. functions *f* such that *f*(*n*) is always a prefix of *f*(*n*+1). The idea behind prefix non-uniform complexity classes is that the advice given for inputs of size *n* must also be useful to decide smaller inputs.

### Definition 4.2

Let be a class of sets and a class of functions. The prefix advice class is the class of sets *A* for which there exists and some prefix function such that, for all words *w*∈*Σ** of length less than or equal to *n*, *w*∈*A* if and only if 〈*w*,*f*(*n*)〉∈*B*.

As an example of definition 4.2, we have . It is important to notice that the usual non-uniform complexity classes contain undecidable sets, e.g. *P*/*poly* contains the sparse halting set. Classes with larger advice usually become uninteresting: exponential advice, for instance, allows a Turing machine to decide any set in linear time. The non-computability of the non-uniform complexity classes results exclusively from the non-computability of the advice functions.

### (b) Coding a log★ advice function as a real

Suppose that the real number 1>*x*>0 has a binary expansion consisting only of the triples 100, 010 or 001. For example, we could have (separating the triples for clarity)
Such numbers occur in a Cantor subset of [0,1], and have the useful property that for every such *x*,
4.1
Now we suppose that we are given an advice function , where *Σ* is a finite alphabet. We code every letter in *Σ* as a binary number (for example, Unicode or ASCII). Then, replace every 0 in its binary form by 100 and every 1 by 010. Thus, a letter in *Σ* might have binary representation 00101, and on replacement by triples (separating triples for clarity) we would have
If we perform this binary and then triple replacement letter by letter, we get a function *c*:*Σ**→{100,010}*, where the length of *c*(*v*) is bounded by a linear function of the length of *v*∈*Σ**.

Now suppose that is such that each *f*(*n*) is a prefix of *f*(*n*+1), i.e. *f*(*n*+1)=*f*(*n*)*s*, for some *s*∈*Σ**. We code *f* as a real number *x*(*f*) in the Cantor set described earlier. We recursively define *x*(*f*) as the limit of *x*(*f*)(*n*), using the coding *c*:*Σ**→{100,010}* by starting with
and using the following cases, where *f*(*n*+1)=*f*(*n*)*s*,
The net effect is to add a 001 at the end of the codes for *n*=1,2,4,8,… We can now prove the following result.

### Proposition 4.3

*Given an advice function* *f* *for a decision process in* , *there is a real number* 1>*x*>0 *obeying* (4.1) *so that, to reconstruct advice sufficient to decide a word* *w*, *it is sufficient to read the first logarithmically (in the length of* *w*) *many binary digits of* *x*.

### Proof.

Construct the real *x*(*f*) as mentioned earlier, and note that it obeys (4.1) by construction. Now, for the word *w*, take with 2^{m−1}<|*w*|≤2^{m}. We read the binary expansion until we have counted a total of *m*+1 001 triples. Now the extra 001s are deleted, and we can reconstruct *f*(2^{m}), which can be used as advice for *w*. But how many binary digits from *x*(*f*) must we read? We start with (for some constants *K* and *L*) from the definition of log length. This means that we must read at most *Lm*+*K*+3*m* digits when we add in the 001 separators, so the number of digits is logarithmic in |*w*|.

### (c) Implementing binary search using an *E*(ExpLin) oracle

Suppose that we have a decision problem in , with advice function *f*. By proposition 4.3, there is an 1>*x*>0 so that to decide a word *w* we need to read at most binary places of *x*. Here, *K*,*L*>0 are constants and |*w*| is the length of *w*. We are given an oracle *O* in the class *E*(ExpLin) for the real value *x*∈(0,1), using a protocol timer *g*∈ExpLin.

The Turing machine will begin its operation by running a sub-program to find the first binary places of *x* by binary search. Then this is used as advice to run the program to decide the input word *w*, in polynomial time in |*w*|. All we have to do is to show that we can find the first binary places of *x* in polynomial time, using calls of the given oracle *O*. We suppose that for *O*'s protocol timer *g*, *g*(*n*)≤*A*2^{Bn}.

The principle of binary search is simple: begin with *y*_{0}=0 and *y*_{1}=1. Call the oracle *O* with query to see whether (in which case take the interval ) or (in which case take the interval ). Now continue bisecting the intervals until we find *k* with *x*∈[*k*/2^{m},(*k*+1)/2^{m}]. The complications with our oracle *O* are that it may report a *time out* result, and that we have to estimate how much time it takes to answer the queries.

In principle, we need *O* to answer *m* queries, of potential length 1 to *m*. For example, suppose at the third stage of the bisection we need to find if *x*>0⋅010 or *x*<0⋅010. If we ask this directly, we might get a *time out* result. To avoid this, add five zeros, and make the query *y*=0⋅01000000, i.e. *y*_{1}⋯*y*_{8}=01000000. This query takes not more than time *A*2^{8B} to answer. By the *sufficiency of the protocol* property, if |*x*−*y*|>1/2^{8}, we get the correct answer, either *x*>0⋅010 or *x*<0⋅010. But (4.1) states that |*x*−*y*|>1/2^{8}; so we do get the correct answer.

To get the required advice by binary search to find the first *m* digits, it suffices to have *m* queries, each taking not more than time *A*2^{(m+5)B}. This proves the following proposition.

### Proposition 4.4 (lower bound)

*Given a decision problem in* , *there is an* *x*∈(0,1) *so that any oracle in class* *E*(ExpLin) *can be used to solve the problem in polynomial time*.

### (d) An upper bound on the computational power of *E*(ExpLin)

We have seen that every problem in can be solved by some oracle in the class *E*(ExpLin) in polynomial time. But is every decision problem solved by a Turing machine augmented by an oracle in class *E*(ExpLin) necessarily in ? The answer is no, as is discussed in some detail at the beginning of §5, the basic reason being the lack of repeatability, and that this could be used to input more information than expected to the Turing machine. To get round this problem, we consider a second class of oracles.

### Definition 4.5

The following axioms define the class of physical oracles .

—

*Real values.*The experiment is designed to find a physical parameter*x*∈(0,1).—

*Queries.*Each query string is interpreted as a binary string of 0s and 1s,*y*_{1}*y*_{2}⋯*y*_{k}, giving a dyadic rational*y*=0⋅*y*_{1}*y*_{2}⋯*y*_{k}.—

*Finite output.*The result is either*y*<*x*,*y*>*x*(correctly assigned) or*time out*.—

*Protocol timer.*There is a so that the time taken for any query of length*k*is bounded by*g*(*k*).—

*Sufficiency of the protocol.*If |*x*−*y*|>2^{−k}for the dyadic rational*y*=0⋅*y*_{1}*y*_{2}⋯*y*_{k}, then the result is not*time out*.—

*Repeatability.*If the same query is used on the oracle, the same output will be obtained.

We now have a slightly modified version of theorem 3.2, to show that some experiments can give rise to oracles of this class. The proof is just adding repeatability to the list of axioms.

### Theorem 4.6 (interface verification test 2)

*Suppose we are given an experimental procedure to measure x∈(0,1) in the following manner. Suppose there are rationals A,B,E>0 and integers n,q,p≥1 so that*

—

*Given y=0⋅y*_{1}*y*_{2}*⋯y*_{k}*we can set up the experiment with a test value**with |y−y′|<2*^{−s}*in time**. Further, every run of the experiment for a given y gives an identical**.*—

*We can run the experiment to determine whether x<y′ or x>y′ in time*

*Then, there is a physical oracle using the experiment, that obeys the axioms for E*_{det}(ExpLin).

We can now find an upper bound to the computational power of a Turing machine with an oracle of class *E*_{det}(ExpLin). As now we know that the result of a given query is always the same, all we have to do is to make an advice function that encodes the results of all possible queries up to a given query length, and check the length of the advice function. This is a consequence of the *sufficiency of the protocol* and the *correctness* of the answers *x*<*y* and *x*>*y*, which give, for a query of length *n*,
4.2
The key is in looking at the results on successive *y*=*k*/2^{n} for integer *k* and fixed *n*. For convenience, we extend this from *y*∈(0,1) to all integer *k* by filling in the obvious answers. Now we get results *y*<*x*, *time out* and *y*>*x*, which we shorten to <, 0 and >, respectively. Now for sufficiently small *k*, by (4.2), we get the result <, and sufficiently large *k*, we have >. From (4.2), the transition zone cannot be longer than three units long, and so can only have a few forms, which we list:
4.3
Here, the * represent some choices of the three symbols (with the first not being a <, and the last not being a >). To each *n*, we give a finite string (length independent of *n*) to describe which pattern the transition zone has.

Now, for our given *n*, we would like to describe where the transition zone starts (say the *k* giving the < after the dots). By (4.2), this value of *k*, which we call *k*_{n}, obeys the inequality
4.4
The problem is that an absolute description of *k*_{n} cannot be performed in a data string that has length independent of *n*. However, from (4.4), we can deduce that 2*k*_{n}−*k*_{n+1} is an integer between −7 and 5, so we can simply record this number instead of *k*_{n}.

Now, beginning from the *n*=1 case, we form a word *u*(*n*) recursively. The word *u*(1) describes the results from all queries of length one. Recursively, we form *u*(*n*+1) by appending to *u*(*n*) a word describing the form of the transition for *n*+1 and the integer 2*k*_{n}−*k*_{n+1}. As this is a bounded amount of data (independently of *n*), the length of *u*(*n*) is bounded by a constant times *n*, and it contains enough information to reconstruct the result of any query of *length*≤*n*.

Now consider a program using an oracle in the class *E*_{det}(ExpLin) to solve a decision problem in polynomial time in the length of the input. So for input *w*, the time will be ≤*p*(|*w*|), so we can perform only queries of length bounded by a linear function in . By the previous paragraph, we can use *u*(*n*) as an advice function, where *n* is bounded by the linear function in . We have now proved the second half of the following result, the first half being a corollary of proposition 4.4.

### Theorem 4.7

*Given a word decision problem in* *, there is an 1>x>0 so that any oracle in class E*_{det}(ExpLin) *for real value x∈(0,1) can be used to solve the problem in polynomial time. Conversely, any decision problem that can be solved in polynomial time by a Turing machine with an oracle in class E*_{det}(ExpLin) *is in* *.*

## 5. Removing the repeatability assumption

If we allow the same query to give different results on different occasions, then we have to be rather careful about the computational power.

As an extreme case, our innocent looking apparatus might be a radio receiver, tuned to a signal transmitted by little green men from Alpha Centauri. Further, these little green men might have invented a hypercomputer, and be transmitting its non-Turing computable output to our low-tech receiver at a constant bit rate.

To exclude weird scenarios, and actually get some results, we need some assumptions on the ‘non-repeatability’ or ‘non-determinism’ of queries. The easiest assumption is that the non-repeatability is of the form of statistically independent results. That is, if we repeat an identical experiment *n* times, the probability of the outcome of the (*n*+1)th time is completely independent of the previous *n* results, or indeed the fact that there were any previous experiments at all. So we could return to the axioms of given in §3, remove the repeatability assumption and continue. However, this is too complicated for our purposes and we need only a much simpler set of axioms. If we have to remove repeatability from what would otherwise be an oracle, then there should be at least one query for which the result is not repeatable, i.e. the same query gives different outputs on two occasions. We will assume that this result is an independent identically distributed random variable. Now, we forget about everything else, and make the definition of the oracle class Iid(*δ*), the Iid referring to *independent identically distributed* random variables. Why forget about everything else? The answer, as we shall see in theorem 5.3, is that we do not lose any computational power by doing so.

### (a) The complexity classes BPP and BPP//log★

We impose the following conditions on a Turing machine: (i) every step of a computation can be made in exactly two possible ways, which are considered different even if there is no difference in the corresponding actions (this distinction corresponds to two different bit guesses); (ii) the machine is clocked by some time constructible function, and the number of steps in each computation is exactly the number of steps allowed by the clock—if a final state is reached before this number of steps, then the computation is continued, doing nothing up to this number of steps; and (iii) every computation ends in a final state, which can be either *accept* or *reject*.

A set *A* is decided by a *probabilistic Turing machine*, in constructible time *t*, if, whenever *x*∈*A*, at least 2^{t(|x|)+1} computations (of length *t*(|*x*|)) end in an accepting state, and, whenever *x*∉*A*, strictly less than 2^{t(|x|)}+1 computations end in a rejecting state.^{8}

A set *A* is decided by a bounded probabilistic Turing machine in constructible time *t* if there exists a dyadic rational such that, whenever *x*∈*A*, the number of computations (of length *t*(|*x*|)) ending in an accepting state is greater than or equal to , and, whenever *x*∉*A*, the number of computations (of length *t*(|*x*|)) ending in a rejecting state is greater than or equal to .^{9} *BPP* is the class of such sets, decided by bounded probabilistic Turing machines in polynomial time.

For the probabilistic complexity classes, it is a matter of some controversy whether definition 4.1 is the appropriate definition of a non-uniform probabilistic class (e.g. of ). Notice that by demanding that there is a set *B*∈*BPP* and a function (in this order) such that *w*∈*A* if, and only if, 〈*w*,*f*(|*w*|)〉∈*B*, we are demanding a fixed probability , *ε*>0 (fixed by the Turing machine chosen to witness that *B*∈*BPP*) *for any possible correct advice*, instead of the more intuitive idea that the error only has to be bounded after choosing the correct advice. This leads to the following definition for the specific complexity class *BPP* that we will be using in what follows.

### Definition 5.1

is the class of sets *A* for which a probabilistic Turing machine TM, a prefix function and a constant exist such that, for every length *n* and input *w* with |*w*|≤*n*, TM rejects 〈*w*,*f*(*n*)〉 with probability at most *γ* if *w*∈*A* and accepts 〈*w*,*f*(*n*)〉 with probability at most *γ* if *w*∉*A*.

It is unknown whether .

### (b) Implementing the axioms for Iid(δ)

Here, we take the description in §2*b*, and interpret it in detail for a particular case, called Iid(*δ*). Here, is a given rational number.

### Definition 5.2

The axioms define the class of physical oracles Iid(*δ*) as follows.

—

*Real values.*The experiment is designed to find a physical parameter*x*∈(0,1).—

*Queries.*The query string is a constant.—

*Finite output.*The result, which we label*X*, is either 0 or 1.—

*Protocol timer.*Each experiment takes place in a fixed time.—

*Sufficiency of the protocol.*The value of*x*is known to be in (*δ*,1−*δ*).—

*Repeatability.*The result*X*is an independent identically distributed random variable with probability that*X*=1 being*x*.

The first comment is that, to the best of our current physical knowledge, radioactive decay does permit the construction of such an oracle in principle. We could take an atom of a radioactive isotope (e.g. ^{238}*U*), place it in a box for a year and see whether it had decayed during that time, the result *X*=1 being that it had decayed. The physical parameter *x*∈(0,1) would be the probability that the atom would decay in one year, which can be calculated from the half-life of ^{238}*U*. A parameter could be found from a textbook value of the half-life, about 4.46 Gyr, which would come with associated errors, but we could find a value of *δ* that would be good enough for the experiment. No query is needed, as every experiment would be identical. (It is not difficult to see how to improve on this experiment, but we only want an example!)

The second comment is that we have the following statement of the computational power of this class of oracles, corresponding to theorem 4.7 for the class *E*(ExpLin).

### Theorem 5.3

*Given a word decision problem in* *, there is an 1>x>0 so that any oracle in class Iid(δ) for real value x∈(δ,1−δ) can be used by a Turing machine to solve the problem in polynomial time. Conversely, any decision problem that can be solved in polynomial time by a Turing machine with an oracle in class* Iid*(δ) is in* *.*

Section 5*c,d* will be devoted to proving theorem 5.3, but the reader should note that the proofs are adapted from Beggs *et al.* [11] for the lower bound on computational power, and Beggs *et al.* [13] for the upper bound. In particular, we shall need the following result from Beggs *et al.* [11] to show that Iid(*δ*) can simulate the independent coin tosses with probability of heads required in the definition of *BPP*.

### Lemma 5.4

*Take a biased coin (probability of heads* *q*∈(*δ*,1−*δ*) *for some* , *and* *γ*∈(0,1). *Then, up to probability* ≥*γ*, *there is a sequence of independent biased coin tosses of length*
*which gives a sequence of independent fair coin tosses of length* *n*.

After the work of Balcázar & Hermo [20], we can safely assume without loss of generality that, for and , the length of any advice *f*(*n*) is exactly , for some depending on *f*. The earlier-mentioned remark on not losing any computational power by focusing on one experiment with an uncertain result is based on the fact that . This inclusion is not known to be strict (it is an open question to know whether *P*=*BPP*). However, it is known that *P*⊆*BPP* [21]. It follows, by monotonicity, that . Notice that [20].

### (c) Proof of a lower bound for the computational power of Iid(δ)

Take a word decision problem in . From definition 5.1, for this particular problem there is an advice function *f*(*n*) consisting of taking the first (round down) digits of a particular string *y*, and a fixed . Take a rational *γ*′>0 so that . Employ the coding of §4*b* for *y*, and call the resulting number *x*∈(0,1) and consider an Iid(*δ*) oracle with value *x*∈(*δ*,1−*δ*) for some rational *δ*>0. We show that a Turing machine using this oracle of type Iid(*δ*) can solve the given word decision problem in polynomial time, with probability of error ≤*γ*+2*γ*′.

There are three processes to consider: firstly, determining the required advice; secondly, simulating the fair coin toss oracle; finally, running the original program on the Turing machine. Each of these processes has its probability of error, and we shall make these *γ*′, *γ*′ and *γ*, respectively, giving a total probability of error of ≤*γ*+2*γ*′.

(1) *Determining the required advice*. To determine the first *k* places of *x*, we need to determine the value of *x* to within 2^{−k−5}. This is because the distance between *x* and any dyadic rational with denominator 2^{k} is at least 2^{−k−5}.

Suppose that the Turing machine queries the Iid(*δ*) oracle *z* times, and keeps count of how many times the result *X*=1 is obtained (denote this count by *L*). The value will be our estimation of *x*. As *L* is a random variable with expected value *μ*=*zx* and variance *ν*=*zx*(1−*x*), by Chebyshev's inequality, we conclude that, for every Δ>0,
To determine the first *k* digits of *x*, we need , so choosing Δ=*z*2^{−k−5}, we get
Thus, if we allow a probability ≤*γ*′ of making an error in determining the first *k* digits of *x*, then we need a number *z*_{k} of oracle calls given by (up to rounding)
Our problem is now simple—how big does *k* have to be for an input word of size *n*? For our problem in we require advice of length (round down). Because the coding substitutes three digits for every original digit, we need to read digits of *x*. To do this, we need *z* oracle calls, given by
5.1

(2) *Simulating the fair coin toss oracle*. For an input of size *m*, the original program on the Turing machine has polynomial runtime *p*(*m*). In particular, it can have called the fair coin toss oracle only *p*(*m*) times. To simulate this, we construct a list of *p*(*m*) independent fair coin tosses. From lemma 5.4, we can do this by calling the *Iid*(*δ*) oracle a total of
5.2
times, with probability of error ≤*γ*′. One point to remember is that, by definition 5.1, *m* is the length of the concatenation encoding 〈*w*,*f*(|*w*|)〉, where |*w*| is the length of the input word *w*, but as *m* has a linear bound in |*w*|, we still have *p*(*m*) having an upper bound that is a polynomial in |*w*|.

(3) *Running the original program on the Turing machine*. Now, we concatenate input word of length *n* with the advice obtained in stage (1) of length , and run the original program. Every time a call of the fair coin toss oracle would be demanded by the original program, we look up the list of pre-prepared simulated fair coin tosses made in part (2). This procedure has probability of error ≤*γ*, assuming that (1) and (2) were successful.

*Summary*. An upper bound on the error of the whole procedure can be given by just summing the errors of the constituent parts, i.e. *γ*+2*γ*′. Determining the times is a little more complicated. Part (1) requires a number of calls of the Iid(*δ*) oracle given by (5.1), and recording the result. This can be done in time polynomial on *n*. Part (2) requires a number of calls of the Iid(*δ*) oracle given by (5.2), and running a small program to turn them into fair coin tosses and recording the result. Part (3) requires a concatenation of the original input word with the advice found in part (1), and then running the original program, again in polynomial time given by (5.2), except for one point. That point is that we have to look up the pre-prepared table of simulated coin tosses instead of just calling a fair coin toss oracle, and this takes a longer time. However, consulting this polynomially long list many times still takes polynomial time. We conclude that the Turing machine with the given Iid(*δ*) oracle can solve our problem in polynomial time.

### (d) Proof of an upper bound for the computational power of Iid(δ)

We shall follow Beggs *et al*. [13] quite closely. Given a probabilistic oracle that gives two answers (say *X*=1 and *X*=0), we can represent the answers to the queries as a binary tree (called a probabilistic tree), where we label each path with its probability. After a certain number of queries, we have accept ‘A’ or reject ‘R’ output. An example of this is given in figure 2.

To get the probability of acceptance in figure 2, we take each descending path from the initial vertex, multiply the probabilities along its edges and add the results for each path ending in acceptance. Thus, the probability of acceptance in figure 2 is (going through the accepting paths from left to right)
We can ask what would happen if we change the probabilities in the tree, keeping the original Turing machine and tapes. Here, it is important to realize that the Turing machine has no knowledge of the probabilities in the tree; it only knows the outcomes. Suppose that we have two probabilistic trees, identical except for the probabilities labelling the edges. The depth of the trees (i.e. the maximum length of a branch descending from the initial vertex) will be *m*. There is a number *k* so that for any given edge, the difference in the probabilities for that edge between the two trees is ≤*k*. Then in Beggs *et al*. [13], it is shown that the difference in probability of acceptance for the two trees differs by at most 2*mk*. Using this, we can adapt the following lemma 5.5 from Beggs *et al.* [13].

### Lemma 5.5

*Let* *be a Turing machine with* Iid(*δ*) *oracle for value* *x*∈(*δ*,1−*δ*). *Suppose that* *decides some set* *A* *in time* *t*(*n*) *with error probability bounded by* . *Take a rational* *γ*′>0 *so that* . *Let* *be an identical Turing machine with* Iid(*δ*′) *oracle, differing only in its value* *x*′∈(*δ*′,1−*δ*′). *If*
*for any word of size* ≤*n*, *then the probability of* *making an error when deciding* *A* *is* ≤*γ*+*γ*′.

### Proof.

We set the depth of the tree to *t*(*n*), as there may be at most *t*(*n*) oracle calls carried out in time *t*(*n*). An upper bound to *k* (the maximum difference in probability labels on the respective edges) is given by the fraction in the statement, so the difference in the probability of acceptance (or similarly rejection) is at most 2*t*(*n*)*k* or *γ*′.

Now we can carry out the reverse of §5*c*. There we simulated an advice function by Iid(*δ*) oracle calls. Now, we simulate Iid(*δ*) oracle calls by an advice function and a fair coin toss oracle. This advice will be initial parts of the binary expansion of *x*∈(0,1). A sufficient length for the advice can be deduced from lemma 5.5, and we continue with the notation of that lemma. Suppose that *t*(*n*) is a polynomial function of *n*. Now, define to be *x* rounded down to *m* binary places *x*; so for example
The distance between *x* and is at most 2^{−m}, so if we set (round up to integer) and , then the conditions of lemma 5.5 are satisfied.

If *t*(*n*) is polynomial in *n*, then *m*_{n} is bounded by for some *a*,*b*. This means that we can use the first logarithmically long segment of *x* as advice to construct *x*′, and then, if we have an independent biased coin toss oracle with probability *x*′, we are done. However, we have only a fair (probability ) coin toss oracle in the definition of . However, we can simulate a biased coin toss oracle with probability *x*′, using a fair coin toss oracle. As *x*′ is a rational with denominator 2^{m}, we can generate a random number using *m* fair coin tosses. Each toss gives a zero or one in an integer. Then, compare this with the fraction *x*′ to determine whether the biased coin toss should be a head. For example, suppose that *x*′=0⋅11 (the rational ), and so *m*=2. The integers of length 2 from the fair coin toss oracle are (with equal probability) 00, 01, 10 and 11. Taking the expansion of *x*′, we have a head if the integer is <11; so we have a chance of a head. This completes the proof.

## 6. Conclusion

Our axioms for interfacing physical systems and algorithms are quite abstract. There are many experiments that satisfy the axioms and, as our earlier detailed analyses of particular physical experiments have established [11,13–15,18,19], these axioms are close to our theoretical understanding of reality. To reflect on their physical interpretation, consider the following question:

*What does the computational power of algorithms boosted by oracles that are physical systems tell us about the physical systems?*

The computational power of a Turing machine augmented by an oracle benchmarks how useful the oracle's information can be in boosting a computation; hopefully, it provides some precise method of quantifying the information provided by the physical experiment. Given our axiomatic characterizations, and the fact that their computational power transcends the Turing barrier, we consider the questions:

*How much information can be extracted from a physical process? How quickly can it be obtained?*

### (a) Physical interpretations of observing experiments

Consider the time bounds we discovered in particular experiments.

*Deterministic systems.* A time bound, such as the following inequality:
6.1
where *n*,*q*≥1 and *A*,*B*>0 are constants determined by the experiment, has an implication for the time taken to extract information from the ‘universe’. But the principle is simple—if we consider the binary expansion of the real world value *x*=0⋅*x*_{1}*x*_{2}*x*_{3}⋯ (for example), determining the binary digit *x*_{n} takes an amount of time at least exponential in *n*. In a certain sense, *the more information we have, the more difficult it is to extract new information*.

How relevant are exponential runtimes (6.1) to the work of an observer? The first point is that measuring finitely many quantities does not really alter (6.1). If the experimenter measures 15 quantities, and each obeys a version of (6.1), then we can plot the results on by treating each point as a coordinate. Then, we can take *x* and *y* as points of , use the standard distance on and get the same form for the time taken.

Where we might see a difference is where the observer can measure a potentially infinite number of quantities. Consider, for example, an astronomer who measures the brightness (absolute luminosity) of one star very accurately, it might be reasonable to expect (6.1) to apply. By the previous paragraph, if an astronomer measures the brightness of 24 789 stars very accurately, it might be reasonable to expect (6.1) to apply. However, the astronomer might measure the brightness of a different star every day, but to a certain fixed accuracy. In principle, this seems to allow for the extraction of information from the universe at a *constant* rate. However, there are at least two problems with this view.

(i) As more stars are observed, the observer is reduced to measuring more distant stars, and it is more difficult to measure the brightness of these fainter stars to the degree necessary to establish their absolute luminosity (indeed, it becomes more difficult to observe them at all). It is likely that similar problems could be raised with any observation of ‘arbitrarily many’ quantities.

(ii) The other problem is that as measurements are made, it may become more obvious that the brightness of stars is falling into a predictable pattern; in other words, a physical law may be postulated, and the variation allowed for within this law may be essentially random. This means that the information may be less useful than it seems at first, as it is a mixture of random variation and predictable information.

This brings us to two cases where observing a localized system might be considered to cause problems with our ideas of information.

*Random systems.* The first is the case of an inherently random system (see Calude [22]). An independent sequence of coin tosses (or similar statistical information) really can assist a computation, in terms of complexity theory. Further, according to our current interpretation of quantum mechanics, such sources of information really do occur in nature—for example, radioactive decay. In (6.1), we considered a deterministic experiment—there is no doubt about the outcome, just the matter of how long it takes to obtain it. However, in several papers (see Beggs *et al*. [11] or [13]), we considered probabilistic outcomes. Instead of continually improving the accuracy of an experiment, we ran an identical experiment many times, and used randomness and averaging to do the work of finding the desired information about the real world quantity. As long as we work in the established framework of complexity theory allowing for a certain probability of error, we found the same complexity theory results from such a probabilistic machine as from the non-probabilistic experimental setup giving (6.1). (To be precise, we should also add an independent coin toss machine to the non-probabilistic machine.) So far from being a problem, the probabilistic approach adds weight to the non-probabilistic oracle results, as these seemingly totally different approaches to experimentation produce the same results in complexity theory.

*Chaotic systems.* The most problematic classical observations, from the point of causing trouble with our conjecture, seem to be observations of chaotic systems. In principle, a real world initial condition *x*=0⋅*x*_{1}*x*_{2}*x*_{3}⋯ might be multiplied by an exponential factor in time, and we might read the binary digits *x*_{n} in a time linear in *n*. As an example, we could take the double and then fractional part map from [0,1) to itself:
However, this map is not time reversible, which is at variance with at least some of the philosophy of modern physics. If a chaotic system is reversible, and has a bounded phase space (a reasonably realistic condition), then such exponential growth could not be maintained forever. In this case, it is not so obvious what measurements could be made to determine the digits of *x* in constant time. In any case, a real world chaotic system suffers from another problem, which would make determination of *x* rather difficult. Random fluctuations, from whatever cause, are also magnified exponentially, and the net result is that, no matter what the initial conditions, the system is likely to become completely random for long enough time.

### (b) Scope and limits to measurement

There is a role for the axioms to explore the scope and limits to measurement.

*Invariance and portability*. In general, the purpose of a set of axioms is to isolate those essential properties that are both fundamental and common to a perceived or imagined class of systems. Later, the axioms come to define the class. The axioms bring with them the notions of an interface and models of its many possible implementations. Our axioms can be applied to a rather extraordinary range of experiments. However, the theorems show that:

*As far as the algorithm is concerned, the experiments satisfying the axioms have the same computational power, whatever their underlying science or technology*.

This is a physical idea similar to the notion of *portability* in software: programs need to run on different machines with different architectures and technologies.

*Non-determinism*. The experiments specified in earlier studies [11,13–15,18,19] have a simple form; yet they are found throughout science and engineering and provide a canonical type for the logical theory of measurement (see Beggs *et al*. [19]). The sets of mathematical axioms are very similar, but it is important to notice the fundamental role of the last property, *repeatability*. Firstly, the axiom used to prove upper bounds needs to be stronger than that for lower bounds in the case of exact and arbitrary precision.

Secondly, in our treatment of fixed precision, the repeatability axiom changes the theorems considerably: the use of a probability distribution introduces non-deterministic behaviour. The axioms lead us this general observation:

*Imprecision and, therefore, uncertainty and non-determinism are ubiquitous features of classical physics, once assumptions about upper bounds on accuracy or fixed error margins are employed in their description.*

Thus, at first sight, even in the simplest of physical situations, it may not be obvious whether apparent non-determinism in the behaviour of a system is intrinsic to the system, or caused by our measurement process.

*Turing barrier*. The axioms apply to many physical quantities, belonging to many physical theories, measured by means of many forms of equipment that are constructed from many technologies. The termination of algorithms is a fundamental problem that has been analysed in many ways (using hierarchies, degrees, proof systems and their ordinals). Consider two versions of the halting problem for Turing machines:
and
It is easy to reduce algorithmically *Halt* to *Total* but not vice versa.^{10} Formulations of the set *Total* exist in (e.g. one based on the tally set of unary encodings of Turing machines). Because the total halting problem for Turing machines lies in , the axioms demonstrate that it is common for physical measurements to transcend the algorithmic limits proposed by the Church–Turing thesis of 1936. The computational classification of the class may lead to a taxonomy of experimental methods.

## Acknowledgements

The research of J.F.C. is supported by Fundação para a Ciência e Tecnologia, Financiamento Base 2010-ISFL-1-209.

## Footnotes

One contribution of 18 to a Theme Issue ‘The foundations of computation, physics and mentality: the Turing legacy’.

↵1 As Turing suggested in [1], §4, the basic theorems of computability, such as undecidability of termination, can be proved for these

*S*-computable functions. Actually, there is nothing special about the operations chosen as basic in an algorithmic model as far as their elementary theory is concerned—a fact best exploited in computability theories over abstract algebras [2–4].↵2 A set

*A*is*Turing reducible*to set*B*if one can decide membership of*A*using an algorithm that allows oracle calls to decide membership in*B*.↵3 The classification of the non-computable in mathematics, using many types of hierarchies and degrees, is a huge achievement, mathematically and philosophically. For many years, the theory of the degrees was considered to be the mathematical epitome of computability theory because of the remarkable nature of priority methods—arguably, the most complex algorithms known—that were developed to solve Post's Problem.

↵4 The polynomial time hierarchy was implicit in Karp [5] and was formulated explicitly for the first time in Meyer & Stockmeyer [6], as a possible way of classifying problems not known to be in

*NP*; see also the earlier studies [7,8].↵5 The theorem is

*there exist computable oracles A and B such that*. In Balcázar*P*(*A*)=*NP*(*A*) and*P*(*B*)≠*NP*(*B*)*et al.*[10], there is an excellent introduction to the subject of positive and negative relativization results for oracles and complexity theory (in ch. 7 and 8).↵6 Further experiments await publication. We have also argued in Beggs

*et al*. [16,17] that some physical models are examples of algorithms with physical oracle calls.↵7 By definition, (〈

*w*,*v*〉)_{1}=*w*, (〈*w*,*v*〉)_{2}=*v*and 〈(*w*)_{1},(*w*)_{2}〉=*w*.↵8 The number of computations is the same, i.e. 2

^{t(|x|)}.↵9 The number of computations is the same, i.e. 2

^{t(|x|)}.↵10 The set

*Total*is complete*Π*_{2}and the set*Halt*is complete*Σ*_{1}.

- This journal is © 2012 The Royal Society