## 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.

## 1. Introduction

Consider a physical experiment in which some independent physical quantities *x*_{1}, *x*_{2}, … may vary and a series of corresponding behaviours *y*_{1}, *y*_{2}, … can be observed. The experiment defines a function *y*_{i}=*f*(*x*_{i}) or, more generally, a relation *r*(*x*_{i}, *y*_{i}) for *i*=1, 2, ….

1. *How can we use such an experiment to compute a function f, or decide a relation r, on a set of data? How do we measure its performance?*

To answer the above question, we must be precise about data representation by physical quantities, experimental equipment and experimental procedures, all of which will be based upon a thorough understanding of one or more physical theories. Let us call this type of calculation experimental computation; clearly, experimental computation includes calculation by analogue computers. For any type of experimental computation we can ask the question:

2. *Is experimental computation equivalent to algorithmic computation? If not, what is the difference?*

Perhaps, for a certain class of experiments, we can show that a function *f*, or relation *r*, is computable by an experiment belonging to the class if, and only if, it is computable by an algorithm? Perhaps we can show that there is a difference in performance: could an algorithmic problem of exponential time be computable by an experiment in polynomial time? The question is relevant for analysing the concept of a faithful computable simulation of a physical experiment.

There is a third question, connected to the last.

3. *If a physical experiment were to be coupled with algorithms, would new functions and relations become computable or, at least, computable more efficiently?*

In this case, can we explore if, and when, analogue–digital (AD) computation extends the purely digital. To pursue this question, we imagine using an experiment as an oracle to a Turing machine, which on being presented with, say, *x*_{i} as its *i*-th question, returns *y*_{i} to the Turing machine. In this paper, we will consider this idea of coupling physical experiments and Turing machines in detail.

The first thing to note is that choosing a physical experiment to use as an oracle is a major undertaking. The experiment comes with plenty of theoretical baggage: concepts of equipment, experimental procedure, measurement, observable behaviour, etc. Theorizing about the input–output behaviour of the experiment, and about the AD machine, involves us with all the three questions above.

In earlier work (Beggs & Tucker 2007*b*), an experiment was devised to measure the position of the vertex of a wedge to arbitrary accuracy, by scattering particles that obey some laws of elementary Newtonian kinematics. Let SME denote this *scatter machine experiment*. The Newtonian theory was specified precisely and SME was put under a theoretical microscope: theorems were proved, which showed that *the experiment was able to compute positions that were not computable by algorithms*. Indeed, the experiment SME could, in principle, measure any real number. Thus, Beggs & Tucker (2007*b*) contains a careful attempt to answer question 2 above, in the negative; it does so using a methodology developed and applied in earlier studies (Beggs & Tucker 2006, 2007*a*). The experiment is capable of hypercomputation if, and only if, the wedge position corresponds with a non-computable number mathematically.

To address question 3, here we propose to use the SME as an oracle to a Turing machine and to classify the computational power of the new type of machine, which we call an *AD scatter machine*. The SME is a physical process that, given fixed real *x* and dyadic rational *y*, possibly with errors, can test whether or not *y*≤*x*. Given the results in Beggs & Tucker (2007*b*), the use of SME could enhance the computational power and efficiency of the Turing machine. To investigate this, we must establish some principles that do not depend upon the SME.

In a Turing machine, the oracle is normally specified very abstractly by a set. Here, we have to design a new machine where the oracle is replaced by a specification of some physical equipment and an experimental procedure for operating it. The design of the new machine depends heavily upon the interface and interaction between the experiment and the Turing machine.

Consider the Turing machine performing a digital computation in which it generates queries that activate an experiment. The Turing machine will generate a (dyadic) rational number *x*_{i} that can be used to set an experimental parameter *p*_{i} of SME in one of two ways: we call the machine *error free* if *p*_{i}=*x*_{i}; and *error prone* if we can ensure that *p*_{i}∈[*x*_{i}−*ϵ*, *x*_{i}+*ϵ*] for an error margin *ϵ*>0. In the error-prone case, we further differentiate between fixed accuracy, where *ϵ*>0 is fixed for the particular SME, and arbitrary accuracy, where *ϵ*>0 can be made arbitrarily small.

Second, the whole process of receiving data from, and passing digital data to, the experiment is some form of AD protocol that consumes time (or other physical resources). By classifying AD protocols, we introduce these different types of AD Turing computation: *polynomial time error free*, *exponential time error free* and *polynomial time error prone* (with arbitrary and fixed precision).

Third, the SME has within it a wedge whose vertex is the site of singular physical behaviour: a particle hitting the vertex of the wedge may scatter randomly. Since the experiment may be non-deterministic, the machines are divided further into deterministic and non-deterministic.

Our use of the SME as an oracle reveals the need for a theory of oracles whose queries involve errors, time and other resources, and non-determinism. We analyse the complexity of computations by these new machines. Following inspiration found in the technical work of Siegelmann and Sontag (cf. Siegelmann 1999), we use *non-uniform complexity classes* of the form /, where is the class of computations and is the advice class. Examples of interest for are P and BPP; examples for are poly and log. The power of the machines will correspond to different choices of and .

We prove the following for the error-free machines (theorems 7.2 and 7.4, respectively).

*The class of sets which are decidable in polynomial time by error-free deterministic AD scatter machines with a polynomial AD protocol is exactly* *P/poly*.

*The class of sets that are decidable in polynomial time by error-free deterministic AD scatter machines with a strictly exponential AD protocol is exactly* *P/log ^{*}*.

For the error-prone machines, we prove (theorems 6.5, 6.6 and 8.1, respectively) the following:

*An AD scatter machine* (*either error-free or error-prone arbitrary precision*) *with a polynomial AD protocol can decide any set in* *P/poly in polynomial time*.

*An error-prone AD scatter machine with an arbitrary precision and with an exponential AD protocol can decide any set in* *P/log ^{*}*

*in polynomial time*.

*An error-prone AD scatter machine with fixed precision, given an independent uniformly distributed cannon position in the error interval, can decide any set in* *BPP//log ^{*}*

*in polynomial time*(

*independently of the protocol*).

First, in §2, we recall briefly the principles used to investigate experimental computation and tackle the questions 1 and 2 above; we extend the methodology to tackle the new question 3. The method was introduced and applied in Beggs & Tucker (2006, 2007*a*) and its principles were used in the analysis of the SME in Beggs & Tucker (2007*b*). The reader is referred to these papers for further explanations. In §3, we recall the SME from Beggs & Tucker (2007*b*) and in §4 we recall some theory of Turing machines with various oracles. In §5 we define the AD scatter machines. In the subsequent sections, we undertake the classification of their complexity. Finally, in §9, we reflect on some possible interpretations and implications of these results. We assume the reader is familiar with our earlier publication (Beggs & Tucker 2007*b*).

## 2. Investigating experimental computation using physical theories

We summarize a methodology for the theoretical investigation of questions 1 and 2 about experimental computation and extend it to answer question 3.

### (a) Experimental computation

