Gilles Dowek
email: gilles.dowek@inria.fr

The physical Church-Turing thesis and non deterministic computation over the real numbers

Keywords: physical Church-Turing thesis, computability over the real numbers, non determinism

On the real numbers, the notions of a semi-decidable relation and that of an effectively enumerable relation differ. The second only seems to be adequate to express, in an algorithmic way, non deterministic physical theories, where magnitudes are represented by real numbers.

The physical Church-Turing thesis, if it holds, suggests that the laws of nature can be expressed, not only in the language of mathematics, but also in an algorithmic language. Gandy's argument, that support the physical Church-Turing thesis, even suggests that these algorithms may operate on the elements of a countable set, such as the natural numbers, the rational numbers, the elements of an extension of finite degree of the field of rational numbers, the computable real numbers, etc.

Nevertheless, the desire to remain as close as possible to the traditional formulations of the laws of nature rather leads to try to describe these laws using algorithms operating on real numbers. This use of algorithms operating on real numbers may be just a first step towards that of algorithms operating on the elements of a countable set, but it may also simplify the formulation of the laws of nature, that might be more complex, if formulated as algorithms operating on the elements of a countable set. We do not claim that physical magnitudes are adequately described by real numbers, neither that all the infinite amount of information contained in a real number is relevant in this description, but simply that real numbers have been used to describe physical magnitudes and that this justifies the attempt to describe the laws of nature in an algorithmic way, using algorithms operating on real numbers.

An algorithmic formulation of the laws of nature should not predict more than the usual propositional formulation of the same laws. As some of the laws of physics are non deterministic, it seems that we must use non deterministic algorithms to express these laws in an algorithmic way.

The notion of a non deterministic algorithm and that of an algorithm operating on real numbers have been defined and well studied. It seems however that the conjunction of these two notions, i.e. the notion of non deterministic algorithm operating on real numbers, remains to be defined. We discuss in this paper what such a definition could be.

We assume that the notion of a computable function operating on the natural numbers is known. The set of such functions can, for instance, be defined as the smallest set containing the projections, the null functions, the successor function and closed by composition, definitions by induction and minimization. Other definitions based on the notions of Turing machines, rewrite systems, etc. are possible. This notion extends to countable sets by numbering their elements.

Non deterministic algorithms 1.Algorithms, functions and relations

A deterministic algorithm, that takes an element of a set A as an argument and returns an element of a set B if it terminates, defines a partial function from A to B.

A non deterministic algorithm, in contrast, defines a relation between the sets A and B and it is therefore natural to try to characterize the relations that correspond to these algorithms. A relation R between two sets A and B can always be seen as a function from A to the powerset of B: the function that maps the element x to the set R x = {y ∈ B | x R y}. This leads to raise, in a first step, the question of the representation of sets with computable functions.

Characteristic functions

When the set B is countable and the sets R x are all finite, they can be numbered. But, this solution is not available when, as it is often the case in physics, the sets R x may be infinite.

In this case, a possibility is to represent the set R x is by an algorithm expressing its characteristic function. Using this representation of sets leads to represent the relation R by a function f that maps x to a function that maps y to the value 1 or 0 depending on the fact that x R y or not. Using the fact that a function taking values in a functional space is equivalent to a function of several arguments, the relation R can also be represented as the binary function that maps (x, y) to 1 or 0 depending on the fact that x R y or not, i.e. by its own characteristic function. This leads to represent a non deterministic algorithm by a decidable relation, i.e. a relation whose characteristic function is computable.

Partial characteristic functions

An other possibility is to represent the set R x by an algorithm expressing its partial characteristic function, i.e. by the function that takes the value 1 at y if y is an element of R x , but is not defined at y otherwise.

Using this representation of sets leads to represent the relation R by a function f that maps x to the partial function that maps y to the value 1 if x R y and that is not defined at y otherwise. Using again the fact that a function taking values in a functional space is equivalent to a function of several arguments, the relation R can also be represented as a binary function that maps (x, y) to 1 if x R y and that is not defined at (x, y) otherwise, i.e. by its own partial characteristic function. This leads to represent a non deterministic algorithm by a semi-decidable relation, i.e. a relation whose partial characteristic function is computable.

Enumeration functions

A third possibility is to represent the set R x by an algorithm expressing a total function whose image is this set. The elements of the domain Ω of this function are called indices. When this set is finite or countable, by using a numbering of its the elements, we can restrict, without loss of generality, to the case where it is the set of natural numbers. To avoid to distinguish a special case for the empty set, we shall consider that this function may fail, i.e. take a special value that is not taken into account in its image.

Using this representation of sets leads to represent the relation R by a function f that maps x to a function f x such that x R y if and only if there exists an index i such that y = f x (i). Without loss of generality, we can assume that all the functions f x share the same set of indices and using again the fact that a function taking values in a functional space is equivalent to a function of several arguments, the relation R can also be represented by a binary function f such that x R y if and only if there exists an index i such that y = f (x, i).

