{'fraction_non_alphanumeric': 0.0633134865688175, 'fraction_numerical': 0.01607934090279701, 'mean_word_length': 3.3376126126126127, 'pattern_counts': {'":': 0, '<': 68, '<?xml version=': 0, '>': 44, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Equivalences between learning of data and probability distributions, and their applications

Algorithmic learning theory traditionally studies the learnability of effective infinite binary sequences (reals), while recent work by [Vitanyi and Chater, 2017] and [Bienvenu et al., 2014] has adapted this framework to the study of learnability of effective probability distributions from random data. We prove that for certain families of probability measures that are parametrized by reals, learnability of a subclass of probability measures is equivalent to learnability of the class of the corresponding real parameters. This equivalence allows to transfer results from classical algorithmic theory to learning theory of probability measures. We present a number of such applications, providing many new results regarding EX and BC learnability of classes of measures, thus drawing parallels between the two learning theories.


Introduction
One of the central problems in statistics is, given a source of random data to determine a probability distribution according to which the data were generated [Vapnik, 1982]. This problem has also been studied extensively in the context of computational learning, in particular the probably approximately correct (PAC) learning model, starting with [Kearns et al., 1994]. More recently, [Vitanyi and Chater, 2017, Bienvenu et al., 2014 initiated the study of this problem in the context of algorithmic learning, 1 based on [Gold, 1967] and the theory of algorithmic randomness and Kolmogorov complexity. A class of computable probability measures C is learnable, if there exists an algorithm that while reading increasingly longer segments of any algorithmically random binary stream X with respect to some µ ∈ C, it eventually determines a description of some µ ′ ∈ C with respect to which X is algorithmically random. 2 There are a number of ways to formalize this definition, many akin to the various learning notions from algorithmic learning theory that originate in [Gold, 1967].
A learner is simply a function L : 2 <ω → N. We refer to infinite binary streams (sequences) as reals. According to [Gold, 1967], a class C of computable elements of 2 ω is EX-learnable if there exists a learner L such that for each Z ∈ C we have that lim n L(Z ↾ n ) exists and equals an index of Z as a computable function. Similarly, C is BC-learnable if there exists a learner L such that for each Z ∈ C there exists some n 0 such that for all n > n 0 the value of L(Z ↾ n ) is an index of Z.
In this paper we study explanatory (EX) learning, behaviorally correct (BC) learning and partial learning of probability measures, based on the classic notion of algorithmic randomness by [Martin-Löf, 1966]. Given a measure µ on the reals and a real X, we say that X is µ-random if it is algorithmically random with respect to µ. We review algorithmic randomness with respect to arbitrary measures in Section 2.3. Definition 1.1 (EX learning of measures). A class C of computable measures is EX-learnable if there exists a computable learner L : 2 <ω → N such that for every µ ∈ C and every µ-random real X the limit lim n L(X ↾ n ) exists and equals an index of a measure µ ′ ∈ C such that X is µ ′ -random. [Vitanyi and Chater, 2017] introduced this notion and observed that any uniformly computable family of measures is EX-learnable. On the other hand, [Bienvenu et al., 2014] showed that the class of computable measures is not EX-learnable, and also not even BC-learnable in the following sense.
Definition 1.2 (BC learning of measures). A class C of computable measures is BC-learnable if there exists a computable learner L : 2 <ω → N such that for every µ ∈ C and every µ-random real X there exists n 0 and µ ′ ∈ C such that for all n > n 0 the value L(X ↾ n ) is an index of µ ′ such that X is µ ′ -random.
One could consider a stronger learnability condition, namely that given µ ∈ C and any µ-random X the learner identifies µ in the limit, when reading initial segments of X. Note that such a property would only be realizable in classes C where any µ, µ ′ ∈ C are effectively orthogonal, which means that the classes of µ-random and µ ′ -random reals are disjoint. 3 On the other hand we could considered a weakened notion 1 In algorithmic learning, one starts with a class of languages or functions which have a finite description and the problem is to find an algorithm (a learner) which can infer, given a sufficiently long text from any language in the given class, a description of the language or function in the form of a grammar or a program. 2 Two differences with classic algorithmic learning are: (a) the inputs on which the learner is supposed to succeed in the limit are random sequences with respect to some probability distribution in the given class C, and not elements of C; (b) there may be multiple acceptable guesses of a learner along real X, since X may be random with respect to many measures in C.
3 In this case we call C effectively orthogonal, and Definitions 1.1, 1.2 are equivalent with the versions where µ ′ is replaced by µ.
of learning of a class C of computable measures, where given µ ∈ C and any µ-random X, the learner identifies some computable measure µ (possibly not in C) in the limit, with respect to which X is random, when reading initial segments of X. Definition 1.3 (Weak EX learning of measures). A class C of computable measures is weakly EX-learnable if there exists a computable learner L : 2 <ω → N such that for every µ ∈ C and every µ-random real X the limit lim n L(X ↾ n ) exists and equals an index of a computable measure µ ′ such that X is µ ′ -random.
Definition 1.4 (Weak BC learning of measures). A class C of computable measures is weakly BC-learnable if there exists a computable learner L : 2 <ω → N such that for every µ ∈ C and every µ-random real X there exists n 0 and a computable measure µ ′ , such that for all n > n 0 the value L(X ↾ n ) is an index of µ ′ such that X is µ ′ -random.
We note that the notions in Definitions 1.1 and 1.2 are not closed under subsets.
Proposition 1.5. There exist classes C ⊆ D of measures such that D is EX-learnable and C is not even BC-learnable.
Clearly C ⊆ D. If C was BC-learnable then ∅ ′′′ could be decided in ∅ ′′ , which is a contradiction. On the other hand the learner which guesses ν i on each extension of σ i is an EX-learner for D.
On the other hand, the weaker notions of Definitions 1.3 and 1.4 clearly are closed under subsets. In Section 1.1 we also consider an analogue of the notion of partial learning from [Osherson et al., 1986] for measures, and prove an analogue of the classic result from the same paper that the computable reals are partially learnable.

Our main results
The aim of this paper is to establish a connection between the above notions of learnability of probability measures, with the corresponding classical notions of learnability of reals in the sense of [Gold, 1967]. To this end, we prove the following equivalence theorem, which allows to transfer positive and negative learnability results from reals to probability measures that are parametrized by reals, and vice-versa. Let M denote the Borel measures on 2 ω . Theorem 1.6 (The first equivalence theorem). Given a computable f : 2 ω → M let D ⊆ 2 ω be an effectively closed set such that for any X Y in D the measures f (X), f (Y) are effectively orthogonal. If D * ⊆ D is a class of computable reals, D * is EX-learnable if and only if f (D * ) is EX-learnable. The same is true of the BC learnability of D * .
As a useful and typical example of a parametrization f of measures by reals as stated in Theorem 1.6, consider the function that maps each real X ∈ 2 ω to the Bernoulli measure with success probability the real in the unit interval [0, 1] with binary expansion X. 4 The proof of Theorem 1.6 is given in Section 3. 5 The next equivalence theorem concerns weak learnability. 6 Theorem 1.7 (The second equivalence theorem). There exists a map Z → µ Z from 2 ω to the continuous Borel measures on 2 ω , such that for every class C of computable reals, C is EX/BC learnable if and only if {µ Z | Z ∈ C} is a weakly EX/BC learnable class of computable measures, respectively.
Finally we give a positive result in terms of partial learning. We say that a learner L partially succeeds on a computable measure µ if for all µ-random X there exists a j 0 such that (a) there are infinitely many n with L(X ↾ n ) = j 0 ; (b) if j j 0 then there are only finitely many n with L(X ↾ n ) = j; (c) µ j 0 is a computable measure such that X is µ j 0 -random.
Theorem 1.8. There exists a computable learner which partially succeeds on all computable measures. Theorems 1.6 and 1.7 allow the transfer of learnability results from the classical theory on the reals to probability measures. Detailed background on the notions that are used in our results and their proofs is given in Section 2.

Applications of our main results
The equivalences in Theorems 1.6 and 1.7 have some interesting applications, some of which are stated below, deferring their proofs to Section 4. [Adleman and Blum, 1991] showed that an oracle can EX-learn all computable reals if and only if it is high, i.e. it computes a function that dominates all computable functions. Using Theorem 1.7 we may obtain the following analogue for measures.

Corollary 1.9. The computable (continuous) measures are (weakly) EX-learnable with oracle A if and only if A is high.
We may write EX[A] to indicate that the EX-learner is computable in A. A class C of measures is (weakly) EX * [A]-learnable for an oracle A, if there exists an EX-learner L ≤ T A for C such that for each X, the function n → L(X ↾ n ) uses finitely many queries to A. The following is an analogue of a result from [Kummer and Stephan, 1996]  If we apply Theorem 1.6 we obtain an analogue of the [Adleman and Blum, 1991] [Blum and Blum, 1975] showed the so-called non-union theorem for EX-learning, namely that EX-learnability of classes of computable reals is not closed under union. We may apply our equivalence theorem in order to prove an analogue for measures. Corollary 1.12 (Non-union for measures). There are two EX-learnable classes of computable (Bernoulli) measures such that their union is not EX-learnable.
in Section 3. 4. 6 For the special case where we allow measures with atoms in our classes, Theorem 1.7 has a somewhat easier proof than the one given in Section 3.5.
One can find applications of Theorem 1.6 on various more complex results in algorithmic learning theory. As an example, we mention the characterization of low oracles for EX-learning that was obtained in Pleszkoch, 1989, Slaman andSolovay, 1991] (also see [Fortnow et al., 1994]). An oracle A is low for EX-learning of classes of computable measures, if any class of computable measures that is learnable with oracle A, is learnable without any oracle. The characterization mentioned above is that, an oracle is low for EX-learning if and only if it is 1-generic and computable from the halting problem. This argument consisted of three steps, first showing that 1-generic oracles computable from the hating problem are low for EX-learning, then that oracles that are not computable from the halting problem are not low for EX-learning, and finally that oracles that are computable from the halting problem but are not 1-generic are not low for EX-learning. The last two results can be combined with Theorem 1.6 in order to show one direction of the characterization for measures: if an oracle A is either not computable from the halting problem or not 1-generic, then there exists a class of computable (Bernoulli) measures which is not EX-learnable but which is EX-learnable with oracle A. (1) In other words, low for EX-learning oracles for measures are 1-generic and computable from the halting problem.
Corollary 1.13. If an oracle is low for EX-learning for measures, then it is also low for EX-learning for reals.
We do not know if the converse of Corollary 1.13 holds. [Bienvenu et al., 2014] say that a learner L EX-succeeds on a real X if lim n L(X ↾ n ) equals an index of a computable measure with respect to which X is random. Similarly, L BC-succeeds on X if there exists a measure µ such that X is µ-random, and for all sufficiently large n, the value of L(X ↾ n ) is an index of µ. The results in [Bienvenu et al., 2014[Bienvenu et al., , 2017 are of the form 'there exists (or not) a learner which succeeds on all reals that are random with respect to a computable measure'. Hence [Bienvenu et al., 2014[Bienvenu et al., , 2017 refer to the weak learnability of Definitions 1.3 and 1.4. [Bienvenu and Monin, 2012] introduced and studied layerwise learnability, in relation to uniform randomness extraction from biased coins. This notion is quite different from learnability in the sense of algorithmic learning theory, but it relates to the 'only if' direction of Theorem 1.6. Let M denote the class of Borel measures on 2 ω . 7 A class C ⊆ M of measures (not necessarily computable) is layerwise learnable if there is a computable function F : 2 ω × N → M which, given any µ ∈ C and any µ-random real X, if the µ-randomness deficiency of X is less than c then F(X, c) = µ. In other words, this notion of learnability of a class C ⊆ M requires to be able to compute (as an infinite object) any measure µ ∈ C from any µ-random real and a guarantee on the level of µ-randomness of the real. 8 As a concrete example of the difference between the two notions, consider the class of the computable Bernoulli measures which is layerwise learnable [Bienvenu and Monin, 2012] but is not (weakly) EX-learnable or even (weakly) BC-learnable by [Bienvenu et al., 2014].

Background
We briefly review the background on the Cantor space 2 ω and the space of Borel measures on that is directly relevant for understanding our results and proofs. We focus on effectivity properties of these concepts and the notion of algorithmic randomness. This is textbook material in computable analysis and algorithmic randomness, and we have chosen a small number of references where the reader can obtain more detailed presentations that are similar in the way we use the notions here.

Representations of Borel measures on the Cantor space
We view 2 ω and the space M of Borel measures on 2 ω as computable metric spaces. 9 The distance between two reals is 2 −n where n is the first digit where they differ, and the basic open sets are σ =: {X ∈ 2 ω | σ X}, σ ∈ 2 <ω , where denotes the prefix relation. 10 The distance between µ, ν ∈ M is given by The basic open sets of M are the balls of the form We represent measures in M as the functions µ : 2 <ω → [0, 1] such that µ(∅) = 1 (here ∅ is the empty string) and µ(σ) = µ(σ * 0) + µ(σ * 1) for each σ ∈ 2 <ω . We often identify a measure with its representation. A measure µ is computable if the its representation is computable as a real function. There are two equivalent ways to define what an index (or description) of a computable measure is. One is to define it as a computable approximation to it with uniform modulus of convergence. For example, we could say that a partial computable measure is a c.e. set W of basic open sets (σ, I) of M, where σ ∈ 2 <ω , I is a basic open interval of [0, 1]; 12 In this case we can have a uniform enumeration (µ e ) of all partial computable measures, which could contain non-convergent approximations. Then µ e , represented by the c.e. set W e , is total and equal to some measure µ if µ ∈ [(σ, I)] for all σ, I with (σ, I) ∈ W e , and for each σ we have 9 All of the notions and facts discussed in this section are standard in computable analysis and are presented in more detail in Monin, 2012, Bienvenu et al., 2017]. More general related facts, such that the fact that for any computable metric space C the set of probability measures over C is itself a computable metric space, can be found in [Gács, 2005]. 10 If V ⊆ 2 ω then V := ∪ σ∈V σ . 11 These are the intervals (q, p), [0, q), (p, 1] for all dyadic rationals p, q ∈ (0, 1). 12 if one wishes to ensure that in case of convergence the property µ(σ) = µ(σ * 0) + µ(σ * 1) holds, we could also require that if (σ, I), inf{|I| | (σ, I) ∈ W e } = 0. Alternatively, one could consider the fact that for every computable measure µ there exists a computable measure ν which takes dyadic values on each string σ, and such that µ = Θ(ν) (i.e. the two measures are the same up to a multiplicative constant). 13 Moreover from µ one can effectively define ν, and the property µ = Θ(ν) implies that the µ-random reals are the same as the ν-random reals. This means that we may restrict our considerations to the computable measures with dyadic rational values on every string, without loss of generality. Then we can simply let (µ e ) be an effective list of all partial computable functions from 2 <ω to the dyadic rationals such that µ(σ) = µ(σ * 0) + µ(σ * 1) for each σ such that the values µ(σ), µ(σ * 0), µ(σ * 1) are defined.
The two formulations are effectively equivalent, in the sense that from one we can effectively obtain the other, so we do not explicitly distinguish them. In any case an index of a computable measure µ is a number e such that µ e is total and equals µ. An important exception to this equivalence is when we consider subclasses of computable measures, such as the computable Bernoulli measures which feature in Section 4. In this case we have to use the first definition of (µ e ) above, since it is no longer true that every computable Bernoulli measure can be replaced with a computable Bernoulli measure with dyadic values which has the same random reals.

Computable functions and metric spaces
There is a well-established notion of a computable function f between computable metric spaces from computable analysis, e.g. see Monin, 2012, Weihrauch, 1993]. The essence of this notion is effective continuity, i.e. that for each x and a prescribed error bound ǫ for an approximation to f (x), one can compute a neighborhood radius around x such that all of the y in the neighborhood are mapped within distance ǫ from f (x). Here we only need the notion of a computable function f : 2 ω → M, which can be seen to be equivalent to the following (due to the compactness of 2 ω ). Let M * denote the basic open sets of M.
Definition 2.1. A function f : 2 ω → M is computable if there exists a computable function f * : 2 <ω → M * which is monotone in the sense that σ τ implies f * (σ) ⊆ f * (τ), and such that for all Z ∈ 2 ω we have More generally, a computable metric space is a tuple (X, d x , (q i )) such that (X, d x ) is a complete separable metric space, (q i ) is a countable dense subset of X and the function ( In this way, as it is illustrated in Definition 2.1, computable functions between 2 ω , N, M and their products can be thought of as induced by monotone computable functions between the corresponding classes of basic open sets, such that the sizes of the images decrease uniformly as a function of the size of the arguments. 13 See [Juedes and Lutz, 1995].

Algorithmic randomness with respect to arbitrary measures
There is a robust notion of algorithmic randomness with respect to an arbitrary measure µ on 2 ω , which was manifested in approaches by [Levin, 1976[Levin, , 1984 and [Gács, 2005] in terms of uniform tests, and in [Reimann and Slaman, 2015] in terms of representations of measures, all of which were shown to be equivalent by [Day and Miller, 2013]. In this paper we will mainly use the specific case when the measure is computable, which is part of the classic definition of [Martin-Löf, 1966]. Given a computable measure µ, a Martin-Löf µ-test is a uniformly c.e. sequence (U i ) of sets of strings (viewed as the sets of reals with prefixes the strings in the sets) such that µ( Occasionally it is useful to refer to the randomness deficiency of a real, which can be defined in many equivalent ways. 14 For example, we could define µ-deficiency to be the least i such that . Clearly Z is µ-random if and only if it has finite µ-deficiency. Randomness with respect to arbitrary measures only plays a role in Section 3.1. We define it in terms of randomness deficiency, following [Bienvenu et al., 2017]. We define the (uniform) randomness deficiency function to be the largest, up to an additive constant, function d : Given any µ ∈ M and Z ∈ 2 ω , the µ-deficiency of Z is d(Z, µ) and Z is µ-random if it has finite µ-deficiency. This definition is based on the uniform tests approach as mentioned before, and is equivalent to Martin-Löf randomness for computable measures. Moreover the deficiency notions are equivalent in the sense of footnote 14.
3 Proof of Theorem 1.6 and Theorem 1.7 We start with Theorem 1.6. Let D ⊆ 2 ω be an effectively closed set and let D * ⊆ D contain only computable reals. Also let f : 2 ω → M be a computable function such that for any X Y in D the measures f (X), f (Y) are effectively orthogonal. The easiest direction of Theorem 1.6 is that if D * is (EX or BC) learnable then f (D * ) is (EX or BC, respectively) learnable, and is proved in Section 3.1. 16 Sections 3.2 and 3.3 prove the 'if' direction of Theorem 1.6 for EX and BC learnability respectively, and are the more involved part of this paper. In Section 3.5 we prove Theorem 1.7. 14 Equivalent in the sense that from an upper bound of one notion with respect to a real, we can effectively obtain an upper bound on another notion with respect to the same real. 15 We can get a precise definition of d by starting with a universal enumeration W e (k) all uniform c.e. sequences of sets W(k), where each W(k) is a set of pairs (σ, I) of basic open sets of 2 ω , M respectively (viewed as basic open set of the product space 2 ω × M) with the property that for each µ is the maximum k such that (X, µ) is in the open set W e (k). 16 We stress that the effective orthogonality property of f , and hence the fact that it is injective, is used in a crucial way in the argument of Section 3.1.

From learning reals to learning measures
We show the 'only if' direction of Theorem 1.6, first for EX learning and then for BC learning. Let f, D, D * be as in the statement of Theorem 1.6. Since D is effectively orthogonal, given X ∈ 2 ω there exists at most one µ ∈ f (D) such that X is µ-random. By the properties of f , there is also at most one Z ∈ D such that X is f (Z)-random. Moreover for each X ∈ 2 ω , c ∈ N, the class of Z ∈ D such that X is f (Z)-random with redundancy ≤ c is a Π 0 1 (X) class P(X, c) (uniformly in X, c) which either contains a unique real, or empty. Moreover the latter case occurs if and only if there is no µ ∈ f (D) with respect to which X is µ-random with deficiency ≤ c. Now note that given a Π 0 1 (X) class P ⊆ 2 ω , by compactness the emptiness of P is a Σ 0 1 (X) event, and if P contains a unique path, this path is uniformly computable from X and an index of P. It follows that there exists a computable function h : 2 <ω → 2 <ω such that for all X which is f (Z)-random for some Z ∈ D, Indeed, on the initial segments of X, the function h will start generating the classes P(X, c) as we described above, starting with c = 0 and increasing c by 1 each time that the class at hand becomes empty. While this process is fixed on some value of c, it starts producing the initial segments of the unique path of P(X, c) (if there are more than one path, this process will stop producing longer and longer strings, reaching a finite partial limit). In the special case that X is f (Z)-random for some Z ∈ D, such a real Z ∈ D is unique, and the process will reach a limit value of c, at which point it will produce a monotone sequence of longer and longer prefixes of Z. 17 Note that since f : 2 ω → M is computable, there exists a computable g : N → N such that for each e, if e is an index of a computable Z ∈ 2 ω , then g(e) is an index of the computable measure f (Z).
We are ready to define an EX-learner V for f (D * ), given an EX-learner L for D * and the functions h, g that we defined above. For each σ we let V(σ) = g (L(h(σ))). It remains to verify that for each X which is µ-random for some computable µ ∈ f (D * ), the limit lim s V(X ↾ s ) exists and equals an index for (the unique such) µ. By the choice of X and h we have that there exists some s 0 such that for all s > s 0 , the string h(X ↾ s ) is an initial segment of the unique Z ∈ D * such that f (Z) = µ; moreover lim s |h(X ↾ s )| = ∞ and since µ is computable and D is effectively closed, it follows that Z is computable. Hence, since L learns all reals in D * , we get that lim s L(h(X ↾ s )) exists and is an index of Z. Then by the properties of g we get that g(lim s L(h(X ↾ s ))) = lim s g(L(h(X ↾ s ))) is an index for µ. Hence lim s V(X ↾ s ) is an index of the unique computable µ ∈ f (D * ) with respect to which X is random, which concludes the proof.
Finally we can verify that the same argument shows that if D * is BC-learnable, then f (D * ) is BC-learnable. The definitions of h, g remain the same. The only change is that now we assume that L is a BC-learner for D * . We define the BC-learner V for f (D * ) in the same way: V(σ) = g (L(h(σ))). As before, given X such that there exists (a unique) Z ∈ D * such that X is f (Z)-random, we get that there exists some s 0 such that for all s > s 0 , the string h(X ↾ s ) is an initial segment of the unique computable Z ∈ D * such that f (Z) = µ, and moreover lim s |h(X ↾ s )| = ∞. Since L is a BC-learner for D * , there exists some s 1 such that for all s > s 1 the integer L(h(X ↾ s )) is an index for the computable real Z. Then by the properties of g we get that for all s > s 1 , the integer g(L(h(X ↾ s ))) is an index for the computable measure f (Z). Since X is f (Z)-random, this concludes the proof of the BC clause of the 'only if' direction of Theorem 1.6.

From learning measures to learning reals: the EX case
We show the 'if' direction of the EX case of Theorem 1.6. Let f, D, D * be as given in the theorem and suppose that f (D * ) is EX-learnable. This means that there exists a computable learner V such that for every Z ∈ D * and every f (Z)-random X, the limit lim s V(X ↾ s ) exists and is an index of f (Z). We are going to construct a learner L for D * so that for each Z ∈ D * the limit lim s L(Z ↾ s ) exists and is an index for Z. Since D is effectively closed and f is computable and injective on D, by the compactness of 2 ω , there exists a computable g : N → N such that for each e, if e is an index of a computable µ ∈ f (D), the image g(e) is an index of the unique and computable Z ∈ D such that f (Z) = µ. (2) Hence it suffices to construct a computable function L * : 2 <ω → N with the property that for each Z ∈ D * the limit lim s L * (Z ↾ s ) exists and is an index for f (Z) ( 3) because then the function L(σ) = g(L * (σ)) will be a computable learner for D * .
Note that by the properties of f * we have for each Z ∈ 2 ω , each n ∈ N and any measures µ, ν ∈ f * (Z ↾ h(n) ) we have Below we will also use the fact that there is a computable function that takes as input any basic open interval I of M and returns (an index of) a computable measure (say, as a measure representation) µ ∈ I.
Proof idea. Given Z ∈ D * we have an approximation to the measure µ * = f (Z). Given µ * and V we get a majority vote on each of the levels of the full binary tree, where each string σ votes for the index V(σ) and its vote has weight µ * (σ). In search for the index of Z ∈ D * we approximate the weights of the various indices as described above, and aim to chose an index with a positive weight. If V EX-learns µ * , it follows that such an index will indeed be an index of µ * . One obvious way to look for such an index is at each stage to choose the index whose current approximated weight is the largest. This approach has the danger that there may be two different indices with the same weight, in which case it is possible that the said approximation lim n L * (X ↾ n ) does not converge. We deal with this minor issue by requiring a sufficient difference on the current weights for a change of guess.
Construction of L * . We let L * map the empty string to index 0 and for every other string σ we define L * (σ) as follows.
So it remains to define L * in steps, where at step n we define L * on all strings σ ∈ 2 h(n) .
Properties of L * . It remains to show (3), so let Z ∈ D * . First we show the claimed convergence and then that the limit is an index for f (Z). Let µ * := f (Z) and for each e define Since Z ∈ D * it follows that V learns µ * . Hence the µ * -measure of all the reals X such that lim s V(X ↾ s ) exists and equals an index of a measure with respect to which X is random, is 1. If we take into account that f (D) is effectively orthogonal, it follows that the µ * -measure of all the reals X such that lim s V(X ↾ s ) exists and equals an index of µ * is 1. Hence there exists an index t of µ * = f (Z) such that w t > 0, and moreover each e with w e > 0 is an index of µ * .
Lemma 3.1. For each e, lim n w e [n] = w e .
Proof. Since V learns µ * , the µ * -measure of the reals on which V reaches a limit is 1. For each n let Q n be the open set of reals on which V changes value after n bits. Then Q n+1 ⊆ Q n and lim n µ * (Q n ) = µ * (∩ n Q n ) = 0. Let P e [n] be the closed set for reals X such that V(X ↾ i ) = e for all i ≥ n. Then P e [n] ⊆ P e [n + 1] for all n and w e is the µ * -measure of ∪ n P e [n]. Hence w e = lim n µ * (P e [n]).
Given n 0 , for each n ≥ n 0 we have w e [n] ≤ µ * (P e [n 0 ]) + µ * (Q n 0 ). This shows that lim sup n w e [n] ≤ lim sup n µ * (P e [n]) = w e . On the other hand P e [n 0 ] ⊆ {σ ∈ 2 n | V(σ) = e)} for all n ≥ n 0 . So w e = lim n (µ * (P e [n])) ≤ lim inf n w e [n]. It follows that lim n w e [n] = w e . Now, given Z consider the sequence of computable measures µ Z↾ h(n) ∈ f * (Z ↾ h(n) ) that are defined by the function σ → µ σ applied on Z, and let From (4) we get that for each n, e, In particular, by Lemma 3.1, w e = lim n w e [n] = lim n w * e [n]. Let m be some index such that w m = max e w e . Lemma 3.2. There exists n 0 such that for all n ≥ n 0 and all e, |w e − w * e [n]| < w m /5.
Proof. By (6) we have e w e = 1 and 0 < w m ≤ 1. Then there exists e 0 such that e<e 0 w e > 1 − w m /20. And as we also have for all e, lim n w * e [n] = w e , then there exists n 0 such that for all n ≥ n 0 , e<e 0 |w e − w * e [n]| < w m /20. Then for e < e 0 , it is clear that for all n ≥ n 0 , |w e − w * e [n]| < w m /5. On the other hand, we have e≥e 0 w e = 1 − e<e 0 w e < w m /20. And for all n ≥ n 0 , e≥e 0 w * e [n] = 1 − e<e 0 w * e [n] ≤ 1 − ( e<e 0 w e − w m /20) < w m /10. So for all e ≥ e 0 , 0 ≤ w e < w m /20 and 0 ≤ w * e [n] < w m /10, and thus, |w e − w * e [n]| < w m /5.
Let us now fix the constant n 0 of Lemma 3.2.
Lemma 3.3 (The limit exists). The value of L * (Z ↾ n ) will converge to some index i with w i > 0.
Proof. Let L * (Z ↾ h(n 0 ) ) = e 0 . In case there is some n ≥ h(n 0 ) such that L * (Z ↾ n ) e 0 , there should be some n 1 ≥ n 0 such that L * (Z ↾ h(n 1 ) ) = e 1 e 0 . It then follows from the construction of L * that w * e 1 [n 1 ] ≥ w * m [n 1 ] > 4w m /5. Then by Lemma 3.2 for all n ≥ n 1 , w * e 1 [n] > w e 1 − w m /5 > w * e 1 [n 1 ] − 2w m /5 = 2w m /5 and on the other hand for all e, w * e [n] < w e + w m /5 ≤ 6w m /5 < 3w * e 1 [n]. This means that after step n 1 the value of L * (Z ↾ n ) will not change and thus, lim n L * (Z ↾ n ) = e 1 and w e 1 > 4w m /5 > 0. In case for all n ≥ h(n 0 ) we have L * (Z ↾ n ) = e 0 , then we only need to show that w e 0 > 0. Assume w e 0 = 0, then there will be some n 2 > n 0 such that for all n ≥ n 2 , w * e 0 [n] < w m /4. Noticed that w * m [n] > 4w m /5 > 3w * e 0 [n], by the construction of L * the value of L * (Z ↾ h(n 2 ) ) need to be changed. This is a contradiction.
The above lemma together with (6) concludes the proof of (3) and the 'only if' direction of Theorem 1.6.

From learning measures to learning reals: the BC case
We show the 'if' direction of the BC case of Theorem 1.6. So consider f : 2 ω → M, D, D * ⊆ 2 ω as given and assume that f (D * ) is a BC-learnable class of computable measures. This means that there exists a learner V such that for all µ ∈ f (D * ) and µ-random X there exists some s 0 such that for all s > s 0 the value of V(X ↾ s ) is an index of µ.
We use the expression lim n V(X ↾ n ) ≈ µ in order to denote property (8). Hence our hypothesis about V is for all µ ∈ f (D * ) and µ-random X we have lim n V(X ↾ n ) ≈ µ.
Proof idea. We would like to employ some kind of majority argument as we did in Section 3.2. The problem is that now, given Z ∈ D * , there is no way to assign weight on the various indices suggested by V, in a way that this weight can be consistently approximated. The reason for this is that V is only a BClearner and at each step the index guesses along the random reals with respect to µ * = f (Z) may change.
However there is a convergence in terms of the actual measures that the various indices represent, so we use a function that takes any number of indices, and as long as there is a majority with respect to the measures that these indices describe, it outputs an index of this majority measure. With this modification, the rest of the argument follows the structure of Section 3.2.
The formal argument. In the following we regard each partial computable measure µ e as a c.e. set of tuples (σ, I) such that I is a basic open set of [0, 1] and µ e (σ) ∈ I (see Section 2.1).
Definition 3.5 (Majority measures). Given a weighted set A and a partial computable measure µ, if the weight of A ∩ {e | µ e = µ} is more than 1/2 we say that µ is the majority partial computable measure of A.
Note that there can be at most one majority partial computable measure of a weighted set. In the case that µ of Definition 3.5 is total, we call it the majority measure of A.
Lemma 3.6. There is a computable function that maps any index of a weighted set A to an index of a partial computable measure µ with the property that if A has a majority partial computable measure ν then µ = ν. 21 Proof. Given a weighted set A we effectively define a partial computable measure µ and then verify its properties. We view partial computable measures as c.e. sets of tuples (σ, I) where σ ∈ 2 <ω and I is an open rational interval of [0, 1] and (σ, I) ∈ µ indicates that µ(σ) ∈ I. Define the weight of tuple (σ, I) to be the weight of {i ∈ A : (σ, I) ∈ µ i . Then define µ as the tuples (σ, I) of weight > 1/2.
It remains to verify that if A has a majority partial computable measure then µ is the majority partial computable measure of A. If ν is the majority partial computable measure of A it is clear that for each (σ, I) ∈ ν we have (σ, I) ∈ µ. Conversely, if (σ, I) ∈ µ, there would be a subset B ⊆ A of weight > 1/2 such that (σ, I) ∈ µ i for all i ∈ B. Since ν is the majority partial computable measure of A, it follows that there is an index of ν in B (otherwise the weight of A would exceed 1). Hence (σ, I) ∈ ν, which concludes the proof.
Recall the function g from (2). It suffices to show that there exists a computable function L * : 2 <ω → 2 <ω such that for each Z ∈ D * we have lim s L * (Z ↾ s ) ≈ f (Z) (10) because then the function L(σ) = g(L * (σ)) will be a computable BC-learner for D * .
Definition of L * . We let L * map the empty string to index 0 and for every other string σ we define L * (σ) as follows.
So it remains to define L * in steps, where at step n we define L * on all string σ ∈ 2 h(n) . Since f * (σ) is basic open interval in M so we may use (5) in order to get a computable function σ → µ σ from strings to computable measures, such that for each σ the measure µ σ belongs to f * (σ). Given n and σ ∈ 2 h(n) , for each e define wgt (e) = µ σ ({τ ∈ 2 n | V(τ) = e}).
Let A n be the weighted set of all e such that wgt (e) > 0 (clearly there are at most 2 n many such numbers e) where the weight of e ∈ A n is wgt (e). Then apply the computable function of Lemma 3.6 to A n and let L * (σ) be the resulting index.
Properties of L * . We show that L * satisfies (10), so let Z be a computable member of D * .
Proof. Since Z ∈ D * it follows that V learns µ * , hence w = 1. It remains to show that lim n w n = w. For each n let Q n be the open set of reals X with the property that there exists some t > n such that V(X ↾ t ) is not an index of µ * . Then Q n+1 ⊆ Q n and since V learns µ * we have lim n µ * (Q n ) = µ * (∩ n Q n ) = 0. Let P n be the closed set for reals X such that for all i ≥ n the value of V(X ↾ i ) is an index of µ * . Then P n ⊆ P n+1 for all n and w is the µ * -measure of ∪ n P n . Hence w = µ * (∪ n P n ) = lim n µ * (P n ).
Given n 0 , for each n ≥ n 0 we have w n ≤ µ * (P n 0 ) + µ * (Q n 0 ). This shows that lim sup n w n ≤ lim sup n µ * (P n ) = w e . On the other hand P n 0 ⊆ {σ ∈ 2 n | V(σ) is an index of µ * )} for all n ≥ n 0 . So w = lim n (µ * (P n )) ≤ lim inf n w n . It follows that lim n w n = w.
Lemma 3.8. For each Z ∈ D * , there exists some n 0 such that for all n > n 0 the value of L * (Z ↾ n ) is an index of f (Z) = µ * .
Proof. Given Z ∈ D * consider the definition of L * (Z ↾ h(n) ) during the various stages n, and the associated weighted sets A n . According to the construction of L * and Lemma 3.6 it suffices to show that there exists n 0 such that for all n > n 0 the weighted set A n in the definition of L * (Z ↾ h(n) ) has a majority measure which equals µ * .
Consider the sequence µ Z↾ h(n) ∈ f * (Z ↾ h(n) ) of computable measures that are defined by the function σ → µ σ applied on Z, and let w * n = µ Z↾ h(n) σ ∈ 2 n | V(σ) is an index of µ * ) . From (4) we get that for each n, |w n − w * n | < 2 −n . In particular, by Lemma 3.7, lim n w n = lim n w * n = 1. For (11) it suffices to consider any n 0 such that for all n > n 0 we have w * n > 1/2. Then by the construction of L * at step n and the definition of w * n it follows that for each n > n 0 , the majority measure of the weighted set A n is µ * .
Lemma 3.8 shows that L * satisfies (10), which concludes the BC case of the proof of the 'if' direction of Theorem 1.6.

From learning measures to learning reals: an extension
There is a way in which we can relax the hypotheses of the 'if' direction of Theorem 1.6 for EX-learning, which concerns the strength of learning as well as the orthogonality hypothesis.
Definition 3.9 (Partial EX-learnability of classes of computable measures). A class C of computable measures is partially EX-learnable if there exists a computable learner V : 2 <ω → N such that (a) C is weakly EX-learnable via V (recall Definition 1.3); (b) for every µ ∈ C there exists a µ-random X such that lim n V(X ↾ n ) is an index of µ.
The idea behind this notion is that not only for each µ ∈ C the learner eventually guesses a correct measure (possibly outside C) along each µ-random real, but in addition every measure µ ∈ C is represented as a response of the learner along some µ-random real.

Theorem 3.10 (An extension). Suppose that a computable function f : 2 ω → M is injective on an effectively closed set D ⊆ 2 ω , and D * ⊆ D is a set of computable reals. If f (D * ) is a partially EX-learnable class of computable measures then D * is an EX-learnable class of computable reals.
Proof idea. We would like to follow the argument of Section 3.2, but now we have a weaker assumption which allows the possibility that given Z ∈ D * , µ * = f (Z), there are indices e with positive weight, which do not describe µ * . In order to eliminate these guesses from the approximation n → L * (Z ↾ n ) to an index of f (Z), we compare how near the candidate measures are to our current approximation to µ * . Using this approach, combined with the crucial fact (to be proved) that indices with positive weight correspond to total measures, allows us to eliminate the incorrect total measures (eventually they will be contained in basic open sets that are disjoint from the open ball f (Z ↾ n ) containing f (Z)) and correctly approximate an index of µ * .
The formal argument. Recall the argument from Section 3.2 and note that (2) continues to hold under the hypotheses of Theorem 3.10. Hence it suffices to construct a computable L * : 2 <ω → N such that (3) holds. Since f (D * ) is a partially EX-learnable class of computable measures, there exists V with the properties of Definition 3.9 with respect to C := f (D * ).
Lemma 3.11. Every measure µ * ∈ f (D * ) has an index e such that lim n V(X ↾ n ) = e for a positive µ *measure of reals X.
Proof. Let µ * ∈ f (D * ) and consider a µ * -random X such that lim n V(X ↾ n ) is an index e of µ * . Consider the Σ 0 2 class F of reals Z with the property that lim n V(Z ↾ n ) = e. It remains to show that µ * (F ) > 0. Since F is the union of a sequence of Π 0 1 classes and X ∈ F , there exists a Π 0 1 class P ⊆ F which contains X. Since X is µ * -random, it follows that µ * (P) > 0, so µ * (F ) ≥ µ * (P) > 0.
Given µ * ∈ f (D * ) define w e , w e [n] as we did in Section 3.2. Note that Lemma 3.1 still holds by the same argument, since it only uses the hypotheses we presently have about D, f, V.
Lemma 3.12. For every µ * ∈ f (D * ) there exists an index e of µ * such that w e > 0. Conversely, if w e > 0 then e is an index of a computable measure µ ′ .
Proof. The first claim is Lemma 3.11. For the second claim, if w e > 0 it follows from clause (a) of Definition 3.9 applied on V that e is an index of a computable measure µ ′ such that all reals in some set Q with µ * (Q) = w e > 0 are µ ′ -random.
Let H be a partial computable predicate such that for every basic open set B of M and every e such that µ e is total, we have H(B, e) ↓ if and only if µ e B. 22 Hence if µ e is total then, ∃n H( f * (X ↾ n ), e)[n] ↓ ⇐⇒ µ e lim n f * (X ↾ n ).
where the suffix '[n]' indicates the state of H after n steps of computation.
Construction of L * . We let L * map the empty string to index 0 and for every other string σ we define L * (σ) as follows.
So it remains to define L * in steps, where at step n we define L * on all string σ ∈ 2 h(n) . Since f * (σ) is basic open interval in M so we may use (5) in order to get a computable function σ → µ σ from strings to computable measures, such that for each σ the measure µ σ belongs to f * (σ).
Properties of L * . We show that (3) holds, i.e. that for each Z ∈ D * the limit lim s L * (Z ↾ s ) exists and is an index for f (Z). Let Z ∈ D * , µ * = f (Z) and consider the sequence of computable measures µ Z↾ h(n) ∈ f * (Z ↾ h(n) ) that are defined by the function σ → µ σ applied on Z, and are used in the steps n of the definition of L * with respect to Z. Let w * e [n] = µ Z↾ h(n) {σ ∈ 2 n | V(σ) = e)} . and note that these are the weights used in the definition of L * at step n with respect to Z ↾ h(n) . Proof. The first equality is Lemma 3.1. From (4) we get that for each n, e, |w e [n] − w * e [n]| < 2 −n , which establishes the second equality.  Proof. As e w e = 1 and 0 < w m ≤ 1, then there exists e 0 such that e<e 0 w e > 1 − w m /20. And as we also have for all e, lim n w * e [n] = w e , then there exists n 0 such that for all n ≥ n 0 , e<e 0 |w e − w * e [n]| < w m /20. Then for e < e 0 , it is clear that for all n ≥ n 0 , |w e − w * e [n]| < w m /5. On the other hand, we have e≥e 0 w e = 1− e<e 0 w e < w m /20. And for all n ≥ n 0 , e≥e 0 w * e [n] = 1− e<e 0 w * e [n] ≤ 1−( e<e 0 w e −w m /20) < w m /10. So for all e ≥ e 0 , 0 ≤ w e < w m /20 and 0 ≤ w * e [n] < w m /10, and thus, |w e − w * e [n]| < w m /5. If w e > 4w m /5, clearly, it must be be case that e < e 0 , and thus, there are only finitely much such index e. For every such index e, if e T , then there will be some n e such that for all n ≥ n e H e [n] ↓. Let n 1 be the largest number among these n e and n 0 , and then n 1 is the number we need.
Let us now fix the constant n 0 of Lemma 3.14.
Lemma 3.15 (The limit exists). The value of L * (Z ↾ n ) will converge to some index i ∈ T .
Proof. Let L * (Z ↾ h(n 0 ) ) = e 0 . In case there is some n ≥ h(n 0 ) such that L * (Z ↾ n ) e 0 , then there should be some n 1 > n 0 such that L * (Z ↾ h(n 1 ) ) = e 1 e 0 . It then follows from the construction of L * that w * e ↓. This means that after step n 1 the value of L * (Z ↾ n ) will not change and thus, lim n L * (Z ↾ n ) = e 1 ∈ T . In case for all n ≥ h(n 0 ) we have L * (Z ↾ n ) = e 0 , then we only need to show that e 0 ∈ T . Assume e 0 T , then there exists some step n 2 ≥ n 0 such that H e 0 [n 2 ] ↓. As m ∈ T then for all n ≥ n 0 H m [n] ↑. By the construction of L * the value of L * (Z ↾ h(n 2 ) ) need to be changed. This is a contradiction.
The above lemma concludes the proof of Theorem 3.10.

Proof of Theorem 1.7
It is well known that if Z is computable and µ-random for some computable measure µ, then Z is an atom of µ and µ(Z ↾ n * Z(n))/µ(Z ↾ n ) tends to 1. Here is a generalization.
Proof. We prove the contrapositive: fix computable µ, Z, and suppose that for some Y there exists a rational q ∈ (0, 1) such that for infinitely many n. For each t consider the set V t of the strings of the form (Z ↾ j ⊕X ↾ j ) * Z( j) for some j, X, such that j is minimal with the property that there exist at least t many n ≤ j with (13) by replacing Y with X. For each nonempty string σ, let σ − denote the largest proper prefix of σ. By the minimality of the choice of n above, we have that (a) V t is prefix-free; (b) each string τ ∈ V t+1 extends a string σ is the set of all the strings in V t+1 extending σ ∈ V t then µ(V t+1 (σ)) < q · µ(σ). It follows that µ(V t+1 ) < q · µ(V t ) so there exists a computable sequence (m j ) such that µ(V m j ) < 2 − j for each j. So (V m j ) is a µ-test and by its definition, if Y satisfies (13) for infinitely many n, then Z ⊕ Y has a prefix in V t for each t, and so in V m j for each j. Hence in this case Z ⊕ Y is not µ-random.
Lemma 3.17. Given any computable Z, a real X is µ Z -random if and only if it is of the form Z ⊕ Y for some random Y with respect to the uniform measure.
So Y is not random with respect to the uniform measure.
Hence if Z X are computable, the measures µ Z , µ X are effectively orthogonal. Then the 'only if' direction of Theorem 1.7 follows from the 'only if' direction of Theorem 1.6 (with D := 2 ω and D * := C). The following concludes the proof of Theorem 1.7.

Lemma 3.18. For each class C of computable reals, if {µ Z | Z ∈ C} is a weakly EX/BC learnable class of measures then C is EX/BC learnable.
Proof. We first show the EX case. Fix C and let V be a learner which EX-succeeds on all measures in {µ Z | Z ∈ C}. It remains to construct an EX-learner L for C.
Proof idea. Given a computable Z, in order to define L(Z ↾ n ) we use V on the strings Z ↾ n ⊕σ, σ ∈ 2 n and take a majority vote in order to determine Z(n). According to Lemmas 3.16 and 3.17, eventually the correct value of Z(n) will be the j such that (Z ↾ n ⊕σ) * j gets most of the measure on (Z ↾ n ⊕σ), with respect to any measure correctly guessed by V(Z ↾ n ⊕σ), for the majority of σ ∈ 2 n .
Construction of L. First, define a computable g 0 : 2 <ω → N as follows, taking a majority vote via V. For each Z, n we define g 0 (Z ↾ n ) to be an index of the following partial computable real X. For each m < n we leet X(m) = Z(m). If m ≥ n, suppose inductively that it has already defined X ↾ m . In order to define X(m), it calculates the measure-indices V(X ↾ m ⊕σ) = e for all σ ∈ 2 m and waits until, for some j ∈ {0, 1}, at least 2/3 these partial computable measures µ e have the property µ e ((X ↾ n ⊕σ) * j) ↓> µ e (X ↾ n ⊕σ)/2. If and when this happens it defines X(m) = j.
Fix Z ∈ C. By Lemma 3.16, if V weakly EX-learns µ Z , for all sufficiently large n the value of g 0 (Z ↾ n ) will be an index of Z (possibly different for each n). In order to produce a stable guess, define the function L : 2 <ω → N as follows. In order to define L(Z ↾ n ), consider the least n 0 ≤ n such that (i) at least proportion 2/3 of the strings σ ∈ 2 n have not changed their V-guess since n 0 , i.e. V(Z ↾ i ⊕σ ↾ i ) = V(Z ↾ n 0 ⊕σ ↾ n 0 ) for all integers i ∈ (n 0 , n]; (ii) no disagreement between Z ↾ n and the reals defined by the indices L(Z ↾ i ), i ∈ (n 0 , n) has appeared up to stage n.
Then let L(Z ↾ n ) be g 0 (Z ↾ n 0 ). Given Z ∈ C we have that V weakly learns µ Z , so V(Z ↾ n ⊕Y ↾ n ) converges for almost all Y (with respect to the uniform measure). Hence in this case (i) will cease to apply for large enough n. Moreover by the properties of g 0 , clause (ii) will also cease to apply for sufficiently large n. Hence the n 0 in the definitions of L(Z ↾ n ) will stabilize for large enough n, and L(Z ↾ n ) will reach the limit g 0 (Z ↾ n 0 ) which is an index for Z.
For the BC case, assume instead that V BC-succeeds on all measures in {µ Z | Z ∈ C}. We define g 0 exactly as above, and the BC-learner L by L(Z ↾ n ) = g 0 (Z ↾ n ). Given Z ∈ C we have that V weakly BC-learns µ Z , so for almost all Y (with respect to the uniform measure), V(Z ↾ n ⊕Y ↾ n ) eventually outputs indices of a computable measure µ (dependent on Y ↾ n ) with the property that µ((Z ↾ n ⊕Y ↾ n ) * Z(n)) > 2/3 · µ(Z ↾ n ⊕Y ↾ n ). By the definition of g 0 , this means that for sufficiently large n, the value of L(Z ↾ n ) is an index of Z. Hence L is a BC-learner for C. Define the eth randomness deficiency function by setting d e (σ) to be ⌈− log µ e (σ)⌉ − K(σ) for each string σ, where K is the prefix-free complexity of σ. Define the eth randomness deficiency on a real X as: d e (X) = sup n d e (X ↾ n ) where the supremum is taken over the n such that d e (X ↾ n ) ↓. By [Levin, 1984], if µ e is total then X is µ e -random if and only if d e (X) < ∞.
At stage s, we define L(σ) for each σ of length s as follows. For the definition of L(σ) find the least i such that s is i-expansionary and d i (σ)[s] ≤ i. Then let j be the least such that p(i, j) is larger than any k-expansionary stage t < |σ| for any k < i such that d k (σ ↾ k )[t] ≤ k, and define L(σ t ) = p(i, j).
Let X be a real. Note that L(X ↾ n ) = x for infinitely many n, then x = p(i, j) for some i, j, which means that µ i = µ x is total and there are infinitely many x-expansionary stages as well as infinitely many i-expansionary stages. This implies that there are at most x many y-expansionary stages t for any y < x with d y (σ ↾ y )[t] ≤ y. Moreover for each z > x there are at most finitely may n such that L(X ↾ n ) = z. Indeed, for each z if n 0 is an i-expansionary stage then L(X ↾ n ) z for all n > n 0 . Moreover if L(X ↾ n ) = x for infinitely many n, then d x (X) = d i (X) ≤ i and µ i is total, so X is µ i -random. We have shown that for each X there exists at most one x such that L(X ↾ n ) = x for infinitely many n, and in this case µ x is total and X is µ x -random.
It remains to show that if X is µ-random for some computable µ, then there exists some x such that L(X ↾ n ) = x for infinitely many n. If X is µ i -random for some i such that µ i is total, let i be the least such number with the additional property that d i (X) ≤ i (which exists by the padding lemma). Also let j be the least number such that p(i, j) is larger than any stage t which is k-expansionary for any k < i with d k (σ ↾ k )[t] ≤ k. Then the construction will define L(X ↾ n ) = p(i, j) for each i-expansionary stage n after the last k-expansionary stage t for any k < i with d k (σ ↾ k )[t] ≤ k. We have shown that L partially succeeds on every µ-random X for any computable measure µ.

Applications
For the 'if' direction of Corollaries 1.9 and 1.11 we need the following lemma. Proof. We first show the part for the computable Bernoulli measures. The function which maps a real X ∈ 2 ω to the measure representation µ : 2 ω → R of the Bernoulli measure with success probability the real in R with binary expansion X is computable. Hence, given an effective list (µ e ) of all partial computable measures in M and an effective list (ϕ e ) of all partial computable reals in 2 ω , there exists a computable function g : N → N such that for each e such that ϕ e is total, µ g(e) is total and is the measure representation of the Bernoulli measure with success probability the real with binary expansion ϕ e . . We define an A-computable learner V as follows: for each σ let V(σ) be g(e) for the least index e ≤ |σ| which minimizes cost(e, σ) subject to the condition h(e, |σ|) = 1.
It remains to show that for each X ∈ 2 ω which is random with respect to a computable Bernoulli measure µ, lim n V(X ↾ n ) exists and equals an index of µ. According to our working assumption about X, there exist numbers e such that ϕ e is total and sup n cost(e, X ↾ n ) < ∞. These numbers e are the indices of reals in 2 ω which are the binary representations of the success probability of the Bernoulli measure with respect to which X is random. Now consider the least e with this property, and which minimizes sup n cost(e, X ↾ n ). Note that, by the definition of cost(e, σ), for each k, σ there are only finitely many e such that cost(e, σ) < k. It follows by the construction of V that lim n V(X ↾ n ) = e.
The proof for the class of all computable measures is the same as above, except that we take g to be the identity function.
For the other direction of Corollary 1.9, let C be the class of all computable reals, and assume that the computable measures are weakly EX[A]-learnable. Then {µ Z | Z ∈ C} is also weakly EX[A]-learnable, and by Theorem 1.7 we get that C is EX[A]-learnable. Then by [Adleman and Blum, 1991] it follows that A is high.

Applying Theorem 1.6 to classes of Bernoulli measures
Perhaps the most natural parametrization of measures on 2 ω by reals is the following.

Definition 4.2.
Consider the function f b : 2 ω → M mapping each X ∈ 2 ω to the Bernoulli measure with success probability the real whose binary expansion is X.
Clearly f b is computable, but it is not injective since dyadic reals have two different binary expansions. In order to mitigate this inconvenience, we consider the following transformation.

Lemma 4.6. If A ≤ T B ′ then every class of computable measures which is EX-learnable by A with finitely many queries, is also EX-learnable by B.
Proof. This is entirely similar to the analogous result for EX-learning of classes computable reals from [Fortnow et al., 1994]. By A ≤ T B ′ one can obtain a B-computable function that approximates A. Given an A-computable learner and replacing the oracle with the approximation given by B, the resulting learner will converge along every real on which the original learner converges and uses finitely many queries on A. Moreover in this case, the limit will agree with the limit with respect to the original A-computable learner. This shows that any class that is EX-learnable via the A-computable learner will also be EX-learned by the new B-computable learner. Now given an oracle A, by the jump-inversion theorem, since ∅ ′ ≤ T A ⊕ ∅ ′ , there exists some B such that B ′ ≡ T A ⊕ ∅ ′ . So A ≤ T B ′ . By Lemma 4.6, if the computable measures are EX-learnable with oracle A and finitely many queries, then it will also be EX-learnable by B. Then by Corollary 1.9 it follows that B is high, so B ′ ≥ T ∅ ′′ and ∅ ′′ ≤ T A ⊕ ∅ ′ as required.
Conversely, assume that ∅ ′′ ≤ T A⊕∅ ′ . Let (µ e ) be a universal enumeration of all partial computable measure representations with dyadic values and note that by the discussion of Section 2.1 it is sufficient to restrict our attention these measures, which may not include some measures with non-dyadic values. By Jocksuch [Jockusch, 1972] there exists a function h ≤ T A such that (µ h(e) ) is a universal enumeration of all total computable measure representations with dyadic values. The fact that uniformly computable families of measures are EX-learnable (originally from Vinanyi and Chater [Vitanyi and Chater, 2017]) relativizes to any oracle. Since (µ h(e) ) contains all computable measure representations with dyadic values, it follows that the class of all computable measures is EX-learnable with oracle A.

Conclusion and open questions
We have presented tools which allow to transfer many of the results of the theory of learning of integer functions or reals based on [Gold, 1967], to the theory of learning of probability distributions which was recently introduced in [Vitanyi and Chater, 2017] and studied in [Bienvenu et al., 2014[Bienvenu et al., , 2017. We demonstrated the usefulness of this result with numerous corollaries that provide parallels between the two learning theories. We also identified some differences; we found that although in the special case of effectively orthogonal classes, the notions of Definitions 1.1 and 1.2 are closed under the subset relation, in general they are not so. 24 We showed that the oracles needed for the EX-learning of the computable measures are exactly the oracles needed for the EX-learning of the computable reals, which are the high oracles. In the classic theory there exists no succinct characterization of the oracles that BC-learn the computable functions. On the other hand, Theorem 1.7 shows that if an oracle can BC-learn the class of computable (continuous) measures, then it can also BC-learn the class of computable functions.
Open problem. If an oracle can BC-learn the class of computable functions, is it necessarily the case that it can learn the class of computable (continuous) measures?
Another issue discussed is the low for EX-learning oracles for learning of measures. We showed that every such oracle is also low for EX-learning in the classical learning theory of reals. We do not know if the converse holds.