To capture the diversity of examples, old and new, and to organize the subject of computation as physical process, we have introduced the idea of *experimental computation*. In this paper, we will need only some simple general ideas about experimental computation. For example, we suppose a partial function *y*=*f*(*x*), or relation *r*(*x*, *y*), can be computed by an experimental procedure in the following three stages:

input data

*x*are used to determine initial conditions of the physical system,the system operates for a finite or infinite time, and

output data

*y*are obtained by measuring the observable behaviour of a system at specified times.

The concept can be found in modelling natural systems (e.g. in classical wave mechanics: Kreisel 1974; Pour-El & Richards 1981, 1989; Smith 2001; Weihrauch & Zhong 2002; Stoltenberg-Hansen & Tucker 2003) and technologies for designing machines (e.g. in the nineteenth century mechanical systems of analogue computers: Thomson & Tate 1880; Bush & Hazen 1931; Shannon 1941; Pour-El 1974; Lipshitz & Rubel 1987; Graça & Costa 2003). Experimental computation depends upon choosing a physical system, which may be a part of nature or a machine, and is therefore dependent on specific physical theories that are needed to reason about what can be computed.

### (b) Methodological principles

The theory of algorithms is based on the idea that all data and computations on data can be analysed independently of any form of physical implementation. Specification, computation, reasoning and performance are matters for algebra and logic rather than physical theory. Upon this abstraction, exemplified in the Turing machine, rests our deep understanding of digital computation and its spectacular practical applications. The idea of experimental computation is to attempt to analyse physical models of computation *independently of the theory of algorithms*. Physical theories play a fundamental role in understanding experimental computation, which we have discussed at length elsewhere (Beggs & Tucker 2006, 2007*a*). To seek conceptual clarity, and mathematical precision and detail, we have proposed, in Beggs & Tucker (2006, 2007*a*), the following four principles and stages for an investigation of any class of experimental computations.

*Principle 1. Defining a physical subtheory*. Define precisely a subtheory*T*of a physical theory and examine experimental computation by the systems that are valid models of the subtheory*T*.*Principle 2. Classifying computers in a physical theory*. Find systems that are models of*T*that can through experimental computation implement specific algorithms, calculators, computers, universal computers and hypercomputers.*Principle 3. Mapping the border between computer and hypercomputer in physical theory*. Analyse what properties of the subtheory*T*are the source of computable and non-computable behaviour and seek necessary and sufficient conditions for the systems to implement precisely the algorithmically computable functions.*Principle 4. Reviewing and refining the physical theory*. Determine the physical relevance of the systems of interest by reviewing the truth or valid scope of the subtheory. Criticism of the system might require strengthening the subtheory*T*in different ways, leading to a portfolio of theories and examples.

To study experimental computation and seek answers to questions 1 and 2, the key idea is to lay bare all the concepts and technicalities of examples by putting them under a mathematical microscope using the theory *T* and, furthermore, to look at the computational behaviour of classes of systems that obey the laws of *T*. Our methodology requires a careful formulation of a physical theory *T*, which can best be done by axiomatizations, ultimately formalized in a logical language, i.e. a formal specification of a fragment of the physical theory.

### (c) Combining experiments and algorithms

The methodology above is designed to explore computation by physical systems in ways that are independent of the theory of algorithms. However, it is also interesting to consider the interaction between experiments and algorithms and to extend our methodology to answer question 3 of §1. Two types of interaction can arise naturally: (i) an algorithm may be needed to perform an experiment and (ii) an experiment may be used as a component to boost the performance of an algorithm.

First, it is easy to find examples of experiments for which some algorithmic computation is needed, e.g. experiments in which measurements are substituted into an algebraic formula. In such cases, we must also define precisely what algorithm will be used and reflect on how these calculations could be accomplished physically. Typically, in mechanics, we find algebraic formulae based on the operations of *x*+*y*, −*x*, *x*.*y*, *x*^{−1}, extended by . Suppose that a calculator is to be used, which computes using rational numbers. We may be tempted to add this calculator to the specification of the theory *T*. However, with principle 2 in mind, we may ask: can this calculator be implemented within the physics of the theory *T*, or some modest extension of *T*? Equivalently: is the theory *T* strong enough to implement the calculator? The same holds for any and all algorithms.

Second, and more dramatically, we can consider using a physical system as a component in an algorithm or class of algorithms. In this case, computations involve analogue and digital procedures and some form of *protocol* for exchanging data between them. Such hybrid computing systems have long been used in control theory.

A simple general way to do this is to choose an algorithmic model and incorporate the experiment as an oracle. There are many algorithmic models: Turing machines; register machines; programming languages; equational calculi, etc. The advantage of choosing Turing machines is their rich theory of computational complexity.

Suppose we wish to study the complexity of computations by *Turing machines with experimental or analogue oracles*. Given an input string *w* over the alphabet of the Turing machine, in the course of a finite computation, the machine will generate a finite sequence of oracle queries and receive a finite sequence of oracle answers. Specifically, as the *i*-th question to the oracle, the machine generates a string that is converted into a rational number *x*_{i} and used to set an input parameter *p*_{i} to the equipment. The experiment is performed and, after some delay, returns as output a rational number measurement, or observation, *y*_{i}, which is converted into a string or state for the Turing machine to process. The Turing machine may pause while interacting with the oracle. As an oracle, the experiment defines a function *y*_{i}=*f*(*x*_{i}) or, more generally, a relation *r*(*x*_{i}, *y*_{i}) for *i*=1, 2, … . But, clearly, there are digital–analogue and AD conversions involved in the protocol for data exchange. In summary,

*Principle 5. Combining experiments and algorithms*. Use a physical system as an oracle in a model of algorithmic computation, such as Turing machines. Determine whether the subtheory*T*, the experimental computation and the protocol extends the power and efficiency of the algorithmic model.

## 3. The scatter machine experiment

Experimenting with scatter machines is exactly as described in Beggs & Tucker (2007*b*); for convenience, we review the SMEs. First, following the methodology, we recall the underlying physical theory.

### (a) Theory specification

The SME is defined using a subtheory *T* of Newtonian mechanics, comprising the following laws and assumptions.

Point particles obey Newton's laws of motion in the two-dimensional plane.

Straight-line barriers have perfectly elastic reflection of particles, i.e. kinetic energy is conserved exactly in collisions.

Barriers are completely rigid and do not deform on impact.

A cannon, which can be moved in position, can project a particle with a given velocity in a given direction.

Particle detectors are capable of telling if a particle has crossed a given region of the plane.

A clock measures time.

In performing the experiment, we will *not* need (i) absolute precision in measurements, either in space or time or (ii) calculations with algebraic formulae. The theory *T* is independent of any notion of computation.

### (b) Specification of scattering machine

The machine consists of a cannon for projecting a point particle, a reflecting barrier in the shape of a wedge and two collecting boxes, as in figure 1.

The wedge can be at *any* position, but we will assume it is fixed for the duration of all the experimental work. Under the control of the Turing machine, the cannon will be moved and fired repeatedly to find information about the position of the wedge. Specifically, the way the SME is used as an oracle in Turing machine computations is this: a Turing machine will set a position for the cannon as a query and will receive an observation about the result of firing the cannon as a response. For each input to the Turing machine, there will be finitely many runs of the experiment.