This leads to represent non deterministic algorithms by effectively enumerable relations, i.e. relations R such that there exists exists a set Ω and a computable function f from A × Ω to B such that for all x and y, x R y if and only if there exists an i such that y = f (x, i).

Relating these notions

These various notions are related: classical results show that a decidable relation is semi-decidable and that a relation is semi-decidable if and only if it is effectively enumerable.

Indeed, if a relation R is decidable, then by composing its characteristic function with a function that maps 1 to 1 and is not defined at 0, we obtain its partial characteristic function, that is therefore computable.

If a relation R is semi-decidable, then there exists a computable function f that takes the value 1 at (x, y) if and only if x R y. Then there exists a computable function g such that g(x, y, i) takes the value 1 if the i first steps of the computation of the value of f at (x, y) give the result 1 and takes the value 0 otherwise. Let h be the computable function mapping (x, (y, i)) to y if g(x, y, i) = 1 and an exceptional value otherwise. We have x R y if and only if there exists a j such that y = h(x, j). Thus the relation R is effectively enumerable.

Remark that we can avoid the use of an exceptional value, if all the sets R x are non empty. In this case, we first show the existence of a computable function d mapping x to an element of R x and we define the binary function h as the function that maps (x, (y, i)) to y if g(x, y, i) = 1 and to d(x) otherwise.

Conversely, if a relation R is effectively enumerable, there exists a function f such that x R y if and only if there exits an index i such that y = f (x, i). By numbering the elements of the set Ω, we can restrict, without loss of generality, to the case where this set is the set of natural numbers. To determine if two elements x and y are in relation or not, it is sufficient to compute, in a sequential way, the values f (x, 0), f (x, 1), f (x, 2), ... and to return the value 1 if the result of one of these computations is equal to y. The partial characteristic function of R is therefore computable.

Remark that the decidability of equality over the natural numbers is used in this proof in an essential way.

Finally, we can prove that a relation can be defined in a non deterministic classical model (Turing machine, rewrite system, etc.) if and only if it is semidecidable, of equivalently effectively enumerable. Thus, the notion that captures non deterministic algorithms is not that of a decidable relation, but that that of a semi-decidable relation or, equivalently, that of an effectively enumerable relation.

Index, elementary event, possible world, universe and hidden variable

This notion of an index, used in the definition of the notion of an effectively enumerable relation, is reminiscent of several other notions, used in various domains, that are all concerned, in a way or an other, with the notion of potentiality. First, it is reminiscent of the notion of an elementary event in Kolmogorov's notion of a probability space. Given an element x, the function that maps an index i to the value f (x, i) could therefore be called a random variable, even if the set of indices is not necessarily equipped with a probability distribution. Then, it is reminiscent of the notion of a possible world that is used in Kripke's models of modal logics, and that of universe in Everett's interpretation of quantum physics, according to which all the possible results of an experiment, predicted by the theory, indeed happen, but each in a different universe. The fact that f (x, i) = y can therefore be read as the fact that, in the world i, the algorithm f maps x to y. Finally, it is reminiscent of the notion of a hidden variable, because non-determinism is interpreted as the dependence to an ancillary variable.

Computation over the real numbers

The links between computability theory and analysis are as old as computability theory itself, as Turing already defined the notion of a computable real number.

Here, we are interested in defining a notion of a computable function from the real numbers to the real numbers.

Computability over the real numbers

A possible definition, in the style Grzegorczyk, Lacombe, and Weihrauch is that a function f from an interval I of R to R is computable if there exists a computable function

F from Q × (Q + \ {0}) to Q × (Q + \ {0} ∪ {+∞}) such that for all x in I, q and r in Q, η and ε in Q + \ {0} (F (q, η) = (r, ε) and |x -q| ≤ η) ⇒ |f (x) -r| ≤ ε
Put in another way, if (r, ε) = F (q, η) and q is an approximation of x up to η, then r is an approximation of f (x) up to ε.

We must however be able to know the value of f (x) with an arbitrary accuracy, which leads to put another condition: if x is a real number and (q n ) n , (η n ) n , (r n ) n and (ε n ) n are sequences such that for all n, (r n , ε n ) = F (q n , η n ) and |x -q n | ≤ η n and the sequence η goes to 0 at infinity, then the sequence ε also goes to 0 at infinity. This definition is equivalent to that of Weihrauch, and when I is a compact interval [a, b], it is also equivalent to the definition of Grzegorczyk and Lacombe, as, for instance, presented by Pour El and Richards, where a function f from an interval

