Ugo Dal
email: dallago@cs.unibo.it

Sara Zuppiroli
email: zuppirol@cs.unibo.it

Probabilistic Recursion Theory and Implicit Computational Complexity ⋆

We show that probabilistic computable functions, i.e., those functions outputting distributions and computed by probabilistic Turing machines, can be characterized by a natural generalization of Church and Kleene's partial recursive functions. The obtained algebra, following Leivant, can be restricted so as to capture the notion of polytime sampleable distributions, a key concept in average-case complexity and cryptography.

Introduction

Models of computation as introduced one after the other in the first half of the last century were all designed around the assumption that determinacy is one of the key properties to be modeled: given an algorithm and an input to it, the sequence of computation steps leading to the final result is uniquely determined by the way an algorithm describes the state evolution. The great majority of the introduced models are equivalent, in that the classes of functions (on, say, natural numbers) they are able to compute are the same.

The second half of the 20th century has seen the assumption above relaxed in many different ways. Nondeterminism, as an example, has been investigated as a way to abstract the behavior of certain classes of algorithms, this way facilitating their study without necessarily changing their expressive power: think about how NFAs [START_REF] Rabin | Finite automata and their decision problems[END_REF] make the task of proving closure properties of regular languages easier.

A relatively recent step in this direction consists in allowing algorithms' internal state to evolve probabilistically: the next state is not functionally determined by the current one, but is obtained from it by performing a process having possibly many outcomes, each with a certain probability. Again, probabilistically evolving computation can be a way to abstract over determinism, but also a way to model situations in which algorithms have access to a source of true randomness.

Probabilistic models are nowadays more and more pervasive. Not only are they a formidable tool when dealing with uncertainty and incomplete information, but they sometimes are a necessity rather than an option, like in computational cryptography (where, e.g., secure public key encryption schemes need to be probabilistic [START_REF] Goldwasser | Probabilistic encryption[END_REF]). A nice way to deal computationally with probabilistic models is to allow probabilistic choice as a primitive when designing algorithms, this way switching from usual, deterministic computation to a new paradigm, called probabilistic computation.

But what does the presence of probabilistic choice give us in terms of expressivity? Are we strictly more expressive than usual, deterministic, computation? And how about efficiency: is it that probabilistic choice permits to solve computational problems more efficiently? These questions have been among the most central in the theory of computation, and in particular in computational complexity, in the last forty years (see below for more details about related work). Roughly, while probability has been proved not to offer any advantage in the absence of resource constraints, it is not known whether probabilistic classes such as BPP or ZPP are different from P.

This work goes in a somehow different direction: we want to study probabilistic computation without necessarily reducing or comparing it to deterministic computation. The central assumption here is the following: a probabilistic algorithm computes what we call a probabilistic function, i.e. a function from a discrete set (e.g. natural numbers or binary strings) to distributions over the same set. What we want to do is to study the set of those probabilistic functions which can be computed by algorithms, possibly with resource constraints.

We give some initial results here. First of all, we provide a characterization of computable probabilistic functions by the natural generalization of Kleene's partial recursive functions, where among the initial functions there is now a function corresponding to tossing a fair coin. In the non-trivial proof of completeness for the obtained algebra, Kleene's minimization operator is used in an unusual way, making the usual proof strategy for Kleene's Normal Form Theorem (see, e.g., [START_REF] Soare | Recursively enumerable sets and degrees: a study of computable functions and computably generated sets[END_REF]) useless. We later hint at how to recover the latter by replacing minimization with a more powerful operator. We also mention how probabilistic recursion theory offers characterizations of concepts like the one of a computable distribution and of a computable real number.

The second part of this paper is devoted to applying the aforementioned recursion-theoretical framework to polynomial-time computation. We do that by following Bellantoni and Cook's and Leivant's works [START_REF] Bellantoni | A new recursion-theoretic characterization of the polytime functions[END_REF][START_REF] Leivant | Ramified recurrence and computational complexity I: Word recurrence and poly-time[END_REF], in which polynomialtime deterministic computation is characterized by a restricted form of recursion, called predicative or ramified recursion. Endowing Leivant's ramified recurrence with a random base function, in particular, is shown to provide a characterization of polynomial-time computable distributions, a key notion in average-case complexity [START_REF] Bogdanov | Average-case complexity[END_REF].

