[37] Let be a computable measure on the sample space {0, 1}. Recall from Section 2.5 Martin-Lofs construction of a constructive -null set using

[37] Let μ be a computable measure on the sample space

{0, 1}∞. Recall from Section 2.5 Martin-L¨of’s construction of a constructive μ-null set using a notion of sequential test V with associated critical regions V1 ⊇ V2 ⊇··· of measures μ(Vi) ≤ 2−i

, for i ≥ 1. A constructive

μ-null set is a total computable μ-null set or Schnorr effective null set if, additionally, f(i) = μ(Vi) is a total computable function. Call an infinite sequence μ-random in the sense of Schnorr if it is not contained in any total computable μ-null set.

(a) Show that there is no universal total computable μ-null set that contains all others.

(b) Show that the set of sequences that are μ-random in the sense of Martin-L¨of is a subset of the set of sequences that are μ-random in the sense of Schnorr.

(c) An ω ∈ {0, 1}∞ is an atom with respect to μ if μ(ω) > 0. A measure

μ is called discrete if the set of atoms of μ has μ-measure one. (Obviously all atoms of computable μ are computable sequences.) Show that the Schnorr-μ-random sequences coincide with the Martin-L¨of-μ-random sequences iff μ is discrete.

Comments. Item

(c) implies that for continuous μ (such as the uniform measure), Schnorr randomness is weaker than Martin-L¨of randomness. The notion of total computable null sets is the computable analog of the intuitionistic notion of sets of measure zero by L.E.J. Brouwer

[A. Heyting, Intuitionism, an Introduction, North-Holland, 1956]. Sometimes the following statement is called Schnorr’s thesis: “A sequence behaves within all effective procedures like a μ-random sequence iff it is

μ-random in the sense of Schnorr.” Source: [C.P. Schnorr, pp. 193–211 in: R.E. Butts and J. Hintikka, eds., Basic Problems in Methodology and Linguistics, D. Reidel, 1977].