I of R to R is computable if there exists a computable function e from Q + \ {0} to Q + \ {0} and a computable function F from Q × (Q + \ {0}) to Q such that for all x in I, q in Q and ε in Q + \ {0} |x -q| ≤ e(ε) ⇒ |f (x) -F (q, ε)| ≤ ε
and where the function e mapping the desired accuracy ε on the image of f to the requested accuracy on its argument, has to be known a priori and uniform on the interval I. But these two definitions differ when the interval I is not compact.

Remark that all computable functions are continuous by definition. Hence the characteristic function of equality and of the set R + \{0} are not computable.

We leave out of this discussion several other important notions of computability over the real numbers. The first is the notion proposed by Blum, Cucker, Shub, and Smale where equality is a decidable relation. Another is the non extensional notion of computability, where the value of a function at a real number x may depend not only on this real number x, but also on its presentation, for instance on the Cauchy sequence used to define it. Despite their intrinsic interest, these notions do not seem to be relevant to the question of the algorithmic description of the laws of nature discussed here.

Remark that, when extending the notion of a computable function to the real numbers, we do not extended the execution modalities of algorithms. We are still using the same execution modalities -Turing machines, rewrite systems, etc. Simply, these computation mechanisms are now used with rational numbers approximating the real numbers. The thesis that real computable functions defined in such a way are sufficient to describe the laws of nature, or that that an analog machine cannot compute a function that would exceed this notion of computability, implies that all that an analog machine can compute can also be computed by a digital machine, or that a physical process cannot access in a finite time to the infinite amount of information contained in a real number. This can be reformulated in more physical terms as the fact that a physical process cannot be used to distinguish, in a finite time, the difference between two close enough magnitudes.

The notion of a computable partial function over the real numbers

This definition of computability over the real numbers generalizes easily to a notion of a computable partial function over the real numbers. It suffices to modify the second condition according to which the sequence ε must go to 0 at infinity. Instead, we require that, for each real number x, either for all sequences (q n ) n , (η n ) n , (r n ) n , (ε n ) n such that for all n, (r n , ε n ) = F (q n , η n ) and |x-q n | ≤ η n and the sequence η goes to 0 at infinity, the sequence ε goes to 0 at infinity, or for all sequences (q n ) n , (η n ) n , (r n ) n , (ε n ) n such that for all n, (r n , ε n ) = F (q n , η n ) and |x -q n | ≤ η n and the sequence η goes to 0 at infinity, the sequence ε is constant and equal to +∞. In this second case, the attempt to obtain any approximation of f (x) by providing more and more accurate approximations of x leads to a computation that does not terminate: the function f is not defined at x.

We can prove this way that the partial characteristic function of the set R + \ {0} is computable. Indeed, it is computed by the function F that maps q and η to the ordered pair (1, η) if q -η > 0 and to the ordered pair (1, +∞) otherwise. Indeed, if x is a strictly positive real, (q n ) n and (η n ) n two sequences such that for all n, |x -q n | ≤ η n and η goes to 0 at infinity, then the sequence (q n -η n ) n goes to x at infinity and thus it is strictly positive beyond a certain point. The sequence (F (q n , η n )) n is therefore equal to (1, η n ) n beyond a certain point and f (x) = 1. If x is negative or null, in contrast, we have for all n, q n -η n ≤ x ≤ 0, thus the sequence (q n -η n ) n is always negative or null and the sequence (F (q n , η n )) n is always equal to (1, +∞): the function f is not defined at x. We can, this way, express formally what is often stated informally: if x is a strictly positive real, then there is an effective way to prove it.

We can prove that the domain of a partial computable function is always an open set. Indeed, if f is a function and x a real number such that f (x) is defined, then there exist sequences (q n ) n , (η n ) n such that for all n, |x -q n | ≤ η n and the sequence η goes to 0 at infinity. Let (r n ) n and (ε n ) n be sequences such that for all n, (r n , ε n ) = F (q n , 2η n ). The function f is defined at x, the sequence (2η n ) n verifies the condition that for all n, |x -q n | ≤ 2η n and it goes to 0 at infinity. Thus, the sequence ε goes to 0 at infinity and there exists a natural number m such that ε m is different from +∞. As |x -q m | ≤ η m , the interval [q m -2η m , q m + 2η m ] is a neighborhood of x and for all y in this interval, |y -q m | ≤ 2η m , thus, there exist two sequences (q ′ n ) n and (η ′ n ) n such that q ′ 0 = q m and η ′ 0 = 2η m and for all n, |y -q ′ n | ≤ η ′ n and such that the sequence η ′ goes to 0 at infinity. Let (r ′ n ) n and (ε ′ n ) n be the sequences such that for all n, (r

′ n , ε ′ n ) = F (q ′ n , η ′ n ).
We have ε ′ 0 = ε m thus the sequence ε ′ is not constant and equal to +∞ and f is defined at y.

Thus, if we call semi-decidable a set whose partial characteristic function is computable, then all semi-decidable sets of real numbers are open.