The sides of the wedge are at 45° to the line of the cannon, and we take the collision to be perfectly elastic, so the particle is deflected at 90° to the line of the cannon, and hits either the left or right collecting box, depending on whether the cannon is to the left or right of the point of the wedge. Since the initial velocity is 10 m s^{−1}, the particle will enter one of the two boxes within 1 s of being fired. Any initial velocity *v*>0 will work with a corresponding waiting time. The wedge is sufficiently wide so that the particle can hit only the 45° sloping sides, given the limit of traverse of the cannon. The wedge is sufficiently rigid so that the particle cannot move the wedge from its position.

What happens if the particle hits the point of the wedge? This is the only exception to the description above. In this case, we shall not make any assumption about what happens, as any assumption would doubtless prove controversial physically. We shall suppose the following assumption.

*After each projection, the particle could enter either box or not enter any box. This means that the scatter machine is non-deterministic*.1

### (c) Operation of scattering machine

Suppose that *x* is the arbitrarily chosen, but fixed, position of the point of the wedge. For a given cannon position *z*, there are three outcomes of an experiment, which are as follows.

One second after firing, the particle is in the right box.

One second after firing, the particle is in the left box.

One second after firing, the particle is in neither box.

Figure 2 shows how the outcomes (l, r and o) are related to the position of the cannon relative to the wedge.

From the mechanics of the system, these outcomes can be connected to the wedge position *x* and parameter *z* in the following manner.

One second after firing, the particle is in the right box. Conclusion:

*z*≥*x*.One second after firing, the particle is in the left box. Conclusion:

*z*≤*x*.One second after firing, the particle is in neither box. Conclusion:

*z*=*x*.

The SME was designed to find *x* to arbitrary accuracy by altering *z*, so that in our machine 0≤*x*≤1 will be fixed, and we will perform observations at different values of 0≤*z*≤1. What values of *z* are allowed? We take the special case of the *dyadic scatter machine*, where we can set *z* to be any fraction in the range 0≤*z*≤1 with denominator a power of 2.

Consider the precision of the experiment. When measuring the output state the situation is simple: either the ball is in one tray, or in the other tray, or in neither. Errors in observation do not arise.

Now consider some of the non-trivial ways in which precision depends on the positions of the cannon. There are different postulates for the precision of the cannon, and we list some in the order of decreasing strength.

The SME is error free if the position of the cannon can be set exactly to any given dyadic rational number.

The SME is error prone with arbitrary precision if the position of the cannon can be set to within any arbitrarily small, but non-zero, precision.

The SME is error prone with fixed precision if the position of the cannon can be set only to within a fixed non-zero precision.

The following is a theorem in Beggs & Tucker (2007*b*), which shows that the behaviour of the SME is not computable by algorithms.

*The error-free dyadic scatter machine can compute the position of any point on a unit line segment to arbitrary accuracy: given any point x*∈[0, 1] *the machine can generate an infinite sequence* [*p*_{n}, *q*_{n}] *of rational number interval approximations of x such that for each n, we have**The entire system is bounded in the sense as follows*.

*Space: the system can be contained within an arbitrary shallow box*.*Mass: the total mass of the system is bounded*.*Time: the calculation of the n-th approximation takes place in linear time O*(*n*).*Energy: the calculation of the n-th approximation uses linear O*(*n*)*energy*.

This is proved by using an experimental procedure based on bisection. We start with the interval [0, 1] and fire the cannon at the endpoints and the midpoint of the interval. This will give which of the two half intervals [0, 1/2] and [1/2, 1] the vertex of the wedge is in. Then repeat using the appropriate half interval, etc. See Beggs & Tucker (2007*b*) for details.

With a little modification, the weaker assumption of an error-prone dyadic scatter machine with arbitrary precision would have sufficed. (To do this, we would have to use overlapping intervals and a ‘times 3/4 method’, rather than a bisection method.)

## 4. Turing machines, oracles and non-uniform complexity theory

To prepare for combining experiments and algorithms, we note some points about oracle Turing machines and probabilistic Turing machines. Then we recall briefly some notions of non-uniform complexity, which we use to analyse our new model of computation.

### (a) The oracle Turing machine

We assume that the reader is familiar with the idea of the deterministic Turing machine and its many definitions, which may vary the finite alphabet Σ of symbols, the control unit with its finitely many states, and the memory with its finitely many tapes. The oracle Turing machine is a device to which is added an *oracle*, which is thought of as a black box that can answer questions. The Turing machine can compute a word in Σ^{*}, which is interpreted as a question, and to each question the oracle deterministically gives an answer, yes or no. We will assume that an oracle Turing machine has at least three tapes: one or more *work tapes*, where calculations can be carried out; one *query tape*, for the purpose of asking questions of the oracle; and one *input tape* for input.

The control unit governs the computation, by reading and writing symbols in the tapes and by consulting the oracle. Among the states of the finite control unit are six special states. Three of these states are used to begin and halt the computation: these are called the *initial state*, the *accepting state* and the *rejecting state*. The remaining three states serve to interact with the oracle: these are called the *query state*, the *‘yes’ state* and the *‘no’ state*. In order to ask the oracle a question, the control unit writes the question in the query tape and moves to the query state. The finite control will then be interrupted, and the oracle will answer the question by resuming the computation in either the yes state or the no state, with the obvious meaning. Then the query tape is erased.

A computation of the oracle Turing machine on a word *w* begins with *w* written in the input tape of the machine, with the input tape head placed on the left-most symbol of *w*, and the control unit in the initial state. The computation will proceed as long as the control unit does not enter either the accepting or rejecting states. The input *w* is said to be *accepted* by the machine if the computation halts in the accepting state and *rejected* if it halts in the rejecting state.

Let *A*⊆Σ^{*} be a set of words over Σ. We say that *A* is decided by an oracle Turing machine if, for every input *w*∈Σ^{*}, *w* is accepted by when *w*∈*A* and rejected by when *w*∉*A*. We say that decides *A* in polynomial time, if decides *A*, and, for every *w*∈Σ^{*}, the number of steps of the computation is bounded by a polynomial in the size of *w*.

To each oracle corresponds a unique set *O* containing exactly the words to which the oracle answers *yes*. We may thus denote an oracle by its corresponding set *O* for which the Turing machine may calculate *w* and decide if *w*∈*O*. We write *P*(*O*) to stand for the class of sets decidable in polynomial time by machines with the oracle *O* and abbreviate *P*=*P*(Ø). An oracle is *sparse* if, for each size *m*, the number of words in it of size ≤*m* is bounded by a polynomial.

### (b) The probabilistic Turing machine

A probabilistic Turing machine is similar to the oracle Turing machine, but instead of a black box that answers questions, the finite control uses a *coin*. The probability of the coin turning up *heads* is *p*∈[0,1], and the probability of it giving *tails* is *q*=1−*p*. It is common to assume that *p*=1/2, i.e. that the coin is fair. This assumption is vital for the usual understanding of probabilistic machines, since a probabilistic machine with a rational *p* can be simulated by a deterministic machine, but this is not necessarily true for an arbitrary real *p*. If *p*=1/2 then the run-time of the deterministic machine is *O*(*t*^{2}.2^{t}), where *t* is the run-time of the probabilistic Turing machine (Balcázar *et al*. 1988, ch. 6).