Related Work. This work is rooted in the classic theory of computation, and in particular in the definition of partial computable functions as introduced by Church and later studied by Kleene [START_REF] Kleene | General recursive functions of natural numbers[END_REF]. Starting from the early fifties, various forms of automata in which probabilistic choice is available have been considered (e.g. [START_REF] Rabin | Probabilistic automata[END_REF]). The inception of probabilistic choice into an universal model of computation, namely Turing machines, is due to Santos [START_REF] Santos | Probabilistic Turing machines and computability[END_REF][START_REF] Santos | Computability by probabilistic turing machines[END_REF], but is (essentially) already there in an earlier work by De Leeuw and others [START_REF] De Leeuw | Computability by probabilistic machines[END_REF]. Some years later, Gill [START_REF] Gill | Computational complexity of probabilistic Turing machines[END_REF] considered probabilistic Turing machines with bounded complexity: his work has been the starting point of a florid research about the interplay between computational complexity and randomness. Among the many side effects of this research one can of course mention modern cryptography [START_REF] Katz | Introduction to Modern Cryptography (Chapman & Hall/Crc Cryptography and Network Security Series[END_REF], in which algorithms (e.g. encryption schemes, authentication schemes, and adversaries for them) are almost invariably assumed to work in probabilistic polynomial time.

Implicit computational complexity (ICC), which studies machine-free characterizations of complexity classed based on mathematical logic and programming language theory, is a much younger research area. Its birth is traditionally made to correspond with the beginning of the nineties, when Bellantoni and Cook [START_REF] Bellantoni | A new recursion-theoretic characterization of the polytime functions[END_REF] and Leivant [START_REF] Leivant | Ramified recurrence and computational complexity I: Word recurrence and poly-time[END_REF] independently proposed function algebras precisely characterizing (deterministic) polynomial time computable functions. In the last twenty years, the area has produced many interesting results, and complexity classes spanning from the logarithmic space computable functions to the elementary functions have been characterized by, e.g., function algebras, type systems [START_REF] Leivant | Lambda calculus characterizations of poly-time[END_REF], or fragments of linear logic [START_REF] Girard | Light linear logic[END_REF]. Recently, some investigations on the interplay between implicit complexity and probabilistic computation have started to appear [START_REF] Lago | A higher-order characterization of probabilistic polynomial time[END_REF]. There is however an intrinsic difficulty in giving implicit characterizations of probabilistic classes like BPP or ZPP: the latter are semantic classes defined by imposing a polynomial bound on time, but also appropriate bounds on the probability of error. This makes the task of enumerating machines computing problems in the classes much harder and, ultimately, prevents from deriving implicit characterization of the classes above. Again, our emphasis is different: we do not see probabilistic algorithms as artifacts computing functions of the same kind as the one deterministic algorithms compute, but we see probabilistic algorithms as devices outputing distributions.

Probabilistic Recursion Theory

In this section we provide a characterization of the functions computed by a Probabilistic Turing Machine (PTM) in terms of a function algebra à la Kleene. We first define probabilistic recursive functions, which are the elements of our algebra. Next we define formally the class of probabilistic functions computed by a PTM. Finally, we show the equivalence of the two introduced classes. In the following, R [0,1] is the unit interval.

Since PTMs compute probability distributions, the functions that we consider in our algebra have domain N k and codomain N → R [0,1] (rather than N as in the classic case). The idea is that if f (x) is a function which returns r ∈ R [0,1] on input y ∈ N, then r is the probability of getting y as the output when feeding f with the input x. We note that we could extend our codomain from [START_REF] Bellantoni | A new recursion-theoretic characterization of the polytime functions[END_REF] in order to simplify the presentation.

N → R [0,1] to N k → R [0,1] , however we use N → R [0,

Definition 1 (Pseudodistributions and Probabilistic Functions

). A pseu- dodistribution on N is a function D : N → R [0,1] such that n∈N D(n) ≤ 1. n∈N D(n) is often denoted as D.
Let P N be the set of all pseudodistributions on N. A probabilistic function (PF) is a function from N k to P N , where N k stands for the set of k-tuples in N. We use the expression {n p1 1 , . . . , n pk k } to denote the pseudodistribution D defined as D(n) = ni=n p i . Observe that D = k i=1 p i . When this does not cause ambiguity, the terms distribution and pseudodistribution will be used interchangeably.

Please notice that probabilistic functions are always total functions, but their codomain is a set of distributions which do not necessarily sum to 1, but rather to a real number smaller or equal to 1, this way modeling the probability of divergence. For example, the nowhere-defined partial function Ω : N ⇀ N of classic recursion theory becomes a probabilistic function which returns the empty distributions ∅ on any input. The first step towards defining our function algebra consists in giving a set of functions to start from: Definition 2 (Basic Probabilistic Functions). The basic probabilistic functions (BPFs) are as follows:

• The zero function z : N → P N defined as: z(n)(0) = 1 for every n ∈ N;

• The successor function s : N → P N defined as: s(n)(n + 1) = 1 for every n ∈ N; • The projection function Π n m : N n → P N defined as:

Π n m (k 1 , • • • , k n )(k m ) = 1 for every positive n, m ∈ N such that 1 ≤ m ≤ n;
• The fair coin function r : N → P N that is defined as:

r(x)(y) = 1/2 if y = x 1/2 if y = x + 1
The first three BPFs are the same as the basic functions from classic recursion theory, while rand is the only truly probabilistic BPF. The next step consists in defining how PFs compose. Function composition of course cannot be used here, because when composing two PFs g and f the codomain of g does not match with the domain of f . Indeed g returns a distribution N → R [0,1] while f expects a natural number as input. What we have to do here is the following. Given an input x ∈ N and an output y ∈ N for the composition f • g, we apply the distribution g(x) to any value z ∈ N. This gives a probability g(x)(z) which is then multiplied by the probability that the distribution f (z) associates to the value y ∈ N. If we then consider the sum of the obtained product g(x)(z)•f (z)(y) on all possible z ∈ N we obtain the probability of f •g returning y when fed with x. The sum is due to the fact that two different values, say z 1 , z 2 ∈ N, which provide two different distributions f (z 1 ) and f (z 2 ) must both contribute to the same probability value f (z 1 )(y) + f (z 2 )(y) for a specific y. In other words, we are doing nothing more than lifting f to a function from distributions to distributions, then composing it with g. Formally:

Definition 3 (Composition). We define the composition f • g : N → P N of two functions f : N → P N and g : N → P N as:

((f • g)(x))(y) = z∈N g(x)(z) • f (z)(y).
The previous definition can be generalized to functions taking more than one parameter in the expected way: Definition 4 (Generalized Composition). We define the generalized composition of functions f : N n → P N , g 1 : N k → P N , . . . , g n : N k → P N as the function f ⊙ (g 1 , . . . , g n ) : N k → P N defined as follows:

((f ⊙ (g 1 , . . . , g n ))(x))(y) = z1,...,zn∈N   f (z 1 , . . . , z n )(y) • 1≤i≤n g i (x)(z i )   .
With a slight abuse of notation, we can treat probabilistic functions as ordinary functions when forming expressions. Suppose, as an example, that x ∈ N and that f : N 3 → P N , g : N → P N , h : N → P N . Then the expression f (g(x), x, h(x)) stands for the distribution in P N defined as follows: (f ⊙ (g, id , h))(x), where id = Π 1 1 is the identity PF. The way we have defined probabilistic functions and their composition is reminiscent of, and indeed inspired by, the way one defines the Kleisli category for the Giry monad, starting from the category of partial functions on sets. This categorical way of seeing the problem can help a lot in finding the right definition, but by itself is not adequate to proving the existence of a correspondence with machines like the one we want to give here.

Primitive recursion is defined as in Kleene's algebra, provided one uses composition as previously defined: Definition 5 (Primitive Recursion). Given functions g : N k+2 → P N , and f : N k → P N , the function h : N k+1 → P N defined as h(x, 0) = f (x); h(x, y + 1) = g(x, y, h(x, y));

is said to be defined by primitive recursion from f and g, and is denoted as rec(f, g).

We now turn our attention to the minimization operator which, as in the deterministic case, is needed in order to obtain the full expressive power of (P)TMs. The definition of this operator is in our case delicate and requires some explanation. Recall that, in the classic case, the minimization operator allows from a partial function f : N k+1 ⇀ N, to define another partial function, call it µf , which computes from x ∈ N k the least value of y such that f (x, y) is equal to 0, if such a value exists (and is undefined otherwise). In our case, again, we are concerned with distributions, hence we cannot simply consider the least value on which f returns 0, since functions return 0 with a certain probability. The idea is then to define the minimization µf as a function which, given an input x ∈ N k , returns a distribution associating to each natural y the probability that the result of f (x, y) is 0 and the result of f (x, z) is positive for every z < y. Formally: Definition 6 (Minimization). Given a PF f : N k+1 → P N , we define another PF µf : N k → P N as follows:

µf (x)(y) = f (x, y)(0) • ( z<y ( k>0 f (x, z)(k))).
We are finally able to define the class of functions we are interested in as follows.

Definition 7 (Probabilistic Recursive Functions). The class PR of probabilistic recursive functions is the smallest class of probabilistic functions that contains the BPFs (Definition 2) and is closed under the operation of General Composition (Definition 4), Primitive Recursion (Definition 5) and Minimization (Definition 6).

It is easy to show that PR includes all partial recursive functions, seen as probabilistic functions: first, for every partial function f : N k ⇀ N, define p f : N k → P N by stipulating that p f (x)(y) = 1 whenever y = f (x), and p f (x)(y) = 0 otherwise; then, by an easy induction, p f ∈ PR whenever f is partial recursive.

Example 1. The following are examples of probabilistic recursive functions:

• The identity function id : N → P N , defined as id (x)(x) = 1. For all x, y ∈ N we have that

id (x)(y) = 1 if y = x 0 otherwise
as a consequence id = Π 1 1 , and, since the latter is a BPF (Definition 2) id is in PR.

• The probabilistic function rand : N → P N such that for every x ∈ N, rand (x)(0) = 1 2 and rand (x)(1) = 1 2 can be easily shown to be recursive, since rand = r ⊙ z (and we know that both r and z are BPF). Actually, rand could itself be taken as the only genuinely probabilistic BPF, i.e., r can be constructed from rand and the other BPF by composition and primitive recursion. We proceed by defining g : N 3 → P N as follow:

g(x 1 , x 2 , z)(y) = 1 if y = z + 1 0 otherwise g is in PR because g = s ⊙ (Π 3
3 ). Now we observe that the function add defined by add (x, 0) = id (x) and add (x 1 , x 2 + 1) = g(x 1 , x 2 , add (x 1 , x 2 )) is a probabilistic recursive function, since it can be obtained from basic functions using composition and primitive recursion. We can conclude by just observing that r = add ⊙ (Π 1 1 , rand ). • All functions we have proved recursive so far have the property that the returned distribution is finite for any input. Indeed, this is true for every probabilistic primitive recursive function, since minimization is the only way to break this form of finiteness. Consider the function f : N → P N defined as f (x)(y) = 1 2 y-x+1 if y ≥ x, and f (x)(y) = 0 otherwise. We define another function h : N → P N by stipulating that h(x)(y) = 1 2 y+1 for every x, y ∈ N. h is a probabilistic recursive function; indeed consider the function k : N 2 → P N defined as rand ⊙ Π 2 1 and build µ k. By definition,

(µ k)(x)(y) = k(x, y)(0) • ( z<y ( q>0 k(x, z)(q))). (1)
Then observe that (µ k)(x)(y) = 1 2 y+1 : by ( 1), (µ k)(x)(y) unfolds into a product of exactly y + 1 copies of 1 2 , each "coming from the flip of a distinct coin". Hence, h = µ k. Then we observe that

(add ⊙ (µ k, id ))(x)(y) = z1,z2 add (z 1 , z 2 )(y) • ((µ k)(x)(z 1 ) • id (x)(z 2 )).
But notice that id (x)(z 2 ) = 1 only when z 2 = x (and in the other cases id

(x)(z 2 ) = 0), (µ k)(x)(z 1 ) = 1 2 z 1 +1
, and add (z 1 , z 2 )(y) = 1 only when z 1 + z 2 = y (and in the other cases, add (z 1 , z 2 )(y) = 0). This implies that the term in the sum is different from 0 only when z 2 = x and z 1 + z 2 = y, namely when z 1 = yz 2 = yx, and in that case its value is 1 2 y-x+1 . Thus, we can claim that f = (add ⊙ (µ k, id )), and that f is in PR.

Probabilistic Turing Machines and Computable Functions

In this section we introduce computable functions as those probabilistic functions which can be computed by Probabilistic Turing Machines. As previously mentioned, probabilistic computation devices have received a wide interest in computer science already in the fifties [START_REF] De Leeuw | Computability by probabilistic machines[END_REF] and early sixties [START_REF] Rabin | Probabilistic automata[END_REF]. A natural question which arose was then to see what happened if random elements were allowed in a Turing machine. This question led to several formalizations of probabilistic Turing machines (PTMs in the following) [START_REF] De Leeuw | Computability by probabilistic machines[END_REF][START_REF] Santos | Probabilistic Turing machines and computability[END_REF] -which, essentially, are Turing machines which have the ability to flip coins in order to make random decisions -and to several results concerning the computational complexity of problems when solved by PTMs [START_REF] Gill | Computational complexity of probabilistic Turing machines[END_REF].

Following [START_REF] Gill | Computational complexity of probabilistic Turing machines[END_REF], a Probabilistic Turing Machine (PTM) M can be seen as a Turing Machine with two transition functions δ 0 , δ 1 . At each computation step, either δ 0 or δ 1 can be applied, each with probability 1/2. Then, in a way analogous to the deterministic case, we can define a notion of a (initial, final) configuration for a PTM M . In the following, Σ b denotes the set of possible symbols on the tape, including a blank symbol ; Q denotes the set of states; Q f ⊆ Q denotes the set of final states and q s ∈ Q denotes the initial state.

Definition 8 (Probabilistic Turing Machine). A Probabilistic Turing Machine (PTM) is a

Turing machine endowed with two transition functions δ 0 , δ 1 . At each computation step the transition function δ 0 can be applied with probability 1/2 and the transition δ 1 can be applied with probability 1/2. Definition 9 (Configuration of a PTM). Let M be a PTM. We define a PTM configuration as a 4-tuple s, a, t, q

∈ Σ * b × Σ b × Σ * b × Q such that:
• The first component, s ∈ Σ * b , is the portion of the tape lying on the left of the head.

• The second component, a ∈ Σ b , is the symbol the head is reading.

• The third component, t ∈ Σ * b , is the portion of the tape lying on the right of the head.

• The fourth component, q ∈ Q is the current state. Moreover we define the set of all configurations as

C M = Σ * b × Σ b × Σ * b × Q.
Definition 10 (Initial and Final Configurations of a PTM). Let M be a PTM. We define the initial configuration of M for the string s as the configuration in the form ε, a, v,

q s ∈ Σ * b × Σ b × Σ * b × Q such that s = a • v and the fourth component, q s ∈ Q, is the initial state. We denote it with IN s M .
Similarly, we define a final configuration of M for s as a configuration s, , ε,

q f ∈ Σ * b × Σ b × Σ * b × Q f .
The set of all such final configurations for a PTM M is denoted by FC s M . For a function T : N → N, we say that a PTM M runs in time bounded by T if for any input x, M halts on input x within T (|x|) steps independently of the random choices it makes. Thus, M works in polynomial time if it runs in time bounded by P , where P is any polynomial.

Intuitively, the function computed by a PTM M associates to each input s, a pseudodistribution which indicates the probability of reaching a final configuration of M from IN s M . It is worth noticing that, differently from the deterministic case, since in a PTM the same configuration can be obtained by different computations, the probability of reaching a given final configuration is the sum of the probabilities of reaching the configuration along all computation paths, of which there can be (even infinitely) many. It is thus convenient to define the function computed by a PTM through a fixpoint construction, as follows. First, we can define a partial order on the string distributions as follows.

Definition 11. A string pseudodistribution on Σ * is a function D : Σ * → R [0,1] such that s∈Σ * D(s) ≤ 1. P Σ * denotes the set of all string pseudodistributions on Σ * . The relation ⊑ P Σ * ⊆ P Σ * × P Σ * is defined as the pointwise extension of the usual partial order on R.

It is easy to show that the relation ⊑ P Σ * from Definition 11 is a partial order. Next, we can define the domain CEV of those functions computed by a PTM M from a given configuration, i.e., the set of those functions f such that f : C M → P Σ * . Inheriting the structure from P Σ * , we can obtain a poset (CEV, ⊑ CEV ), again by defining ⊑ CEV pointwise. Moreover, it is also easy to show that the two introduced posets are ωCPOs.

We can now define a functional F M on CEV which will be used to define the function computed by M via a fixpoint construction. Intuitively, the application of the functional F M describes one computation step. Formally: Definition 12. Given a PTM M , we define a functional F M : CEV → CEV as:

F M (f )(C) = {s 1 } if C ∈ FC s M ; 1 2 f (δ 0 (C)) + 1 2 f (δ 1 (C)) otherwise.
One can show that the functional F M from Definition 12 is continuous on CEV.

A classic fixpoint theorem ensures that F M has a least fixpoint. Such a least fixpoint is, once composed with a function returning IN s M from s, the function computed by the machine M , which is denoted as IO M : Σ * → P Σ * . The set of those functions which can be computed by any PTM is denoted as PC , while PPC is the set of probabilistic functions which can be computed by a PTM working in polynomial time. The notion of a computable probabilistic function subsumes other key notions in probabilistic and real-number computation. As an example, computable distributions can be characterized as those distributions on Σ * which can be obtained as the result of a function in PC on a fixed input. Analogously, computable real numbers from the unit interval [0, 1] can be seen as those elements of R in the form f (0)(0) for a computable function f ∈ PC .

Probabilistic Recursive Functions equals Functions computed by Probabilistic Turing Machines

In this section we prove that probabilistic recursive functions are the same as probabilistic computable functions, modulo an appropriate bijection between strings and natural numbers which we denote (as its inverse) with (•).

In order to prove the equivalence result we first need to show that a probabilistic recursive function can be computed by a PTM. This result is not difficult and, analogously to the deterministic case, is proved by exhibiting PTMs which simulate the basic probabilistic recursive functions and by showing that PC is closed by composition, primitive recursion, and minimization. We omit the details, which can be found in [START_REF] Lago | Probabilistic recursion theory and implicit computational complexity (long version)[END_REF].

The most difficult part of the equivalence proof consists in proving that each probabilistic computable function is actually recursive. Analogously to the classic case, a good strategy consists in representing configurations as natural numbers, then encoding the transition functions of the machine at hand, call it M , as a (recursive) function on N. In the classic case the proof proceeds by making essential use of the minimization operator by which one determines the number of transition steps of M necessary to reach a final configuration, if such number exists. This number can then be fed into another function which simulates M (on an input) a given number of steps, and which is primitive recursive. In our case, this strategy does not work: the number of computation steps can be infinite, even when the convergence probability is 1. Given our definition of minimization which involves distributions, this is delicate, since we have to define a suitable function on the PTM computation tree to be minimized.

In order to adapt the classic proof, we need to formalize the notion of a computation tree which represents all computation paths corresponding to a given input string x. We define such a tree as follows. Each node is labelled by a configuration of the machine and each edge represents a computation step. The root is labelled with IN x M and each node labelled with C has either no child (if C is final) or 2 children (otherwise), labelled with δ 0 (C) and δ 1 (C). Please notice that the same configuration may be duplicated across a single level of the tree as well as appear at different levels of the tree; nevertheless we represent each such appearance by a separate node.

We can naturally associate a probability with each node, corresponding to the probability that the node is reached in the computation: it is 1 2 n , where n is the height of the node. The probability of a particular final configuration is the sum of the probabilities of all leaves labelled with that configuration. We also enumerate nodes in the tree, top-down and from left to right, by using binary strings in the following way: the root has associated the number ε. Then if b is the binary string representing the node N , the left child of N has associated the string b • 0 while the right child has the number b • 1. Note that from this definition it follows that each binary number associated to a node N indicates a path in the tree the root to N . The computation tree for x will be denoted as CT M (x)

We give now a more explicit description of the constructions described above. First we need to encode the rational numbers Q into N. Let pair : N × N → N be any recursive bijection between pairs of natural numbers and natural numbers such that pair and its inverse are both computable. Let then enc be just p pair , i.e. the function enc : N × N → P N defined as follows

enc(a, b)(q) = 1 if q = pair (a, b) 0 otherwise
The function enc allows to represent positive rational numbers as pairs of natural numbers in the obvious way and is recursive.

: N × N → Q is defined as follows: PC M (x, z) = Σ y∈CC M (x,z) PT M (x, y)
Contrary to PT M , there is nothing guaranteeing that PC M is indeed computable. In the following, however, what we do is precisely to show that this is the case.

In Figure 1 we show an example of computation tree CT M (x) for an hypothetical PTM M and an input x. The leaves, depicted as red nodes, represent the final configurations of the computation. So, for example, PC M (x, C) = 1, while PC M (x, E) = 3 4 . Indeed, notice that there are three nodes in the tree which are labelled with E, namely those corresponding to the binary strings 00, 01, and 10. As we already mentioned, our proof separates the classic part of the computation performed by the underlying PTM, which essentially computes the configurations reached by the machine in different paths, from the probabilistic part, which instead computes the probability values associated to each computation by using minimization. These two tasks are realized by two suitable probabilistic recursive functions, which are then composed to obtain the function computed by the underlying PTM. We start with the probabilistic part, which is more complicated. We need to define a function, which returns the conditional probability of terminating at the node corresponding to the string y in the tree CT M (x), given that all the nodes z where z < y are labelled with non-final configurations. This is captured by the following definition:

Definition 15. Given a PTM M , we define PT 0 M : N × N → Q and PT 1 M : N × N → Q as follows: PT 1 M (x, y) = 1 if y is not a leaf of CT M (x); 1 -PT 0 M (x, y) otherwise; PT 0 M (x, y) = 0 if y is not a leaf of CT M (x); PT M (x,y) k<y PT 1 M (x,k) otherwise;
Note that, according to previous definition, PT 1 M (x, y) is the probability of not terminating the computation in the node y, while PT 0 M (x, y) represents the probability of terminating the computation in the node y, both knowing that the computation has not terminated in any node k preceding y.

Proposition 1. The functions PT

0 M : N × N → Q and PT 1 M : N × N → Q are partial recursive.
Proof. Please observe that PT M is partial recursive and that the definitions above are mutually recursive, but the underlying order is well-founded. Both functions are thus intuitively computable, thus partial recursive by the Church-Turing thesis.

⊓ ⊔

The reason why the two functions above are useful is because they associate the distribution {0 PT 1 M (x,y) , 1 PT 0 M (x,y) } to each pair of natural numbers (x, y). In Figure 2, we give the quantities we have just defined for the tree from Figure 1. Each internal node is associated with the same distribution {0 0 , 1 1 }. Only the leaves are associated with nontrivial distributions. As an example, the distribution associated to the node 10 is {0 1/2 , 1 1/2 }, because we have that

PT 0 M (x, 10) = PT M (x, 10) k<10 PT 1 M (x, k) = 1 4 • PT 1 M (x, 01) • PT 1 M (x, 00) • PT 1 M (x, 1) • PT 1 M (x, 0) • PT 1 M (x, ε) = 1 4 • PT 1 M (x, 01) • PT 1 M (x , 00)
.

As it can be easily verified,

PT 1 M (x, 00) = 3 4 , while PT 1 M (x, 01) = 2 3 . Thus, PT 0 M (x, 10) = 1 2 . {0 0 , 1 1 } C ε {0 0 , 1 1 } D 0 {0 1/4 , 1 3/4 } E 00
{0 1/3 , 1 2/3 } E 01 {0 0 , 1 1 } F 1 {0 1/2 , 1 1/2 } E 10 {0 1 , 1 0 } G 11
Fig. 2. The Conditional Probabilities for the Computation Tree from Figure 1 We now need to go further, and prove that the probabilistic function returning, on input (x, y), the distribution {0 PT 1 M (x,y) , 1 PT 0 M (x,y) } is recursive. This is captured by the following definition:

Definition 16. Given a PTM M , the function PTC M : N × N → P N is defined as follows PTC M (x, y)(z) =    PT 0 M (x, y) if z = 0; PT 1 M (x, y) if z = 1; 0 otherwise-
The function PTC M is really the core of our encoding. On the one hand, we will show that it is indeed recursive. On the other, minimizing it is going to provide us exactly with the function we need to reach our final goal, namely proving that the probabilistic function computed by M is itself recursive. But how should we proceed if we want to prove PTC M to be recursive? The idea is to compose p PT 1 M with a function that turns its input into the probability of returning 1. This is precisely what the following function does:

Definition 17. The function I2P : Q → P N is defined as follows I2P (x)(y) =    x if (0 ≤ x ≤ 1) ∧ (y = 1) 1 -x if (0 ≤ x ≤ 1) ∧ (y = 0) 0 otherwise
Please observe how the input to I2P is the set of rational numbers, as usual encoded by pairs of natural numbers. Previous definitions allow us to treat (rational numbers representing) probabilities in our algebra of functions. Indeed:

Proposition 2. The probabilistic function I2P is recursive.

Proof. We first observe that h : N → P N defined as

h(x)(y) = 1/2 y+1
is a probabilistic recursive function, because h = µ (rand ⊙Π 2 1 ). Next we observe that every q ∈ Q ∩ [0, 1] can be represented in binary notation as:

q = i∈N c q i 1/2 i+1
where c q i ∈ {0, 1} (i.e., c q i is the i-th element of the binary representation of q). Moreover, a function computing such a c q i from q and i is partial recursive. Hence we can define b :

N × N → P N as follows b(q, i)(y) = 1 if y = c q i 0 otherwise
and conclude that b is indeed a probabilistic recursive function (because PR includes all the partial recursive functions, seen as probabilistic functions). Observe that:

b(q, i)(y) = c q i if y = 1 1 -c q i if y = 0
From the definition of composition, it follows that

(b ⊙ (id, h))(q)(y) = x1,x2 b(x 1 , x 2 )(y) • id(q)(x 1 ) • h(q)(x 2 ) = x2 b(q, x 2 )(y) • h(q)(x 2 ) = x2 b(q, x 2 )(y) • 1 2 x2+1 = x2 c q x 2 2 x 2 +1 if y = 1 x2 1-c q x 2 2 x 2 +1 if y = 0 = q if y = 1 1 -q if y = 0 .
This shows that I2P = b ⊙ (id, h), and hence that I2P is probabilistic recursive.

⊓ ⊔

The following is an easy corollary of what we have obtained so far:

Proposition 3. The probabilistic function PTC M is recursive. Proof. Just observe that PTC M = I2P ⊙ p PT 1 M . ⊓ ⊔
The probabilistic recursive function obtained as the minimization of PTC M allows to compute a probabilistic function that, given x, returns y with probability PT M (x, y) if y is a leaf (and otherwise the probability is just 0). Proof. The probabilistic function CF M is just the function obtained by minimizing PTC M , which we already know to be recursive. Indeed, if z corresponds to a leaf, then:

(µPTC M )(x)(z) = PTC M (x, z)(0) • y<z k>0 PTC M (x, y)(k) = PTC M (x, z)(0) • y<z PTC M (x, y)(1) = PT 0 M (x, z) • y<z PT 1 M (x, y) = PT M (x, z) y<z PT 1 M (x, y) • y<z PT 1 M (x, y) = PT M (x, z).
If, however, z does not correspond to a leaf, then:

(µPTC M )(x)(z) = PTC M (x, z)(0) • y<z k>0 PTC M (x, y)(k) = PT 0 M (x, z)(0) • y<z k>0 PTC M (x, y)(k) = 0.
This concludes the proof.

⊓ ⊔

We are almost ready to wrap up our result, but before proceeding further, we need to define the function SP M : N × N → N that, given in input a pair (x, y) returns the (encoding) of the string found in the configuration labeling the node y in CT M (x). We can now prove the desired result:

Theorem 1. PC ⊆ PR.
Proof. It suffices to note that, given any PTM M , the function computed by M is nothing more than p SP M ⊙ (id , CF M ).

Indeed, one can easily realize that a way to simulate M consists in generating, from x, all strings corresponding to the leaves of CT M (x), each with an appropriate probability. This is indeed what CF M does. What remains to be done is simulating p SP M along paths leading to final configurations.

⊓ ⊔

We are finally ready to prove the main result of this Section:

Corollary 1 PR = PC
Proof. Immediate from Theorem 1, observing that PR ⊆ PC (this implication is easy to prove).

⊓ ⊔

The way we prove Corollary 1 implies that we cannot deduce Kleene's Normal Form Theorem from it: minimization has been used many times, some of them "deep inside" the construction. A way to recover Kleene's Theorem consists in replacing minimization with a more powerful operator, essentially corresponding to computing the fixpoint of a given function (see [START_REF] Lago | Probabilistic recursion theory and implicit computational complexity (long version)[END_REF] for more details).

Characterizing Probabilistic Complexity by Tiering

In this section we provide a characterization of the probabilistic functions which can be computed in polynomial time by an algebra of functions acting on word algebras. More precisely, we define a type system inspired by Leivant's notion of tiering [START_REF] Leivant | Ramified recurrence and computational complexity I: Word recurrence and poly-time[END_REF], which permits to rule out functions having a too-high complexity, thus allowing to isolate the class of predicative probabilistic functions. Finally, we give a hint at how the equivalence between polytime probabilistic functions and predicative probabilistic functions can be proved (more details are in [START_REF] Lago | Probabilistic recursion theory and implicit computational complexity (long version)[END_REF]).

The constructions from Section 2 can be easily generalized to a function algebra on strings in a given alphabet Σ, which themselves can be seen as a word algebra W. Base functions include a function computing the empty string, called ε, and concatenation with any character a ∈ Σ, called c a . Projections remain of course available, while the only truly random functions concatenate a symbol a ∈ Σ to the input, with probability 1 2 , or leave it unchanged, with probability 1 2 . Such a function is denoted as r a . Composition and primitive recursion are available, although the latter takes the form of recursion on notation. We do not need minimization: the distribution a polytime computable probabilistic function returns (on any input) is always finite, and primitive recursion is anyway powerful enough for our purposes.

The following construction is redundant in presence of primitive recursion, but becomes essential when predicatively restricting it: Definition 19 (Case Distinction). If g ε : W k → P W and for every a ∈ Σ, g a : W k+1 → P W , the function h : W k+1 → P W such that h(ε, y) = g ε (y) and h(a • w, y) = g a (w, y) is said to be defined by case distinction from g ε and {g a } a∈Σ and is denoted as case(g ε , {g a } a∈Σ ).

The idea behind tiering consists in working with denumerable many copies of the underlying algebra W, each indexed by a natural number n ∈ N and denoted by W n . Judgments take the form f

⊲ W n1 × . . . × W n k → W m , where f : W k → W.
In the following, with slight abuse of notation, W stands for any expression in the form

W i1 × • • • × W ij .
Typing rules are in Figure 3. The idea here is that, when generating functions by primitive recursion, one goes from a level (tier) m for the domain to a strictly lower level k for the result. This predicative constraint ensures that recursion does not cause any exponential blowup, simply because the way one can nest primitive recursive definitions one inside the other is severely restricted. Please notice that case distinction, although being typed in a similar way, does not require the same constraints.

ε ⊲ W k → W k ra ⊲ W k → W k ca ⊲ W k → W k Π k m ⊲ Wn 1 × • • • × Wn k → Wn m {gi ⊲ Ws 1 × • • • × Ws r → Wm i } 1≤i≤p f ⊲ Wm 1 × • • • × Wm p → W l f ⊙ (g1, . . . , g l ) ⊲ Ws 1 × • • • × Ws r → W l gε ⊲ W → W l {ga ⊲ W k × W → W l }a∈Σ case(gε, {ga}a∈Σ) ⊲ W k × W → W l gε ⊲ W → W k m > k {ga ⊲ W k × Wm × W → W k }a∈Σ rec(gǫ, {ga}a∈Σ) ⊲ Wm × W → W k
Those probabilistic functions f : W k → P W such that f can be given a type through the rules in Figure 3 are said to be predicatively recursive. The class of all predicatively recursive functions is PT . Actually, the class coincides with the one of probabilistic functions which can be computed by PTMs in polynomial time:

Theorem 2. PT = PPC .

We don't have enough space to give the details of the proof of Theorem 2. It however proceeds essentially by showing the following four lemmas, from which the thesis can be easily inferred:

• On the one hand, one can prove, by a careful encoding, that a form of simultaneous primitive recursion is available in predicative recursion. • On the other hand, PTMs can be shown equivalent, in terms of expressivity, to probabilistic register machines; going through register machines has the advantage of facilitating the last two steps. • Thirdly, any function definable by predicative recurrence can be proved computable by a polytime probabilistic register machine. • Lastly, one can give an embedding of any polytime probabilistic register machine into a predicatively recursive function, making use of simultaneous recurrence. Characterizing complexity classes of probabilistic functions allows to deal implicitly with concepts like that of a polynomial time samplable distribution [START_REF] Bogdanov | Average-case complexity[END_REF][START_REF] Goldreich | Foundations of Cryptography: Basic Tools[END_REF], which is a family {D n } n∈N of distributions on strings such that a polytime randomized algorithm produces D n when fed with the string 1 n . By Theorem 2, each of them is computed by a function in PT and, conversely, any predicatively recursive probabilistic function computes one such family.

Conclusions

In this paper we make a first step in the direction of characterizing probabilistic computation in itself, from a recursion-theoretical perspective, without reducing it to deterministic computation. The significance of this study is genuinely foundational: working with probabilistic functions allows us to better understand the nature of probabilistic computation on the one hand, but also to study the implicit complexity of a generalization of Leivant's predicative recurrence, all in a unified framework.

More specifically, we give a characterization of computable probabilistic functions by a natural generalization of Kleene's partial recursive functions which includes, among initial functions, one that returns the uniform distribution on {0, 1}. We then prove the equi-expressivity of the obtained algebra and the class of functions computed by PTMs. In the the second part of the paper, we investigate the relations existing between our recursion-theoretical framework and sub-recursive classes, in the spirit of ICC. More precisely, endowing predicative recurrence with a random base function is proved to lead to a characterization of polynomial-time computable probabilistic functions.

An interesting direction for future work could be the extension of our recursiontheoretic framework to quantum computation. In this case one should consider transformations on Hilbert spaces as the basic elements of the computation domain. The main difficulty towards obtaining a completeness result for the resulting algebra and proving the equivalence with quantum Turing machines seems to be the definition of suitable recursion and minimization operators generalizing the ones described in this paper, given that qubits (the quantum analogues of classical bits) cannot be copied nor erased.

  It is now time to define a few notions on computation treesDefinition 13 (Computation Trees and String Probabilities). The function PT M : N × N → Q is defined by stipulating that PT M (x, y) is the probability of observing the string y in the tree CT M (x), namely1 2 |y| . Of course, PT M is partial recursive, thus p PT M is probabilistic recursive. Since the same configuration C can label more than one node in a computation tree CT M (x), PT M does not indicate the probability of reaching C, even when C is the label of the node corresponding to the second argument. Such a probability can be obtained by summing the probability of all nodes labelled with the configuration at hand: Definition 14 (Configuration Probability). Suppose given a PTM M . If x ∈ N and z ∈ C M , the subset CC M (x, z) of N contains precisely the indices of nodes of CT M (x) which are labelled by z. The function PC M

Fig. 1 .

 1 Fig. 1. An Example of a Computation Tree

Definition 18 .Proposition 4 .

 184 The function CF M : N → P N is defined as followsCF M (x)(y) =PT M (x, y) if y corresponds to a leaf 0 otherwise. The probabilistic function CF M is recursive.

Fig. 3 .

 3 Fig. 3. Tiering as a Typing System

⋆ This work is partially supported by the ANR project 12IS02001 PACE.