Non deterministic algorithms over the real numbers

We have extended above the notion of computability of functions operating on natural numbers to relations between natural numbers. We can try to extend, in a similar way, the notion of computability of functions operating on real numbers to relations between real numbers. To guide us in the choice of an extension of the notion of computability of functions operating on real numbers to relations between real numbers, we shall require, as a minimal condition, that the proposed definition extends the notion of a computable function, that is that a functions operating on real numbers is computable as a function if and only if it is computable as a relation.

Representing the set R x by its characteristic function

Representing the set R x by its characteristic function leads to represent a relation R by its characteristic function as well.

As computable functions over the real numbers are always continuous, the relations that have a computable characteristic functions are only the empty and the full relation. Thus, this idea leads to dead end.

Representing the set R x by its partial characteristic function

Representing the set R x by its partial characteristic function leads to represent the relation R by its partial characteristic function, as well. We can, for instance, represent the relation R such that x R y if x < y < x+1, whose partial characteristic function is χ R + \{0} ((x + 1 -y)(y -x)).

In contrast, the partial characteristic function of the relation R defined by x R y if y = x or y = x + 1 is not computable, because its graph is not an open set. In the same way, the partial characteristic function of the functional relation R defined by x R y if y = x is not computable. Thus, if this solution allows more relations to be represented than the previous ones, it is far from being sufficient as the identity, that is computable as a function, would not be computable as a relation.

Representing the set R x by an enumerating function

As the characteristic function of equality over the real numbers is not computable, the argument developed in the case of natural numbers that effectively enumerable relations are semi-decidable does not generalize to the case of real numbers: there are more effectively enumerable relations than semi-decidable ones.

Representing the set R x by an enumerating function leads to represent the relation R by a function f such that x R y if and only if there exists an index i such that y = f (x, i). In this definition, the set Ω may be arbitrary. It can, for instance, be the set of natural numbers, the real line, an interval of the set of natural numbers, an interval of the real line, etc.

This solution, unlike the previous ones, gives a large set of representable relations, for instance the relation R defined by x R y if y = x or y = x + 1 is representable, taking the set of natural numbers for the set Ω and, for f , the function defined by f (x, 0) = x and f (x, i) = x + 1 if i ≥ 1. This function is computed by the function F where F (q, η, 0) = (q, η) and F (q, η, i) = (q +1, η) if i ≥ 1. The functional relation R defined by x R y if y = x can also be represented by taking the set of natural numbers for Ω and, for f , the function defined by f (x, i) = x, that is computed by the function F defined by F (q, η, i) = (q, η).

More generally, all computable functions g mapping real numbers to real numbers can be represented as relations, as it suffices to define the function f (x, i) as g(x), ignoring the index i. Conversely, a functional relation that can be represented is computable as a function, because this function g associates to x the value f (x, i 0 ) where i 0 is an arbitrary index.

The conclusion of this section is this that among the three sets of relations we have defined, the last one, the set of effectively enumerable relations is the largest and it is the only one that contains all computable functions and the relation that maps the real number x to the real numbers x and x + 1, that intuitively seems to be computable. It is the only one that can pretend to be used as a description language for the laws of physics.

Probabilities

This notion of a non deterministic algorithm can be extended to a notion of a probabilistic algorithm on real numbers.

Trying to represent a non deterministic algorithm as a computable function f mapping an ordered pair (x, y) to the values 1 of 0 depending on the fact that y could be the result of the algorithm at x or not, lead to failure because the function f being continuous, only the empty and full relations could be represented.

We can try, instead, to map the ordered pair (x, y) not to 1 or 0 but to a real number indicating the propension of y to be the result of the algorithm at x. Depending on the cases, this propension can be a probability, a density of probability, a number whose square is such a probability or a density of probability, etc.

A probabilistic algorithm, that takes an element of a set A as argument and returns an element of a set B if it terminates, defines a function that maps every element of A to a probability distribution over the set B, that is a function that maps a pair formed with an element x of A and a subset Y of B to the probability that the value of this algorithm at x is in Y .

Discussing the computability of this function is delicate, because, we have the problem of representing the set Y . We can nevertheless focus on some particular cases. If the set Y is always an interval, we can replace this function by a repartition function, that is a function that maps x and y to the probability that the value of the algorithm at x is less than y. If this repartition function is moreover differentiable, we can replace it by its derivative, that this the function that maps x and y to the density of probability that the value of the algorithm at x is y. Another particular case is when the algorithm can take only a finite or countable number of values for each x. It is then possible to define this probability distribution by a function that maps x and y to the probability that the value of the algorithm at x is exactly y.

If we require this function to be computable, it must be continuous. In the first case, there are many random variables whose repartition function or whose density function is continuous. In the second, the fact that the function that maps x and y to the probability that the value of the algorithm at x is y is continuous implies that if it is different from zero at a point y, it must be minored by a strictly positive value on a neighborhood of y, which is contradictory. Thus, it is not possible to represent this way a probabilistic algorithm that takes two different values at 0 with probabilities 1/2.