The coin can be seen as a non-deterministic oracle that, when queried, will always answer *yes* with probability *p* and *no* with probability *q*. There is no need for the query tape but otherwise the behaviour of the probabilistic machine is like that of the oracle Turing machine. We thus choose to rename the query, yes and no states to be the *toss state*, the *heads state* and the *tails state*, respectively.

The decision criterion, however, must be different, because unless the control unit makes no use of the coin, the machine will not deterministically accept or reject the input. We will here describe one of the most common probabilistic decision criterion.

For a set *A*⊆Σ^{*}, a probabilistic Turing machine and an input *w*∈Σ^{*}, the *error probability* of for input *w* is the probability of rejecting *w* if *w*∈*A*, or the probability of accepting *w* if *w*∉*A*. We say that decides *A* with *bounded error probability* if there is a number *γ*<1/2, such that the error probability of for any input *w* is smaller than *γ*.2 *A* is decided in polynomial time with bounded error probability if, for every input *w*, the number of steps in the possible computations is always bounded by a polynomial in the length of *w*. We write BPP to stand for the class of sets decidable in polynomial time with bounded error probability using a balanced coin.

### (c) Non-uniform complexity classes

We will see that non-uniform complexity gives the most adequate characterizations of the computational power of the AD scatter machine.3 Non-uniform complexity classifies problems by studying families of finite machines (e.g. circuits) , where each _{n} decides the restriction of some problem to inputs of size *n*. It is called *non-uniform*, because for every *n*≠*m* the finite machines *C*_{n} and *C*_{m} can be entirely unrelated, while in uniform complexity the algorithm is the same for inputs of every size. A way to connect the two approaches is by means of *advice classes*: one assumes that there is a unique algorithm for inputs of every size, which is aided by certain information, called *advice*, which may vary for inputs of different sizes. The input is given, for a word *w*, by the concatenation of *w* and the advice, 〈*w*, *f*(|*w*|)〉, by means of a pairing function Σ*×Σ*→Σ* and its inverses (.)_{1} and (.)_{2}, which are all computable in linear time.

Let be a class of sets and a class of total functions. The non-uniform class / is the class of sets *A* for which some *B*∈ and some *f*∈ are such that, for every *w*, *w*∈*A* if and only if 〈*w*, *f*(|*w*|)〉∈*B*.

is called the *advice class* and *f* is called the *advice function*. Examples for are P, or BPP. We will be considering two instances for the class : poly is the class of functions bounded by a polynomial, i.e. poly is the class of functions *f*:→Σ^{*} such that, for some polynomial *p*, |*f*(*n*)|∈*O*(*p*(*n*)); log is the class of functions *g*:→Σ^{*} such that |*g*(*n*)|∈*O*(log(*n*)). We will also need to treat prefix non-uniform complexity classes. For these classes, we may only use 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.

Let be a class of sets and a class of functions. The prefix non-uniform class /^{*} is the class of sets *A* for which some *B*∈ and some prefix function *f*∈ are such that, for every length *n* and input *w* with |*w*|≤*n*, *w*∈*A* if and only if 〈*w*, *f*(*n*)〉∈*B*.

As examples we have P/log^{*}, or BPP/log^{*}. It is a matter of some controversy whether this is the appropriate definition of BPP/. Note that by demanding that there is a set *B*∈BPP, and a function *f*∈ (in this order) such that *w*∈*A* if and only if 〈*w*, *f*(|*w*|)〉∈*B*, we are demanding a fixed *ϵ*>0 (fixed by the Turing machine chosen to witness that *B*∈BPP) *for any possible 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 definitions.

BPP//poly is the class of sets *A* for which a probabilistic Turing machine , a function *f*∈poly and a constant *γ*<1/2 exist such that rejects 〈*w*, *f*(|*w*|)〉 with probability at most *γ* if *w*∈*A* and accepts 〈*w*, *f*(|*w*|)〉 with probability at most *γ* if *w*∉*A*.

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

It can be shown that BPP//poly=BPP/poly, but it is unknown whether BPP//log^{*}⊆BPP/log^{*}. After the work of Balcázar & Hermo (1998), we can safely assume without loss of generality that, for P/log^{*} and BPP/log^{*}, the length of any advice *f*(*n*) is exactly , for some *a*, *b*∈ which depend on *f*. Their proof generalizes for BPP//log^{*}.

It is important to note that the usual non-uniform complexity classes contain undecidable sets, e.g. P/poly contains the halting set. The non-recursive enumerability of the non-uniform complexity classes results exclusively from the non-computability of the advice functions. In fact, for any class of decidable sets and any class of advice functions, /(∩PR)⊆REC, where PR is the class of partial recursive functions and REC is the class of recursive sets. This means that computable advice results in computable behaviour, but possibly speeded up.4

There exists a characterization of the class P/poly that codifies the relationships between obtaining external information from polynomial length advice and obtaining it from oracles. The proof can be found in Balcázar *et al*. (1988, ch. 5).

*P/poly*=∪_{Osparse}*P*(*O*).

One possible oracle that we can associate with an SME is the set of finite prefixes of the vertex position of the wedge written in binary.

The methods of non-uniform complexity theory were used by Sontag and Siegelmann to study the computational power of deterministic neural nets with real weights, and probabilistic neural nets with rational weights and real probabilities (see Siegelmann 1999). In passing, they speculate on physical applications via Moore's generalized shift map. Bournez & Cosnard also applied non-uniform complexity to piecewise linear dynamical systems (Bournez & Cosnard 1996). Some speculations on mechanics and complexity are in Yao (2003).

## 5. The AD scatter machine

The Turing machine is connected to the SME in the same way as it would be connected to an oracle: we replace the query state with a *shooting state* (*q*_{s}), the yes state with a *left state* (*q*_{l}), and the no state with a *right state* (*q*_{r}). The resulting computational device is called the *AD scatter machine*, and we refer to the *vertex position* of an AD scatter machine when we mean to discuss the vertex position of the corresponding SME.

In order to invoke a SME, the AD scatter machine will write a word *z* in the query tape and enter the shooting state. This word will either be ‘1’, or a binary word beginning with 0. We will use *z* to denote both a word *z*_{1}, …, *z*_{n}∈{1}∪{0*s*:*s*∈{0,1}^{*}} and the corresponding dyadic rationalIn this case, we write |*z*| to denote *n*, i.e. the size of *z*_{1}, …, *z*_{n}, and say that the AD scatter machine is *aiming* at *z*.

After entering the shooting state, the computation will be interrupted and the SME will attempt to set the cannon at *z*. The place where the cannon is actually set at depends on whether the SME is error free or error prone. If the SME is error free, the cannon will be placed exactly at *z*.

If the SME is error prone with arbitrary precision, the cannon will be placed somewhere in the interval [*z*−*ϵ*, *z*+*ϵ*], where *ϵ*>0 is arbitrarily small. Of course, the interface between the Turing machine and the experimental apparatus needs to be able to specify this accuracy, and the most convenient way is to interpret the length of the word specifying *z* as giving the accuracy, so that the cannon will be placed at some point in the interval [*z*−2^{−|z|−1}, *z*+2^{−|z|−1}]. This means that for different words representing the same dyadic rational, the longest word will give the highest precision. To increase the accuracy, it is necessary only to add more zeros to the binary representation of *z*.

If the SME is error prone with fixed precision *ϵ* then the cannon will be placed somewhere in the interval [*z*−*ϵ*, *z*+*ϵ*]. In this case, we will have to specify information on the probability distribution on the interval [*z*−*ϵ*, *z*+*ϵ*], and we will take this to be the uniform probability distribution.

After setting the cannon, the SME will fire a particle, wait one second and then check if the particle is in either box. If the particle is in the right collecting box, then the Turing machine computation will be resumed in the state *q*_{r}. If the particle is in the left box, *or if it is in neither box*, then the Turing machine computation will be resumed in the state *q*_{l}.

With this behaviour, we obtain three distinct AD scatter machines.

An error-free AD scatter machine is a Turing machine connected to an error-free SME. We define an error-prone AD scatter machine with arbitrary precision, and an error-prone AD scatter machine with fixed precision similarly.

Consider the total time to be the sum of the times taken to communicate, initialize and perform the experiment. In the case of the SME, conducting an atomic experiment (one firing of the cannon and the subsequent measurement) takes constant time.

We say an AD protocol is *f*(*n*)-bounded if the total time taken by SME to process a query string of size *n* and return an answer is bounded by *f*(*n*). Polynomial and exponential bounds will be used. In the case of exponential bounds, we will say that a machine has a strictly exponential AD protocol if there is an exponential upper and lower bound to the time taken.

The error-free AD scatter machine has a very simple behaviour. If such a machine, with vertex position *x*∈[0, 1], sets the cannon position at a dyadic rational *z*∈[0, 1], we are certain that the computation will be resumed in the state *q*_{l}, if *z*<*x*, and in the state *q*_{r}, when *z*>*x*. If we make the further assumption that *x* is *not* a dyadic rational, and we will freely make this assumption throughout this text, then the error-free AD scatter machine will behave deterministically. We can thus define the following decision criterion.

Let *A*⊆Σ^{*} be a set of words over Σ. We say that an *error-free* AD scatter machine *decides A* if, for every input *w*∈Σ^{*}, *w* is accepted if *w*∈*A* and rejected if *w*∉*A*. We say that *decides A in polynomial time*, if decides *A*, and there is a polynomial *p* such that, for every input *w*∈Σ^{*}, the number of steps of the computation of on *w* is bounded by *p*(|*w*|).5

The error-prone AD scatter machines, however, do not behave in a deterministic way. If such a machine aims the cannon close enough to the vertex position, and with a large enough error, there will be a positive probability for both the particles going left or right. If the error can be made arbitrarily small, then for certain vertex positions we can recover deterministic behaviour by ensuring that the error interval lies entirely on one side of the vertex position. However, in general, a deterministic decision criterion is not suitable for error-prone machines. For a set *A*⊆Σ^{*}, an error-prone AD scatter machine , and an input *w*∈Σ^{*}, let the *error probability* of for input *w* be either the probability of rejecting *w*, if *w*∈*A* or the probability of accepting *w*, if *w*∉*A*.

Let *A*⊆Σ^{*} be a set of words over Σ. We say that an error-prone AD scatter machine *decides A* if there is a number *γ*<1/2, such that the error probability of for any input *w* is smaller than *γ*. We call *correct* those computations that correctly accept or reject the input. We say that *decides A in polynomial time*, if decides *A*, and there is a polynomial *p* such that, for every input *w*∈Σ^{*}, the number of steps in every correct computation of on *w* is bounded by *p*(|*w*|).

Standard proof techniques of structural complexity can be used to show that if there is an error-prone AD scatter machine that decides *A* in polynomial time with an error probability bounded by *γ*<1/2, then, for any polynomial *q*, there is another error-prone machine that decides *A* in polynomial time with an error probability, for inputs of size *n*, bounded by 1/2^{q(n)}. We may also assume, without loss of generality, that if an error-prone AD scatter machine decides a set *A* in polynomial time, then all of its computations halt after the same number of steps (Balcázar *et al*. 1988).

## 6. AD scatter machines compute P/poly and P/log^{*}

In the following subsections, we will study lower bounds for the computational power of the AD scatter machine under different assumptions on its behaviour.

### (a) Coding the advice function as a wedge position

Given an advice function *f*:→Σ^{*}, we place the wedge at the position given by the binary expansion,To determine the coding *c*(*f*(*m*)) of *f*(*m*), we first code the word *f*(*m*) as a binary number, using a binary code for every letter in its alphabet Σ (e.g. Unicode or ASCII). For example, we might suppose that the binary form of *f*(1) wasTo find *c*(*f*(*m*)), replace every 0 in its binary form by 100 and every 1 by 010. Thus our example becomesTo find each *f*(*m*) from *x*(*f*), read the binary digits of *x*(*f*) in triples. When the triple 001 is found, it means that we start reading the next *c*(*f*(*m*)), as the triple 001 never occurs as a triple in *c*(*f*(*m*)) (i.e. we use 001 as a separator). It is important to note that the length of *c*(*f*(*m*)) is a linear function of the length of *f*(*m*).

Of course, not every element of [0,1] occurs as an *x*(*f*). The reader may note that no dyadic rational can occur, as they would have to end in 0000… or 1111…, and the triples 000 and 111 do not occur in any *x*(*f*). This is good news, in that we cannot have any ambiguity in the binary expansion. For example, 1/2 has the binary expansions 01000… and 00111…, but this sort of ambiguity is limited to dyadic rationals. Later in the paper, we will need a rather stronger result about which numbers cannot be of the form *x*(*f*).

*Given a dyadic rational k*/2^{3n}∈[0, 1] *for integer k*, |*x*(*f*)−*k*/2^{3n}|>1/2^{3n+3} *for all f*.

To prove this it is necessary only to note that whatever the first 3*n* binary digits of *x*(*f*), the next triple is of the form 100 or 010 or 001. ▪

*Given a dyadic rational k*/2^{n}∈[0, 1] *for integer k*, |*x*(*f*)−*k*/2^{n}|>1/2^{n+5} *for all f*.

Consider the cases *n*=3*m*, *n*=3*m*+1 and *n*=3*m*+2 separately and use lemma 6.1. ▪

As we shall see, the purpose of these results is to ensure that various error intervals for the cannon lie entirely on one side of the wedge position.

### (b) AD scatter machines with a polynomial AD protocol can decide P/poly in polynomial time

In this subsection, we will show that both error-free and error-prone arbitrary precision AD scatter machines with a polynomial AD protocol can decide sets in P/poly in polynomial time. We shall leave the more complicated problem of determining an upper bound for the complexity of the sets that these machines can decide until later.