Going from non deterministic algorithms to probabilistic ones thus gives to this method based on characteristic functions a wider spectrum, but not a spectrum wide enough to describe algorithms with a discrete probability distribution. The same argument eliminates also the attempt to base a definition on partial characteristic functions. A partial propension function defined at a point y is defined on a neighborhood of this point and the same problem occurs as in the discrete case.

In contrast, the representation of relations based on the notion of an effective enumeration generalizes easily to probabilistic algorithms with discrete probability distributions. To each pair (x, i) we associate a pair (y, p). We can, for instance, represent the algorithm that maps the real number x to x and x + 1 with probabilities 1/2 by taking for the set of indices Ω = {0, 1, 2, 3} and by defining the function f by f (x, 0) = f (x, 1) = (x, 1/4) and f (x, 2) = f (x, 3) = (x + 1, 1/4). The probability that the value of the algorithm at x is y is the sum of the p i for the i such that y i = y. In this case, the probability that the result of the algorithm at x is x is 1/2, that that it is x + 1 is 1/2 as well, and that that it is another value is 0. This function that takes its value in a Cartesian product can be decomposed into two functions h and p such that h(x, 0) = h(x, 1) = x, h(x, 2) = h(x, 3) = x + 1 and p(x, 0) = p(x, 1) = p(x, 2) = p(x, 3) = 1/4. This amounts to define a non deterministic algorithm with the function h and to equip independently the set Ω with a probability distribution. This solution also permits to represent the algorithm that maps the real number x to x and 2x with probabilities 1/2 and the real number 0 to 0 with probability 1, defining the function f by f (x, 0) = f (x, 1) = (x, 1/4) and f (x, 2) = f (x, 3) = (2x, 1/4). This would not be allowed with a solution that would represent this algorithm as a function mapping each x to the set of possible results, each with its probability, as it would be discontinuous at 0. The conclusion of this section is thus that, in the case of probabilistic algorithms, like in the case of non deterministic algorithms, the definition based on effective enumeration is that that permits to represent the largest set of relations. In particular, it is the only one that permits to represent the relation that maps the real number x to x and x + 1, with probabilities 1/2, that intuitively seems to be computable.

5 What is a computable description of a non deterministic theory in physics?

This discussion on the nature of non deterministic algorithms on real numbers permits to describe more precisely what it could mean for a theory in physics to have an algorithmic expression or not, when this theory is non deterministic and represents physical magnitudes with real numbers.

To do so, let us imagine an experiment in which one prepares a system by choosing a magnitude x, let the system evolve for a fixed time T , and measures a magnitude y. Our two hypotheses on the theory we try to describe are that it represents magnitudes x and y by real numbers and that for each value x, it does not prescribe a unique result y, but a set of possible results, possibly equipped with probabilities. What would be an algorithm that would describe the results prescribed by the theory, for such an experiment?

As we have seen, we should expect such an algorithm to indicate neither if y is a possible result for the experiment initiated with the value x, nor the probability for this result to be y.

In contrast, the theory should describe this experiment by a function that to each value of x associates a random variable f x that is itself a function that maps each element of a set of indices Ω to a value y. We can call f the function that maps x and i to the value f x (i). It is this function, that an algorithmic description of the theory must represent by an algorithm.

The existence of such an algorithm is a strong constraint on the theory. In all the cases where the experiment is deterministic, it boils down exactly to the deterministic physical Church-Turing thesis: the fact that the link between x and y is a computable function. It is therefore neither more constraining nor less constraining for a theory to be algorithmic in the non deterministic case than in the deterministic case.

We shall not answer here to the question of whether such or such theory in physics is algorithmic or not. Our only purpose in this paper was to try to understand how this question could be stated.

Acknowledgments

I want to thank Pablo Arrighi and Jean-Baptiste Joinet for many remarks on a previous draft of this paper, Olivier Bournez, Assia Mahboubi and Nathalie Revol for helping me to find my way in the complex domain of real computation and Giuseppe Longo and Thierry Paul for always stimulating discussions.


Gilles Dowek
email: gilles.dowek@inria.fr

The physical Church thesis as an explanation of the Galileo thesis

The Galileo thesis is a consequence of the physical Church thesis.

1 The Galileo thesis

The effectiveness of mathematics in natural sciences

.

.

Insufficient explanations

Several explanations of this unreasonable effectiveness of mathematics in the natural sciences have been attempted:

1. God is a mathematician and He wrote the vast book in the language of mathematics.

2. The mathematical concepts are built by abstracting from empirical objects.

3. Scientists select only those phenomena that can be mathematically described.

4. Scientists approximate the phenomena they study, until they can be mathematically described.

5. Our brain is part of nature, hence our concepts are natural objects, thus they are of the same kind as the objects they describe.

Each of these explanation is insufficient. The first reduces the problem to that of why God is a mathematician, which seems even harder to explain. The second is partial: if some mathematical concepts are built by abstracting from natural objects, the concept of ellipse, for instance, has not been built by abstracting from the trajectory of the planets, as it has been introduced some two thousands years before. The third leaves intact the problem of why so many -if not all -phenomena can be described in the language of mathematics. The fourth leaves intact the problem of why phenomena can be approximately -if not accurately -described in the language of mathematics. The fifth presupposes that we understand better a phenomenon from the inside than from the outside, which is not the case in general.

Perhaps several kinds of effectiveness

The effectiveness of mathematics in the natural sciences may be of different kinds. And instead of looking for a global explanation of all kinds of effectiveness, we should perhaps look for more local explanations.

For instance, the atomic masses of the chemical elements have a regular structure, as they are the integer multiples of some unit. When this regularity was discovered, there were three exceptions to this rule, because no elements of atomic mass 45, 68, and 70 were known. Yet, as some chemists trusted the structure of the natural numbers better that their observations, they predicted the existence of these three elements, that were later discovered. This is a striking example of the effectiveness of the structure of natural numbers in chemistry.

But, this striking regularity is easily explained by the fact that the mass of the atoms is mostly due to the mass of protons and neutrons that constitute their nucleus and that each nucleus contains an whole number of such particles.

Yet, this explanation sheds light on the effectiveness of the structure of natural numbers to describe the atomic masses of the chemical elements, but it does not shed light on the effectiveness of mathematics in the natural sciences in general, for instance, it does not shed light on the effectiveness of the quadratic functions to describe the free fall.

Thus, in this note, we shall focus on a particular instance of the general thesis that mathematics are effective in in the natural sciences: the fact that physically realized relations can be expressed by a proposition of the language of mathematics.

Physically realized relations

Let us imagine an experiment where one prepares a physical system by choosing some parameters and measures others. Let us call a = ⟨a 1 , ..., a n ⟩ the value of the chosen parameters and b = ⟨b 1 , ..., b p ⟩ that of the measured ones. This experiment, i.e. this physical system together with the protocol defining the chosen parameters and the measured ones, defines a relation: a R b if b is a possible result for the measures when the chosen parameters are a. We say that these relations are physically realized.

For instance, if one applies an electrical tension U to a conductor of resistance R and measures the current I passing through this conductor, then a = ⟨U, R⟩ and b = I and the realized relation is that relating ⟨U, R⟩ and I when U = RI. The relation between ⟨U, R⟩ and I can thus be expressed by a proposition of the language of mathematics. In the same way, the relation between the time and the position of a body freely falling in vacuum can be described by the proposition of the language of mathematics x = 1 2 gt 2 . Among the uncountable number of relations between numbers, only a countable number can be defined by a proposition of the language of mathematics, such as U = RI or x = 1 2 gt 2 and all the physically realized relations seem to be in this small set.

As Galileo stressed the role of the language of mathematics, we can call the Galileo thesis the statement that all physically realized relation can be expressed by a proposition of the language of mathematics.

Instead of attempting to explain the general thesis that mathematics are effective in the natural sciences, we shall restrict our investigation to attempt to explain this unreasonable effectiveness of the propositions of the language of mathematics to express physically realized relations.

The physical Church thesis 2.1 The physical Church thesis

The physical Church thesis expresses that if we are able to construct a computing machine, i.e. a physical system together with an interaction protocol defining a way to communicate some information to the system by choosing some parameters a and to extract some information from the system, by measuring others b, then the relation between a and b is a computable relation.

In the formulation of this thesis nothing is said about the nature of the machine. It may be electronic or not, digital or not, deterministic or not, inanimate or not, etc. This notion of machine encompasses all the physical systems, equipped with an interaction protocol. Thus, it is co-extensive with the notion of experiment, we have defined above.

Therefore, the physical Church thesis can be stated as the fact that physically realized relations are computable.

The physical Church thesis implies the Galileo thesis

Once we have identified the similarities between the Galileo thesis and the physical Church thesis by stating them as theses about the set of physically realized relations, we may remark that the physical Church thesis implies the Galileo thesis.

Indeed, as any program expressing a computable relation is a mathematical expression, all computable relations can be defined by a proposition of the language of mathematics. In fact, computable relations can even be expressed by a proposition in a very small fragment of mathematics: the language of Peano arithmetic.

Thus, if the physical Church thesis holds, then all physically realized relations are computable, hence they can be expressed by a proposition of the language of mathematics, i.e. the Galileo thesis holds.

Gandy's proof of the physical Church thesis