Let *A* be a set in P/poly, and, by definition, let *B*∈*P*, *f*∈poly be such thatNow take an AD scatter machine with the position of the wedge set to *x*(*f*), as described in §6*a*. For a word *w*, if we can determine the advice *f*(|*w*|) in polynomial time in |*w*|, then the Turing machine can determine 〈*w*, *f*(|*w*|)〉 in polynomial time, so the problem is solved in polynomial time. In turn, to determine *f*(|*w*|) it suffices to show that we can read the first *n* binary places of the wedge position *x*(*f*) in polynomial time in *n*.

*An error-free AD scatter machine with a polynomial AD protocol can determine the first n binary places of the wedge position x*(*f*) *in polynomial time in n*.

Use the bisection procedure already outlined, which requires *n* steps, with step *m* requiring an amount of time polynomial in *m*. Multiplying this gives a total amount of time polynomial in *n*. The only way in which the bisection procedure could go wrong is if the wedge is at a dyadic rational, and this cannot be the case for *x*(*f*), as noted in §6*a*. ▪

Now we come to the error-prone arbitrary precision case, which is solved in almost exactly the same way. The work lies in choosing the errors so that the same process actually works, and for that we need corollary 6.2.

*An error-prone arbitrary precision AD scatter machine with a polynomial AD protocol can determine the first n binary places of the wedge position x*(*f*) *in polynomial time in n*.

Use the bisection process again. At the *m*-th stage in the bisection process (involving dyadic rationals with denominators 2^{m}), we set the error in the desired cannon position *k*/2^{m} to be 1/2^{m+5}. By corollary 6.2, the wedge position cannot be in the error interval about the given dyadic rational, and thus the result of the experiment is the same as though the cannon was at the given dyadic rational *k*/2^{m}. The cost in doing this is polynomial in *m*, and if we sum to *m*=*n* we get the total time polynomial in *n*. ▪

*An AD scatter machine* (*either error-free or error-prone arbitrary precision*) *with a polynomial AD protocol can decide* *P/poly* *in polynomial time*.

From the discussion earlier in this subsection, and propositions 6.3 and 6.4. ▪

### (c) AD scatter machines with an exponential AD protocol can decide P/log^{*} in polynomial time

In this subsection, we will show that both error-free and error-prone arbitrary precision AD scatter machines with an exponential AD protocol can decide sets in P/log^{*} in polynomial time.

First we must decide on a coding for log^{*} advice, where the reader is reminded that the advice *f*(*n*) can be used to decide all words *w* with |*w*|≤*n*. We can recursively define *y*(*f*) as the limit sequence of *y*(*f*)(*n*), using the coding *c* given in §6*a* by starting withand 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, ….

Now take *w* with 2^{m−1}<|*w*|≤2^{m}. We read the binary expansion until we have counted a total of *m*+1 triples 001. 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 *y*(*f*) must we read in order to reconstruct *f*(2^{m})? We start with |*c*(*f*(*n*))|*L*≤log_{2}(*n*)+*K* (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 separators, so the number of digits is logarithmic in |*w*|. Using the bisection method, we need to make *O*(log(|*w*|)) experiments, and there is a maximum length to the binary form of the dyadic rationals for these experiments which is also *O*(log(|*w*|)). Then the total experimental time is *O*(log(|*w*|)) times an exponential of *O*(log(|*w*|)), which is polynomial.

*An AD scatter machine* (*either error-free or error-prone arbitrary precision*) *with an exponential AD protocol can decide P/log ^{*}*

*in polynomial time*.

The wedge position is *y*(*f*) (as just described) for the advice function *f*. We only have to revise the statement of the propositions 6.3 and 6.4 to say that they can read log(*m*) digits in time polynomial in *m*. ▪

## 7. An upper bound for the computational power of error-free machines

### (a) What do deterministic AD error-free scatter machines compute?

We have seen that AD error-free scatter machines can solve any problem in P/poly (for polynomial protocols) or in P/log^{*} (for exponential protocols) in polynomial time. Now we may ask the converse, if a set is decidable by an AD error-free scatter machine in polynomial time, what complexity class does it belong to? One difficulty here is what happens if, during the calculation, the projectile hits the edge of the wedge? In §6, the codings were constructed to produce wedge positions that were not dyadic rationals, so this problem did not arise.

Let us begin by considering a deterministic machine. This means that the same result is always given if the projectile hits the edge of the wedge, and there is no probability necessary. If at most *n* binary places can have been written in the query tape describing the cannon position, then the cannon position must be set to a position *m*/2^{n} for some integer 0≤*m*≤2^{n}. In this case, it might be thought that the first *n* binary places of the wedge position *x* would suffice to simulate the scatter machine, but this is not necessarily true. (We always use the terminating form of the binary expansion, i.e. 0.1 not 0.0111… .) For example, suppose that *n*=3 and we have *x*=0.010 to three places (no rounding!). For any position *m*/2^{3}≠0.010, we have determined the scattering, but what about *m*/2^{3}≠0.010? This depends on how the binary expansion of *x* continues. If *x*>0.010 (e.g. *x*=0.010000100…) then the scattering is determined, but if *x*=0.010 then the particle has hit the vertex of the wedge, and something different may occur. The wedge position *x* could be coded 010=(meaning *x*=0.010) or 010>(meaning *x*>0.010).

Now we can code up all the binary expansion of *x* into an infinite word *q*(*x*). After each power of two binary places we append either an = or a >, depending on whether *x* is equal to its expansion truncated to that number of places or not. For example, we could have the following:but not these,as once we have equality we must have all zeros and all equalities. To get the value of *x*, just strip out all the ='s and >'s. Thus the allowed codes above give the numbers 0.0000001000001100… (with more digits to follow) and 0.0000001 exactly.

Let *O* be the (sparse) set of finite prefixes of *q*(*x*).

*Suppose that* *is an error-free AD scatter machine, with a polynomial AD protocol and deterministic scattering at the wedge position. Suppose that* *decides a subset A*⊆Σ^{*} *in polynomial time. Then A is in P/poly.*

By definition 5.3, there is a polynomial *p* such that, for every *w*∈Σ^{*}, the number of steps of the computation is bounded by *p*(|*w*|). Then at most *p*(|*w*|) symbols will have been written on the query tape. If we take the least *n* so that 2^{n}≥*p*(|*w*|), then the prefix of maximum length we need during the computation has length 2^{n}+*n*+1, which is polynomial in |*w*|. The scatter machine deciding *A* can be modified by substituting all calls for the SME by calls to the oracle *O*. Applying theorem 4.5 we get *A* in P/poly. ▪

*The subsets of Σ*^{*} *which are computable in polynomial time by deterministic error-free AD scatter machines with a polynomial AD protocol is exactly P/poly*.

Immediate from propositions 7.1 and 6.5. ▪

*Suppose that* *is an error-free AD scatter machine, with a strictly exponential AD protocol and deterministic scattering at the wedge position. Suppose that* *decides a subset A*⊆Σ^{*} *in polynomial time. Then A is in* *P/log ^{*}*

By definition 5.3, there is a polynomial *p* such that, for every *w*∈Σ^{*}, the number of steps of the computation is bounded by *p*(|*w*|). Then the maximum number of symbols that have been written on the query tape and used to set the scatter machine is logarithmic in |*w*|, say ≤*A* log_{2}(|*w*|)+*B* (this is where we use *strictly* exponential). If we take the least *n* so that 2^{n}≥*A* log_{2}(|*w*|)+*B*, then the prefix of maximum length we need during the computation has length 2^{n}+*n*+1 (which is logarithmic in |*w*|). The proof follows the proof of proposition 7.1, but paying attention to the fact that we only need to consult words of logarithmic size. ▪

*The subsets of* Σ^{*} *which are computable in polynomial time by deterministic error-free AD scatter machines with a strictly exponential AD protocol is exactly* *P/log ^{*}*.

Immediate from propositions 7.3 and 6.6. ▪

### (b) What do non-deterministic AD error-free scatter machines compute?

Now we come to a non-deterministic scatter machine. Here we must make some assumptions—there must be some description printed on the box of the AD scatter machine—in order to make sensible proofs. The simplest is that the wedge position is not a dyadic rational.

*The subsets of* Σ^{*} *which are computable in polynomial time by non-deterministic error-free AD scatter machines that are known to have non-dyadic rational wedge position with a polynomial AD protocol is exactly* *P/poly*.

Almost immediate from propositions 7.1 and 6.5. For proposition 6.5, we note that the required wedge position is non-dyadic. For proposition 7.1, if we know that the wedge position is non-dyadic, then the behaviour is exactly that of a corresponding deterministic machine, as the cannon can never be set to the wedge position. ▪

If we are told nothing about the wedge position for the machine, there is a procedure that will determine some information: take your favourite computable function *g* from to the dyadic rationals in [0,1] which takes every value infinitely many times. The cannon is fired successively at the positions *g*(*n*). At the first time that the result is different for *n*≠*m*, where *g*(*n*)=*g*(*m*), report ‘the machine is non-deterministic with wedge position *g*(*n*)’. If the machine is non-deterministic with a dyadic rational wedge position, then the program will terminate with probability 1. Otherwise it will run indefinitely. There is no bound on the run-time for the terminating cases.

Once a dyadic rational wedge position is known, we can perform sequential cannon firings at that point to try to find information about the probability of scattering right and left. For simplicity (and because it is not at all obvious what else to do), we assume that the results of sequential firings of the cannon at that position produce *independent* results. That is, the probability of going left or right at the *n*-th firing is completely independent of the results of all the previous firings. Then we have an independent random generator, with probability *q* of giving result *r* and 1−*q* of giving result *l*.

*The computational power of an error-free AD scatter machine with known dyadic wedge position and independent scattering right from the edge of the wedge with probability q is the same as that of a Turing machine with an independent random number oracle with probability q*. (*Note that we use a probabilistic decision criterion here*.)

The position itself can be described by a finite string, and therefore could be hard-wired into a modified Turing machine. The only thing we are left with is the independent random generator. ▪

The computational power of such an oracle depends on *q*. For 0<*q*<1 and given *γ*∈[0, 1), it is possible to find a sequence converging with probability ≥*γ* to *q*. This happens even if the real number *q* is not computable. If *q*=1/2, then in polynomial time the AD scatter machine can compute exactly BPP (assuming an appropriate decision criterion). In fact, for any *q*∈(0, 1) we can compute BPP, by simulating a fair (probability 1/2) coin toss by using the following lemma 7.7.

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

The method to simulate one fair toss is to toss the biased coin twice, and

if the result is HT then output H as a fair toss,

if the result is TH then output T as a fair toss, and

if the result is HH or TT, then toss the coin twice again and continue.

The probability of this process halting in one step is *r*=2*q*(1−*q*), and the probability of having to toss again is *s*=1−*r*. This process is repeated until cases (i) or (ii) occur, and then the whole method is repeated *n* times. The total number of tosses *T*_{n} for this to happen is given by the negative binomial distribution, with mean and variance, (Note: if you look in a text book for the mean, you will not find the +2*n* part; this is included as we need to include the time for the successful tosses, not just the standard waiting time until success.)Now we use Chebyshev's inequality in the form,If we put *t*=*ηn* and substitute the value of the variance, thenThe worst case for the probability of failure is then the *n*=1 case, and we getTo get the probability of ‘failure’, i.e. *T*_{n}≥*μ*+*ηn* less than 1−*γ*, we needand then using *r*≥2*δ*(1−*δ*) gives the worst case, and the answer. ▪

## 8. Reducing the precision of the cannon

We will now study the class of sets decidable in polynomial time by an error-prone AD scatter machine with fixed precision. We will show that such machines may, in polynomial time, make probabilistic guesses of up to a logarithmic number of digits of the position of the vertex. We will then conclude that these machines can decide BPP//log^{*}. The reader is reminded that we assume that there is a fixed error *ϵ*>0, and that if the cannon is instructed to fire at position *x*, then it actually fires in the interval [*x*−*ϵ*, *x*+*ϵ*] with a uniform probability distribution. Furthermore, we assume that each time the cannon is set to a position, the corresponding random cannon position is independent of previous positions. First we consider some more probability.

We employ the coding of *c* for log^{*} advice, and call the resulting number *r*∈(0, 1). To determine the first *k* places of *r*, we need to determine the value of *r* to within 2^{−k−5}. This is because the distance between *r* and any dyadic rational with denominator 2^{k} is at least 2^{−k−5}. Now, suppose that *ϵ* is the error when positioning the cannon. We then set the vertex of our AD scatter machine at the position *x*=1/2−*ϵ*+2*rϵ*. Our method for guessing digits of *r* begins by commanding the cannon to shoot from the point 1/2 a number *u* times. If the SME is carried out by entering the shooting state after having written the word 01 in the query tape, the cannon will be placed at some point in the interval [1/2−*ϵ*, 1/2+*ϵ*], with a uniform distribution. Then, we conclude that the particle will go left with a probability of *r* and go right with a probability of 1−*r*.

After shooting the cannon *u* times in this way, we count the number of times that the particle went left, which we denote by *L*. The value will be our estimation of *r*. In order for our estimation to be correct in the sufficient number of digits, it is required that . By shooting the cannon *u* times, we have made *u* Bernoulli trials. Thus, *L* is a random variable with expected value *μ*=*ur* and variance *ν*=*ur*(1−*r*). By Chebyshev's inequality, we conclude that, for every *Δ*,Choosing *Δ*=*u*2^{−k−5}, we getThus, if we allow a probability ≤*γ*_{k} of making an error in determining the first *k* digits of *r*, we need a number *u*_{k} of cannon firings given by (up to rounding.)Our problem is now simple—how big does *k* have to be for a word of size *n*? We know that we require *a* log_{2}*n*+*b* digits, but we do not *a priori* know *a* and *b*. We need to keep reading the digits of *r* until we have encountered the appropriate number of 001 markers to see that we have all of *f*(*n*). So we fire the cannon *u*_{k} times, ask if we have enough 001 markers in the accurate *k* digits, and if not we fire the cannon *u*_{k+1} times, and so on. The problem is that if we make a mistake at any stage, we can prematurely terminate the process with the wrong answer. If the probability of making a mistake is the same for every *k*, it is very likely that we will make a mistake before we terminate for the correct reason. For this reason, we set *γ*_{k}=*γ*/2^{k+1}, givingNow we implement the following algorithm:

set

*k*=1,fire the cannon

*u*_{k}times,check to see if we have found all of

*f*(*n*) in the first*k*digits, andif not, increment

*k*and go to (2).

The probability of making a mistake (i.e. incorrectly stopping at (3)) is now less than *γ*/2. Given that we do not make a mistake, the first time that *k* is large enough for enough 001s to be contained we will identify this with probability *γ*/2^{k+2}, so overall we have a probability of not correctly identifying *f*(*n*) at the first possible stage of less than 1−*γ*.

But how much time does this take? The total number of firings iswhich is polynomial in *n*.

*An error-prone AD scatter machine with fixed precision can decide any set in* *BPP//log ^{*}*

*in polynomial time*.

## 9. Examining the results

We have introduced a class of machines in which physical and symbolic processes are combined: our AD Turing machine combines experimental and algorithmic procedures in a simple way, by thinking of the physical system as some sort of oracle to the Turing machine. We have considered the question: *how do these AD Turing machines compare with the Turing machines we know?*

To begin to answer this question we chose a particular experiment, the SME, which had earlier been studied from the point of view of computation (Beggs & Tucker 2007*b*). Here, we extended the original SME to allow for both variable and fixed errors in its operating procedures. We analysed a portfolio of AD Turing machines based on these SMEs, using non-uniform complexity theory, which is suited to studying computations with oracles. Let us reflect on the results.

The original SMEs are what we call the error-free machines. Here we find that for the deterministic case, error-free AD scatter machines with the vertex at *x* compute the same as Turing machines equipped with the set [0, *x*]∩*D* as a binary language oracle, where *D* is the set of dyadic rationals seen as binary strings. For the non-deterministic case, where the wedge produces random scattering, we found similar results for any non-dyadic vertex position *x*∈[0, 1]−*D*.

However, in the analysis of the new error-prone SMEs, there are two cases: (i) the SME can be set to an arbitrary error presented by the Turing machine and (ii) the SME can be set to a fixed error *ϵ*. Here the connection with familiar oracle Turing machines breaks down. In case (i) we note that no physical assumptions about the SME are required other than the arbitrary accuracy assumption. In case (ii), however, we assumed a uniform probability distribution, and the independence of trials, for the positioning of the cannon within the fixed error margin [*x*−*ϵ*, *x*+*ϵ*].

The theorems show that each variant of the AD scatter machine has some hypercomputational power. For instance, if *K* is a set of codes for the halting problem then {0^{n}:*n*∈*K*} can be decided by an error-free AD scatter machine, or by an error-prone AD scatter machine with arbitrary precision. Of course, the hypercomputational power of the AD scatter machine arises from the nature of the vertex position *x*, which is a matter for subtle physical analysis of the kind found in Beggs & Tucker (2007*b*). But whenever the vertex position is a computable real number, then the AD scatter machine can compute no more than the Turing machine.

We assumed that we have a sharp wedge with respect to point particles, whose vertex position is measured by a precise point *x*. The existence of an arbitrarily sharp wedge contradicts atomic theory, and so it is easy to find reasons to object to the scatter machine as a counterexample to the commonly formulated physical Church–Turing theses. The relevance of the AD scatter machine as a model of computation is that it allows one to think with *great mathematical precision and detail* about how computations can be made by physical systems which is one of the central motivations of our methodology and programme.

The work here addresses directly some aspects of the role of oracles in dealing with hypercomputation. Oracles are so versatile that it would be surprising if the computability and complexity theories of machines with oracles could not be adapted to handle whatever computational behaviours we find in physical theories. Seen from established work with oracle Turing machines, one can interpret this work as developing carefully controlled *Gedankenexperimente* to implement certain oracles that arise from thinking about the physical world. From this point of view the technical question is: what can we compute if we have *the possibility of measuring an answer to the predicate y*≤*x, for an arbitrary, fixed real value x and a given dyadic rational y*. We could have replaced the barriers, particles, cannon and particle detectors with any other physical system with this behaviour. So, for the Turing machines the scatter machine becomes a tool to answer the more general question about *measurement*:

*If we have a physical system to measure an answer to a predicate* (*such as y*≤*x*), *to what extent can we use this system in feasible computations?*

The error or difficulty that such a measurement entails is represented in the SME by making assumptions on the placement of the cannon. We have given an answer to this question for the case when there is no error and for two simplistic models of error, and studied the case when more precise measurements require a high amount of some resource. In each case, a non-computable *x* will result in hypercomputational properties.

Using the scatter machine in this sense, it is very interesting to note that a system to measure the answer to the predicate *y*≤*x* is very limited in its computational power, unless the precision of measurement can be made arbitrarily high—such as in §6. Without this proviso, the access to the information of *x* becomes difficult, or extremely slow. Even with arbitrarily small error, it does not appear that such a system can be feasibly used, e.g. to answer the halting problem or to solve NP-complete problems. In the first case, it would take an unfeasible number of *O*(2^{n}) experiments to obtain an answer for the halting problem on inputs of size *n*, and for the second case, it is unlikely that NP is contained in P/poly, because this would imply the collapse of the polynomial hierarchy (cf. Karp & Lipton 1980). Thus, if we accept that ‘measuring a physical constant *x*’ means ‘answering the predicate *y*≤*x*’ as above, our results can be seen as a critical analysis of the claim that hypercomputation could be achieved by measuring a presumably uncomputable physical constant (as suggested in Copeland & Proudfoot (1999), and severely criticized in Davis (2006*a*)).

The SME is able to support further investigations, including an analysis of oracles and their information content using Kolmogorov complexity.

The study of models capable of hypercomputation can be extremely subtle (cf. Loff & Costa in press) and a little controversial (cf. Davis 2006*a*,*b*). However, with our methodology for studying experimental computation, we can achieve clear insights and definite results.

## Acknowledgments

E.B. and J.V.T. would like to thank the EPSRC for their support via grant EP/C525361/1. J.F.C. and B.L. were supported by FEDER and FCT Plurianual 2007. The authors would like to thank Barry Cooper for raising questions about the physical reality of oracles.

## Footnotes

↵In a physical sense, not the technical definition of non-determinism in Turing machines.

↵Under the assumption that

*p*=1/2, one can represent every possible computation of a probabilistic Turing machine on an input*w*as a complete binary tree, where each node of the tree corresponds to the global state, or configuration, of the machine after each possible sequence of coin tosses. Then the probability of error is simply the fraction of leaves of this tree, which incorrectly accept or reject*w*.↵For an interesting definition of how we can compare computational power among different models of computability, see Boker & Dershowitz (2005).

↵The reader should note that exponential length advice suffices to decide all sets, because for length

*n*there are at most 2^{n}words, which can be concatenated to give the advice.↵Note that as scatter machines can decide all sets, the interest here is the characterization of the time constraints.

- Received February 27, 2008.
- Accepted May 28, 2008.

- © 2008 The Royal Society