This explanation of the Galileo thesis reduces the problem of explaining the Galileo thesis to that of explaining why the physical Church thesis holds. But, such an explanation has already been attempted. For instance, Robin Gandy [START_REF] Gandy | Church's thesis and principles for mechanism[END_REF] has shown that the physical Church thesis is a consequence of three assumptions about nature:

• the homogeneity of space and time,

• the boundedness of the velocity of propagation of information,

• the boundedness of the density of information.

The boundedness of the density of information can be expressed, in physical terms, as the fact that a physical system of finite diameter has a finite state space and the boundedness of the velocity of propagation of information can be expressed as the fact that the state of a system in one place can only affect the state of a system in another after a delay, proportional to their distance.

Then, to prove the physical Church thesis from these assumptions, we just need to partition the space into an infinite number of identical cells of finite size. Because information has a bounded density, the state of each cell is an element of a finite set. Because of the homogeneity of space, this state space is the same for all cells. At the origin of time all the cells except a finite number are in a particular quiescent state. Like space, time can be discretized. Because the velocity of propagation of information is bounded, the state of a cell at a given time step is function of the state of a finite number of neighbors cells at the previous time step. This function of a finite number of variables varying in a finite set is obviously computable. Hence the state of each cell at each time step can be computed from the initial state.

Gandy's hypotheses can be, and have been [START_REF] Copeland | Physical computation: how general are Gandy's principles for mechanisms[END_REF], criticized. For instance, it is well-known that in Newtonian mechanics, gravity is instantaneous and thus information can be propagated with an infinite velocity. Also, the position of a body between two points A and B -the distance AB taken as a unit -can be any real number between 0 and 1 and thus can contain an infinite quantity of information: any infinite sequence in a finite alphabet can be encoded as the digits of such a number, in an appropriate base. Yet, Gandy's hypotheses have not be refuted experimentally -for instance by the construction of an instantaneous computer network or by the construction of a hard drive with an infinite capacity.

More importantly, even if Gandy's hypotheses must be refined, Gandy's proof shows that the physical Church thesis is a consequence of some hypotheses about nature, that do not refer to notions such that those of language or computability. And, the Galileo thesis also is a consequence of these hypotheses.

If these hypotheses are true, the fact that natural phenomena can be described by propositions of the language of mathematics is a consequence of objective properties of nature, such as the fact that a system of finite size has a finite state space.

Eliminating the physical Church thesis

We have seen that • Gandy's hypotheses imply the physical Church thesis,

• and the physical Church thesis implies the Galileo thesis. Thus, we can deduce that Gandy's hypotheses imply the Galileo thesis and attempt to prove this directly.

Yet, from a historical point of view, it is important to notice the role of computability theory and the physical Church thesis in connecting Gandy's hypotheses to the Galileo thesis.

An algorithmic description of the laws of nature

A side effect of this explanation of the Galileo thesis is that the laws of nature can be described not only in the language of mathematics, but also in a language designed to express algorithms: a programming language.

Instead of expressing the law of free fall in vacuum by the proposition x = 1 2 gt 2 , we could express it by the algorithm fun t -> g * t * t / 2, leading to a second Galilean revolution in the language of natural sciences. In particular, as long as differential equations have computable solutions [START_REF] Pour-El | Computability in analysis and physics[END_REF][START_REF] Bournez | A survey on continuous time computations[END_REF][START_REF] Collins | Effective computability of solutions of ordinary differential equations -The thousand monkeys approach[END_REF][START_REF] Collins | Effective computability of solutions of differential inclusions -The ten thousand monkeys approach[END_REF] the language of differential equations can be seen as a language to define algorithms: a programming language. Yet, this algorithmic description of the laws of nature may have a broader scope than the description of the laws of nature with differential equations. For instance, the transformation of a messenger RNA string to a protein is easily expressed by an algorithm, while it cannot be expressed by a differential equation.

A property of nature or of the theory?

An objection to Galileo's formulation of the Galileo thesis "The Universe [...] is [...] a book [...] written in the language of mathematics" is that it confuses nature with our description of nature: nature itself is neither a book written in the language of mathematics, nor a book written in another language: it is not a book at all. Only our description of nature is a book. Thus, we could imagine that our description of nature is written in the language of mathematics because we have chosen to write it this way, nature having nothing to do with our decision [START_REF] Ziegler | Physically-relativized Church-Turing hypotheses: Physical foundations of computing and complexity theory of computational physics[END_REF]. Rather than a property of nature itself, this set of relations seems to be a property of a particular theory chosen to describe nature.

Yet, the Universe and our description of the Universe are not independent: our description must have an experimental adequation of some sort with the Universe.

We show, in this section, that in the construction of a theory, the scientists have very little freedom when "choosing" this set of realized relations.

Let us consider first a particular case where all the realized relations are functional. Then, we show that if two theories differ on the set of realized relations, one of the theories can be, at least in principle, experimentally refuted. Indeed, if the set of the realized relations differ, then there exists a relation R that is realized according to one theory T but not according to the other theory T ′ . Let E be the experiment realizing R according to the theory T and R ′ be the relation realized by this experiment according to the theory T ′ . As R is not realized according to T ′ , the relations R and R ′ are different. Thus, there exists a, b and b ′ , b ̸ = b ′ , such that a R b and a R ′ b ′ . Then, if we perform the experiment E with the parameters a, the measures will either give the result b and refute T ′ or b ′ and refute T or an other value and refute both theories.

When the realized relations need not be functional, we have a weaker result: either a theory can be refuted, or it predicts, among others, a result that never occurs, whatever the number of times the experiment is repeated is. Again, if the set of the realized relations differ, then there exists an experiment that realizes a relation R according to one theory and a relation R ′ , R ′ ̸ = R, according to the other. Thus, there exists an a, such that the set R a of the b such that a R b and the set R ′ a of the b such of b such that a R ′ b are different. As these sets are different, they are not both equal to R a ∩ R ′ a . Then, if we repeat the experiment with the parameters a, either the measures give one result that is not in R a ∩ R ′ a and at least one of the theories is refuted, or the measures always give results in R a ∩ R ′ a and at least one theory predicts a result that never occurs.

set in the natural sciences. Several other theses can be stated as a property of this set.

• The negation of the physical Church thesis, i.e. the existence of hypercomputations, is, of course, also a thesis about this set of relations.

A hyper-computation is an experiment that is supposed to realize a relation that is not computable. It has be argued for instance that hypercomputations exist because the quantum adiabatic theorem [START_REF] Kieu | Quantum algorithm for Hilbert's tenth problem[END_REF] or the properties of time-space in the neighborhood of a black hole [START_REF] Etesi | Non-Turing computations via Malament-Hogarth spacetimes[END_REF][START_REF] Hogarth | Deciding arithmetic using SAD computers[END_REF] allow to perform an infinite number of computation steps in a finite time. Even in classical Newtonian physics, such hyper-computations may also exist if we accept to encode a non computable set in the initial state of the system, using either the fact that the system has an infinite size [START_REF] Beggs | Computation via experiments with kinematic systems[END_REF], or that it contains arbitrarily small pieces [START_REF] Beggs | Can Newtonian systems, bounded in space, time, mass and energy compute all functions[END_REF], or that the position of some point is described with a real number [START_REF] Beggs | Experimental computation of real numbers by Newtonian machines[END_REF].

More interesting than the refutation of the physical Church thesis is a positive characterization of the set of the relations physically realized under these hypotheses.

• Determinism and non-determinism can also be stated as theses about the set of the physically realized relations. It is too naive to state that determinism is the thesis that all physically realized relations are functional, because the functionality of these relations depends on the chosen protocol. For instance, if one applies a given electrical tension U to a conductor of resistance R and measures the current I passing through this conductor, then the realized relation contains all the pairs ⟨⟨U, R⟩, I⟩ such that U = RI and this relation is functional. But, if one applies an electrical tension to a conductor of resistance R and measures both the electrical tension and the current passing through this conductor, then the realized relation contains all the pairs ⟨R, ⟨U, I⟩⟩ such that U = RI and, unlike the previous one, this relation is not functional, although no non-determinism occurs here. To define determinism, we have to take time into account and restrict to protocols where the chosen parameters are measurable parameters of the system at a given time t and the measured one are the parameters of the system at a later time t ′ . Then, determinism can be stated as the fact that for each physical system, there exists such a protocol, for which all realized relations are functional. Non-determinism, in contrast, is the thesis that there exist systems such that for all such protocols, there exists a non functional realized relation.

• The thesis that all physical phenomena are continuous or differentiable can also be stated as properties of the set of the physically realized relations.

In very general terms, when a set A is a subset of a set B, then the thesis that the physically realized relations are elements of the set A and that they are elements of the set B are related: the first implies the second. The fact that the physical Church thesis implies the Galileo thesis is just a particular case of this.

For some sets A of relations, there exists a language L such that the relations of the set A are those that can be expressed in the language L. For instance, the polynomial relations are those that can be expressed in the language of polynomials, the computable relations are those that can be expressed in a programming language, etc.

In this case, the thesis that all the physically realized relations are elements of the set A can be stated as the fact that all realized relations can be expressed in the language L or, in a more poetic way, as the fact that the language L is (unreasonably) effective in the natural sciences. Such a should be understood as a thesis about nature, not about the language.

Towards a logical analysis of natural phenomenaThe formulation of the Galileo thesis and the physical Church thesis as properties of the set of physically realized relations points out the importance of this

Acknowledgments

To Pablo Arrighi, Olivier Bournez, José Félix Costa, Nachum Dershowitz, Jean-Baptiste Joinet, Giuseppe Longo and Thierry Paul.