## Abstract

We study the notion of universality probability of a universal prefix-free machine, as introduced by C. S. Wallace. We show that it is random relative to the third iterate of the halting problem and determine its Turing degree and its place in the arithmetical hierarchy of complexity. Furthermore, we give a computational characterization of the real numbers that are universality probabilities of universal prefix-free machines.

## 1. Introduction

One of the most important discoveries of the twentieth century (especially on a conceptual level) is the notion of the universal computer—that is, a computer that can simulate any other computer. Turing [1] famously gave an abstract mathematical definition of the computer, also establishing the existence of universality. This notion turned out to play a fundamental role in the development of computing, both on a practical and on a theoretical level (see Davis [2], for a comprehensive history of the universal computer in the twentieth century). First, it led to the realization that the construction of *stored-program computers* (i.e. computers which can store *programs* and *data* in a uniform, interchangeable way) is possible. This, in turn, led to the development of the physical computer as we know it today, starting with the prototypes in the UK and USA during the Second World War. Second, it quickly led to the development of a rich theory of computation, which heavily rests on the existence of universal machines. The theory of Kolmogorov complexity is not an exception.

### (a) The role of universality in Kolmogorov complexity

Program-size complexity (also known as Kolmogorov complexity) was introduced by Kolmogorov [3] and Solomonoff [4] as a measure of complexity for programs (identified with binary strings) and was based on the following simple and appealing idea:
1.1
Kolmogorov and Solomonoff used the theory of Turing machines (which we also call simply ‘machines’) in order to express (1.1) (and, in particular, the notion of ‘description’) mathematically. If a machine *M* outputs string *τ* on input *σ* and then it halts (denoted by *M*(*σ*)=*τ*), then *σ* is called an *M*-description of *τ*. In other words, he required that descriptions are given in an algorithmic way. He then defined the complexity of a string *τ* with respect to machine *M* as the length of the shortest string *σ* such that *M*(*σ*)=*τ*. The existence of universal Turing machines allowed him to largely eliminate the dependency of this definition on the particular machine *M*, by defining the complexity with respect to a universal machine. Because the length of programs is a central concern in this theory, Kolmogorov thought of universal machines *U* as being able to simulate any other machine *with a constant overhead* in the required programs. In other words, for each machine *M*, there exists a constant *c* such that for all *σ* we have *U*(*ρ*)=*M*(*σ*) for some *ρ* which is longer than *σ* by no more than *c* bits.

Indeed, using this notion of universality, he could show that, if a different universal machine is chosen for the definition of complexity, the difference of the two complexities for any string is bounded by a constant. This means that the choice of a different underlying universal machine is like the choice of a different coordinate system in geometry, in the sense that it does not affect the theory. Kolmogorov's definition amounts to the following rather appealing formulation:
1.2
Indeed, one should take into account the size of the machine that is used to provide descriptions because a large machine may have quite complex strings hardwired into it. In other words, every string (however complex) is fairly simple with respect to *some* machine. In (1.1), the precise definition of the *size* of a machine is not essential. In addition, different formulations of the term ‘machine’ (e.g. different programming languages) produce a slight variation on the value of the complexity, which is entirely similar to the variation of the complexity according to the original formulation, when we use different underlying universal machines.

One of the main motivations of Kolmogorov for defining the complexity of programs was to give a definition of randomness of infinite binary sequences based on ‘incompressibility’ as follows. Let us say that a string *σ* is *c*-incompressible if it does not have a description that is shorter by *c* bits.
1.3
Unfortunately, Martin-Löf showed that, according to the notion of ‘description’ that Kolmogorov defined, there is no random infinite binary string in the sense of (1.3) (see Kolmogorov [5]). However, Levin [6] and Chaitin [7] provided a refinement of Kolmogorov complexity (and the definition of ‘description’) with respect to which (1.3) gives a very plausible mathematical counterpart to the intuitive notion of randomness. They observed that, given a string *σ*, one can extract information not only from the bits of *σ* *but also from its length*. Hence, the information that a string contains (measured in bits) is not reflected in the Kolmogorov complexity of the string (as we defined it earlier) but rather in the sum of this complexity with the information that is coded in the length of its shortest description.

Therefore, if we wish to define the complexity of a string as a reflection of the information that it contains (in terms of the number of bits), we need to use Turing machines that cannot use the length of a description in the computation of the string that is being described. Such machines are sometimes called *self-delimiting* because they operate with the restriction that the reading head moves only forward, and by the time they read the last bit of the input they have to halt. Such a modification does not allow the machine to scan the input and use its length as additional input information in computing the output. Moreover, they are equivalent to the so-called *prefix-free machines*—i.e. machines whose domain is prefix free (i.e. there is no string such that both it and a proper extension of it belong to the domain). Such a modification gives the so-called *prefix-free complexity* (defined as mentioned earlier, but with prefix-free machines instead of plain Turing machines), which is not only a motivated refinement of Kolmogorov complexity but also allows the development of a theory of randomness for infinite binary strings based on Kolmogorov's original proposal (1.3).

In fact, Martin-Löf [8] had already given a definitive mathematical definition of a random (infinite) sequence long before the developments of Levin [6] and Chaitin [7]. He followed a measure-theoretic approach by specifying a canonical countable family of null sets in the space of infinite binary sequences (with the uniform measure) and calling a sequence random when it does not belong to any member of this family. This family is the collection of effectively null sets, i.e. sets of the form ∩_{j}*U*_{j} where (*U*_{j}) is a uniform sequence of classes such that *μ*(*U*_{j})<2^{−j−1}. The idea behind this definition is that each member of the canonical family represents a stochastic test that looks for special properties of sequences. The sequences that have algorithmically special features will belong to a member of this family; hence they will not be random; and vice versa. These sequences are called Martin-Löf random.

Schnorr (see Chaitin [7]) showed a sequence is Martin-Löf random if and only if it is random according to the approach of Kolmogorov (based on (1.3) and the use of prefix-free machines). In other words, if we let *K*(*σ*) denote the prefix-free complexity of *σ* (with respect to a fixed underlying universal prefix-free machine), then an infinite binary sequence *X* is Martin-Löf random if and only if for some constant *c* and all . In other words, if for each the first *n* bits of *X* cannot be compressed by more than *c* bits.

The approaches of Martin-Löf and Kolmogorov should not be viewed as fixed definitions of randomness of infinite binary sequences but rather as a framework in which we can calibrate and study randomness of various strengths. For example, we can introduce parameters in the basic definitions that we discussed earlier, in the form of oracles in the underlying machines. This *relativization* provides natural equivalent definitions of the notion of an infinite binary sequence *X* being random relative to an infinite binary sequence *Y* . In particular, if *X* is random relative to ∅^{(n)} (the halting problem iterated *n* times), then we call it *n*+1-random.^{1} This, in turn, provides a natural hierarchy of randomness notions. For a more detailed discussion of the basic concepts and results of algorithmic randomness (of strings and infinite sequences), we refer the reader to Nies [9], ch. 2 and 3 and for a more elaborate history of the subject we refer to Li & Vitányi [10], Zvonkin & Levin [11] and van Lambalgen [12].

### (b) Random numbers as probabilities of universal prefix-free machines

Intuitively, random streams (i.e. infinite binary sequences) are very typical and have no special features that distinguish them. Despite this, Chaitin [7] showed that ‘natural’ examples of random streams can be obtained by considering a certain probability related to any given universal prefix-free machine. This probability was first introduced by Zvonkin & Levin [11]. Of course, probabilities are real numbers between 0 and 1, but we can easily identify them with streams if we consider their binary expansion (which is unique, if the number is irrational). Hence, we can talk about *random real numbers* and, in this fashion, we may refer to the elements of the Cantor space 2^{ω} (the set of infinite binary sequences) as *reals*.

Chaitin considered the situation where random bits are fed as an input to a universal prefix-free machine *U* one after the other, until (if ever) the machine halts on the input consisting of the random bits that we provided. He then considered the probability *Ω*_{U} that the machine will eventually halt in such an experiment, which he called the *halting probability of the machine* *U*. This is given by
1.4
where the sum is taken over all strings on which *U* halts. Chaitin [7] showed that the halting probability of any universal machine is a random number, thus providing concrete examples of randomness. Another feature of these numbers is that they can be approximated by an increasing computable sequence of rational numbers, and this can be seen from (1.4). Such real numbers are called *left computably enumerable*, or *left c.e.* for short. Similarly, a real number is *right c.e.* if it is the limit of a decreasing computable sequence of rational numbers.

By the cumulative effort of Solovay [13], later Calude *et al.* [14] and finally Kučera & Slaman [15], a characterization of the reals that are halting probabilities of universal prefix-free machines was obtained. It was shown that a real number has this property exactly when it is a random c.e. real. A nice and concise proof of this was described by Downey & Hirshfeldt [16], §9.2 (we will make essential use of the methods that are discussed there in our technical arguments in §§4 and 5).

We may obtain more highly random numbers if we consider a universal prefix-free machine that works with an oracle *X*. Then, the halting probability *Ω*^{X} of this machine will be random relative to *X*. By increasing the complexity of *X*, the level of randomness of *Ω*^{X} is also increased accordingly. Such probabilities *Ω*^{X} were studied thoroughly in the study of Downey *et al.* [17] (we make use of some of the results in that paper in §3).

On the other hand, there have been attempts to obtain highly random numbers without the use of oracle machines. In Becher & Chaitin [18], a number that is random relative to ∅^{(2)} was obtained as the probability that a universal prefix-free machine outputs an infinite stream with only finitely many 0s, during an infinite computation. In Becher and co-workers [19,20], such numbers are obtained as probabilities that a universal prefix-free machine outputs a string that belongs to a complicated set. For example, in Becher *et al.* [19], the numbers
1.5
were studied, where *U* is a universal prefix-free machine and *X* is a given set. This work was extended in Becher & Grigorieff [20], where it was shown that for each *n*≥1 the number in (1.5) is *n*-random whenever *X* is partial many-one -complete.^{2}

However, one may argue that the above-mentioned examples of highly random numbers are not entirely ‘natural’, as they directly depend on auxiliary sets that are well known to have high complexity from computability theory (via diagonalization arguments). In this paper, we provide a natural example of a highly random number (random relative to ∅^{(3)}) that directly reflects a probability of a universal machine related with universality and does not depend on external parameters. Moreover, as we explain in §1*d*, it was originally defined by Wallace without the intention of exhibiting a random number (he believed it was zero).

### (c) Universality variations for prefix-free machines

The notion of a universal machine in Kolmogorov complexity was defined in §1*a*. However, there is more than one way to define it, and not all of them are equivalent. In this section, we give two standard notions of universality: a strong one and a weaker one, and discuss their differences. At this point, our discussion becomes more mathematical; so let us clarify the terminology and notations that we use. By ‘machine’, we mean *Turing machine* with domain a subset of the set 2^{<ω} of finite binary strings. The output of the machines is also a subset of 2^{<ω}. If *M*,*N* are two machines, then we write *M*(*σ*)=*N*(*τ*) if either both *M*(*σ*) and *N*(*τ*) converge to the same value, or both of them diverge. We use ⊆ to denote the prefix relation on strings (as well as the subset relation, when the variables range over sets).

The standard way to define a universal prefix-free machine is to make it simulate any other machine via a *constant* overhead. The standard example is the machine *U*(0^{e}1*σ*)=*M*_{e}(*σ*), where (*M*_{e}) is an effective enumeration of all prefix-free machines. Machines with this property will simply be called *universal* from now on. Moreover, the operation of concatenation on strings will often be denoted by ‘*’.

### Definition 1.1 (universality)

A prefix-free machine *U* is called *universal* if for each prefix-free machine *M* there is a string *τ* such that *M*(*σ*)=*U*(*τ***σ*) for all strings *σ*.

Occasionally, a more general notion of universality is used in Kolmogorov complexity, which is the one we mentioned in §1*a*. This is when we merely require the simulation to take place with *at most a constant overhead*. This turns out to be an essential requirement for a machine to be called universal. Indeed, let *K*_{V} denote the prefix-free complexity with respect to machine *V* . In Kolmogorov complexity, a basic requirement for an underlying prefix-free machine *U* (with respect to which we measure the complexity of strings) is that, for each prefix-free machine *M*, there exists a constant *c* such that *K*_{U}(*σ*)≤*K*_{M}(*σ*)+*c* for all strings *σ*. Such machines are often called ‘(additively) optimal’ [10], definition 2.0.1 because, modulo a constant, they produce the shortest descriptions compared with any other prefix-free machine. An equivalent way to express this property is as follows.

### Definition 1.2 (weak universality)

A prefix-free machine *U* is called weakly universal if for each prefix-free machine *M* there is a constant *c* such that, for each string *σ*, we have *M*(*σ*)=*U*(*τ*) for some string *τ* with |*τ*|≤|*σ*|+*c*.

In some papers, e.g. Figueira *et al.* [21], definition 1, universal machines are called *universal by adjunction*, reserving the term ‘universal’ for weakly universal machines in terms of definition 1.2. The easiest way to produce a weakly universal prefix-free machine is to make it universal. However, not all weakly universal machines are universal. In fact, sometimes this distinction matters, as it does in various results in Figueira *et al.* [21].

In our paper, we deal with both notions of universality, but the case of weak universality tends to be less interesting (with respect to the notions that we study). Indeed, as we see in §2, the notion of *universality probability*—the main object of study in this paper—becomes less robust when it is considered with respect to weakly universal machines. Moreover, the question of Wallace that motivated this work (see §1*d*) referred to the stronger notion of universality. For these reasons, we are mainly concerned with the notion of definition 1.1.

### (d) Universality probability of a machine and a question of C. S. Wallace

Wallace was a physicist and statistician at Monash University, Clayton, Australia, who developed a strong interest in information theory and in particular the *minimum message length* (MML) approach to inductive inference, learning theory and the complexity of programs. His work on this topic, much of which is discussed in his book [22], was heavily influenced by ideas and methods in machine learning, statistics, econometrics, inductive inference and philosophy. See Dowe [23] for a survey of Wallace's work as well as Wallace & Dowe [24] for a comparison of MML with Kolmogorov complexity.

Wallace was interested in the notion of a real *preserving universality* with respect to a prefix-free machine, and in particular the probability of this event (see Dowe [23], §0.2.2, p. 530, column 1 and footnote 70 and [25], §2.5, p. 913).

### Definition 1.3 (preserving universality)

A real *X* *preserves* [*weak*] *universality* with respect to a prefix-free machine *M*, if all machines , are [weakly] universal.

The *universality probability* of a prefix-free machine *M* is the measure of the reals that preserve universality with respect to *M*. Clearly, if *M* is not universal, then it has universality probability 0. In §2, we will see that the converse is also true.

The philosophical motivation of Wallace for considering these notions was his intuition that (vaguely speaking)
In other words, he believed that the universality probability of any machine is 0. This conjecture was the starting point and the main motivation for this project. In §2, we refute it, showing that for a universal machine it is always a number strictly between 0 and 1. After this basic result was obtained, we wished to obtain various logical and computational properties of these numbers such as their arithmetical complexity and their Turing degree. Ultimately, we characterized them as the reals that are random relative to ∅^{(3)} and right c.e. relative to the same oracle. On the basis of this main result and various results from the literature, we calculated the exact place of these numbers in the arithmetical hierarchy of complexity and showed that their Turing degrees vary with the choice of the underlying universal prefix-free machine. The latter corollary contrasts with the fact that the halting probabilities of universal prefix-free machines all have the same Turing degree (the degree of the halting problem). These results are stated in detail in §3, and the more technical arguments are deferred until §§4 and 5.

The characterization of universality probabilities has the same spirit as the characterization of halting probabilities from earlier studies [13–15] that we discussed in §1*b*. In fact, in a certain sense, the two probabilities are complementary as we show in §3 (corollary 3.5). Moreover, the characterization of universality probabilities is considerably harder to obtain than the case of halting probabilities because we deal with 4-quantifier complexity as opposed to the 1-quantifier complexity of the halting probabilities. The additional obstacles stem from the fact that this notion does not have counterparts in lower arithmetical levels and this lack of inductive structure forces us to work directly on the computable level with the aim of meeting conditions on the fourth level of arithmetical complexity (instead of transferring a simpler argument of a lower level to the fourth level by the use of parameters and an inductive step). As consequence, the main argument of §4 does not involve oracle computations. The specific novelties and obstacles to this argument are detailed throughout §4. Note, however, that oracle computations are used in §§3 and 5 in order to derive further properties of the universality probabilities, from the main result and a wealth of results from the literature. Moreover, the techniques used in the easier case of halting probabilities are fully utilized in our arguments.

## 2. Basic properties of universality probability

It will be useful to discuss the complexity of the class of reals that preserve [weak] universality (with respect to some machine *M*). Notice that if *M* is not universal, then this class is empty. Let (*V*_{e}) be a standard list of all prefix-free machines. The number *e* is said to be an index of the machine *V*_{e}. Notice that we use natural numbers to index machines, instead of strings. Let *P*(*e*,*n*,*τ*,*σ*,*s*) be the computable predicate that *V*_{e}(*τ***σ*)[*s*]=*V*_{n}(*σ*)[*s*] (where the suffix [*s*] indicates the state of the machine after it has performed *s* steps). Then, the property that machine *e* is universal can be expressed by the predicate ∀*n*∃*τ*∀*σ*,*t*∃*s*>*t*, *P*(*e*,*n*,*τ*,*σ*,*s*). Similarly, the property that machine *e* is weakly universal can be expressed by the predicate ∀*n*∃*c*∀*σ*,*t*∃*s*>*t*,*τ*[|*τ*|≤|*σ*|+*c*∧*P*(*e*,*n*,*τ*,*σ*,*s*)]. However, the variables in *P* are not entirely ‘independent’ (e.g. if *V*_{e}(*τ*)↓ this affects *P* on all variables *σ*). For this reason, the set of indices of [weakly] universal machines has lower complexity.

### Proposition 2.1 (folklore)

*The set of indices of the [weakly] universal prefix-free machines is* -*complete*.

### Proof.

Let *P* be as in the above-mentioned discussion and let *n* be the index of a fixed universal machine. Then, the programs *e* that can simulate any other program (in the sense of definition 1.1) are exactly the ones that can simulate *V*_{n}. Hence, *V*_{e} is universal if and only if
2.1
Therefore, they form a set. Similarly, the programs *e* that can weakly simulate any other program (in the sense of definition 1.2) are exactly those that can weakly simulate *V*_{n}. Hence, *V*_{e} is weakly universal if and only if
2.2
Therefore, they too form a set.

In order to show that (2.1) and (2.2) are -complete, let *Q*(*e*,*t*,*k*,*s*) be a computable relation such that the predicate ∃*t*∀*k*∃*s* *Q*(*e*,*t*,*k*,*s*) is -complete. Let (*τ*_{i}) be an infinite computable prefix-free sequence of strings. Then for each *e*, we can make a program *f*(*e*) such that
2.3
for each and all strings in the domain of *V*_{f(e)} extend some . This is simply carried out by expressing the predicate ∀*k*∃*s* *Q*(*e*,*t*,*k*,*s*) as the of a computable function *g* with binary values, and updating the *V*_{f(e)}-simulation of *V*_{n} on extensions of *τ*_{t} at stages *s* where *g*(*s*)=1. By (2.3) (and the fact that all *V*_{f(e)}-computations are enumerated on strings that are prefixed by some *τ*_{i}, ), we have that
Because *f* is computable, it follows that the predicates in (2.1) and (2.2) are -complete.

The proof of proposition 2.1 may be useful to some readers as an introduction to the spirit of the main arguments in §§4 and 5.

It is not hard to see that the class of reals that preserve [weak] universality (with respect to some machine *M*) can be represented as the class of infinite paths through a ∅^{(3)}-computable tree *T*. Indeed, let *N* be a universal prefix-free machine and let
2.4
Clearly, *T* is a tree (i.e. a downward closed set of strings) and, because the predicate in the second clause of the equivalence in (2.4) is computable from ∅^{(3)}, it is computable from this oracle. Moreover, by definition, a real preserves universality with respect to *M* if and only if it is a path through *T*. Similar observations apply for the case of weak universality. Therefore, we have the following:
2.5
In this paper, we are mainly interested in the measure of the class of (2.5), in the non-trivial case when *M* is a universal machine. We will first show that this measure is always positive and then that it is always a 4-random number (i.e. random relative to ∅^{(3)}). The case of weak universality turns out to be less robust and less interesting.

### Proposition 2.2

*There exists a weakly universal machine* *V* *that does not preserve weak universality with respect to any real*.

### Proof.

Let *U* be a universal machine. For each string *σ*, if *U*(*σ*)=*τ* let *V* (*j***σ*)=*τ*, where *j* is 0 or 1 according to whether |*τ*| is even or odd, respectively. Clearly, *V* is weakly universal. However, for each non-empty string *ρ*, the machine *M*_{ρ}(*σ*):= *V* (*ρ***σ*) is not weakly universal. Indeed, if the first digit of *ρ* is 1, then *M*_{ρ} gives descriptions to only strings of odd length. Similarly, if the first digit of *ρ* is 0, then it gives descriptions to only strings of even length. This shows that no real preserves weak universality with respect to *V* .

On the other hand, theorem 2.4 shows that some machines preserve [weak] universality with respect to a set of reals of positive measure. Our last comment about weak universality is in lemma 3.2, where we show that, for some machines *V*, the measure of reals that preserve weak universality with respect to *V* is 4-random. From now on, we focus on the case of universality (in the sense of definition 1.1).

### Definition 2.3 (universality probability)

The [weak] *universality probability* of *M*, denoted by *P*_{M} (denoted by *P*^{w}_{M}), is the measure of all reals that preserve [weak] universality with respect to *M*.

A related notion is the halting probability *Ω*_{M} of a machine *M* that was introduced by Chaitin [7]. In order to draw an analogy with definitions 1.3 and 2.3, we say that a prefix-free machine *M* halts on a real *X* if it halts on some initial segment of *X*. Then, *Ω*_{M} is the measure of all reals *X* on which the machine *M* halts and is expressed formally as . If *U* is a universal machine, then clearly *Ω*_{U}>0. In addition, *P*^{w}_{U}≤1−*Ω*_{U} because, if *U* halts on some input, no real extending that input can preserve universality. Hence, *P*^{w}_{U}<1 for every universal machine *U*. We wish to show that we also have *P*_{U}>0 and *P*^{w}_{U}>0. It suffices to construct a universal machine *V* such that *P*_{V}>0. Indeed, then we argue that *P*_{U}>0 (hence *P*^{w}_{U}>0) as follows. Because *U* is universal, there is some *τ* such that *V* (*σ*)=*U*(*τ***σ*) for all strings *σ*. Then, for every *X* that preserves universality with respect to *V* , the sequence *τ***X* preserves universality with respect to *U*. Therefore, *P*_{U}≥2^{−|τ|}⋅*P*_{V}>0. The proof of the following theorem sets the basis for the more complex arguments of §§4 and 5.

### Theorem 2.4

*The universality probability of any universal machine is strictly between 0 and 1.*

### Proof.

As we explained already, for the proof of the theorem it suffices to construct a universal machine *V* such that *P*_{V}>0. In order to achieve this, we will enumerate a class *Q* of measure <1, such that every real in the class 2^{ω}−*Q* preserves universality by adjunction (with respect to *V*). Obviously, *Q* will contain the domain of *V* , i.e. the sequences on which *V* halts.

Let *U* be a universal prefix-free machine. The machine *V* will be constructed through an iteration of *U* on various cylinders [*σ*]:={*X*∈2^{ω}|*σ*⊂*X*}. In what follows, we identify strings *σ* with the corresponding basic open sets [*σ*] of the Cantor space 2^{ω}. In addition, we identify sets *Q*[*s*] of strings with the corresponding open sets of the space, consisting of the sequences extending one of the strings in *Q*[*s*]. Let *Q*[0]=∅.

*Construction.* At stage *s*+1, consider the set *C*[*s*] of strings *σ* of length *s* such that [*σ*]⊈*Q*[*s*]. For each *σ*∈*C*[*s*], do the following. Find a string *τ* of length >2*s*+2 extending *σ* which has no prefix in *Q*[*s*]. Let *V* (*τ***ρ*):=*U*(*ρ*) for all strings *ρ*. Put *τ* in *Q*[*s*+1].

*Verification.* First, note that the sets *Q*[*s*] are clopen; therefore, the string *τ* will always be found in the construction for each *σ* of length *s* such that [*σ*]⊈*Q*[*s*]. So, the construction is well defined. In addition, by the construction we have *V* (*τ*)[*s*]↓ for some string *τ* only if some prefix of *τ* is in *Q*[*s*]. Therefore, the new definitions of *V* at each stage are enumerated in cylinders [*σ*] where there is no previous convergence of *V* . So, *V* is a consistent and prefix-free Turing machine.

Now let *Q*:=∪_{s}*Q*[*s*] and suppose that *X*∈2^{ω}−*Q*. Then, by the construction, we have for all . Therefore, *X* preserves universality with respect to *V* . It remains to show that *μ*(*Q*)<1. Notice that *C*[*s*] consists of at most 2^{s} strings at each stage *s*. By the way we choose the strings in *Q*[*s*+1] from *C*[*s*] (for each string of length *s*, we choose at most one extension of it of length 2*s*+2), we have that *μ*(*Q*[*s*+1]−*Q*[*s*])≤2^{−s−2}. Because *Q*=∪_{s}*Q*[*s*], we have *μ*(*Q*)<1.

In the proof of theorem 2.4, we constructed a universal machine *V* and a class *P* of positive measure such that every real in *P* preserves universality with respect to *V* . If *U* is a universal machine, there exists *τ* such that *V* (*σ*)=*U*(*τ***σ*) for all strings *σ*. Therefore, all reals in the class *P*_{*}={*τ***X*|*X*∈*P*} preserve universality with respect to *U*. Moreover, *μ*(*P*_{*})=2^{−|τ|}⋅*μ*(*P*)>0; so we have the following.

### Corollary 2.5

*Given a universal machine* *U*, *there exists a* *class* *P of positive measure such that all reals in* *P* *preserve universality with respect to* *U*.

A result of Kučera [26] says that if *P* is a class of positive measure, then every Martin-Löf random sequence has a final segment in *P*. Therefore, we have the following consequence.

### Corollary 2.6

*If* *U* *is a universal prefix-free machine and* *X* *a Martin-Löf random sequence, then some final segment of* *X* *preserves universality with respect to* *U*.

In the proof of theorem 2.4, by modifying the number 2*s*+2 in the construction, we can clearly make sure that the measure of the class *Q* is arbitrarily small. Hence, we can make sure that *P*_{V} is as close to 1 as we wish. Similarly, by choosing the domain of *V* to have suitably large measure, we can ensure that *P*_{V} is as close to 0 as we wish. Moreover, recall that the machine *V* that is built is universal. Therefore, we have the following consequence of the argument in the proof of theorem 2.4.

### Corollary 2.7

*If* *U* *ranges over the universal prefix-free machines, then we have* *and* .

Typical reals in the sense of Baire category are called *generic*. These are the sequences that meet every ‘definable’ dense set of strings. Various interpretations of ‘definable’ yield various levels of genericity. One of the weakest such notions is 1-*genericity*. A real *X* is 1-generic if every set of strings that is dense along *X* (i.e. *X* is an accumulation point of the neighbourhoods in the set) has a prefix of *X*. The following observation contrasts corollary 2.6.

### Proposition 2.8

*If* *M* *is a prefix-free machine and* *X* *is a 1-generic real, then* *X* *does not preserve universality with respect to* *M*. *Hence, the set of reals that preserve universality with respect to a prefix-free machine is a meagre set*.

### Proof.

If a real *X* preserves universality with respect to *M*, then the domain of *M* is a set of strings that is dense along *X*. Moreover, no prefix of *X* is in the domain of *M*. This means that in this case *X* cannot be 1-generic. Because the set of 1-generic reals is a co-meagre set, the set of reals that preserve universality with respect to *M* is meagre.

An easy modification of the proof of theorem 2.4 yields the following observation.

### Proposition 2.9

*Every computable real preserves universality with respect to some prefix-free machine* *V* . *Hence, for every computable real* *X* *and any universal prefix-free machine* *U*, *some finite variation* *σ***X* *of* *X* *preserves universality with respect to* *U*.

On the other hand, for each computable real *X*, there exists a universal prefix-free machine *U* with respect to which *X* does not preserve [weak] universality.

The ideas presented in the proof of theorem 2.4 will be used in the latter sections in order to obtain more advanced results on the universality probability. On the other hand, there is a simpler proof of it (and its corollaries) that was suggested to us by Leonid Levin.

*Levin's example*. Let *U* be a standard universal prefix-free machine and let *c* be a constant such that for some real *X*. Let *N*_{c} be the c.e. set of strings *σ* such that *K*(*σ*)≤|*σ*|−*c*. Fix a computable enumeration of *N*_{c} in which at most one string is enumerated at each stage. Define a new machine *M* as follows. At stage *s*+1, set *M*(*σ***τ*)=*U*(*τ*) for all *τ*, unless there are some *ρ*∈*N*_{c}[*s*] that are compatible with *σ*. It is not hard to check that *M* is well defined and prefix free. Because every string has extensions in *N*_{c}, every real *X* with no prefixes in *N*_{c} preserves universality. Hence, *M* has positive universality probability.

The halting probability of a universal prefix-free machine *Ω* stands out as a rather special random number. One can obtain more highly random numbers by relativizing *Ω*. For example, *Ω*^{∅′} (the halting probability of a universal prefix-free machine with oracle ∅′) is random relative to ∅′, i.e. 2-random. There is another way to obtain highly random numbers through *Ω*, without relativization. Such methodologies were explored in earlier studies [18–20]. For example, in Becher *et al.* [19], the numbers (1.5) were studied where *U* is a universal prefix-free machine and *X* is a given set. This work was extended in Becher & Grigorieff [20], where it was shown that for each *n*≥1 the number in (1.5) is *n*-random whenever *X* is partial many-one -complete (see footnote 2). In §3, we show that universality probabilities are natural examples of highly random numbers.

## 3. Randomness of universality probability

In this section, we wish to show that the universality probability of a universal prefix-free machine is a random number. In fact, we will show that it is 4-random, i.e. random relative to ∅^{(3)}. Following the methodology in the proof of theorem 2.4, we construct a prefix-free machine *V* with special properties. For every string *τ*, let [*τ*] denote the class of infinite binary extensions of *τ*. If *S* is a set of strings, then let [*S*] denote the union of all [*τ*] for *τ*∈*S*. Recall that open sets in the Cantor space are of the form [*S*] for some set of strings *S*. If an open set can be represented by a computably enumerable set of strings, then it is called .

### Lemma 3.1 (special machines)

*Given any* *set of strings* *J*, *there is a universal prefix-free machine* *V* *and a c.e. set of strings* *Q* *such that*:

*A real in 2*^{ω}−[*Q*]*preserves [weak] universality with respect to**V**if and only if it does not have a prefix in**J*.*The measure of*[*Q*]*is computable and at most 2*^{−e}.*the measure of the reals in*[*Q*]*that preserve [weak] universality with respect to**V**can be*∅^{(3)}-*approximated from above*.

*Moreover, the programs for* *V*, *Q*, *μ*(*Q*) *can be effectively obtained from a* *index of* *J* and *e*.

The proof of lemma 3.1 is the main technical argument needed for theorem 3.3 and is presented in §4. Lemma 3.2 shows that the universality probability of one of the machines obtained in lemma 3.1 is a 4-random number.

### Lemma 3.2 (universality probability of a special machine)

*There is a prefix-free machine whose [weak] universality probability is random relative to* ∅^{(4)}.

### Proof.

Let *J* be the second member of a universal Martin-Löf test relative to ∅^{(3)}, so that *μ*([*J*])<2^{−2} and every infinite sequence that is not 4-random has a prefix in *J*. We show that the corresponding machine *V* of lemma 3.1 for *e*=2 has the desired property. Let *Q* be the c.e. set that is produced as in lemma 3.1. By the choice of *J*,*e*,*V* we have

there are reals in 2

^{ω}−[*Q*] that preserve universality with respect to*V*every real in 2

^{ω}−[*Q*] that preserves [weak] universality with respect to*V*is 4-randomthe measure of the reals in [

*Q*] that preserve [weak] universality with respect to*V*can be ∅^{(3)}-approximated from above.

Recall that the measure of a class is a right-c.e. real and, similarly, the measure of a class (where *X* is some oracle) is a right-c.e. real relative to *X*. By Nies [9], theorem 3.2.35, the measure of a class that contains only 1-random reals is a 1-random real. A direct relativization of this fact gives the following analogous result:
3.1
Because the class [*Q*] is , by (2.5) the class of reals in 2^{ω}−[*Q*] that preserve [weak] universality with respect to *V* is a class. Then, by item (ii) of the proof of lemma 3.2 and (3.1) we have (3.2).
3.2
On the other hand, by Downey & Hirshfeldt [16], theorem 8.7.2, the sum of a right-c.e. real with a 1-random right-c.e. real is a 1-random right-c.e. real. A direct relativization of this results shows (3.3).
3.3
Hence, it remains to show that the measure of the class of reals in [*Q*] that preserve [weak] universality with respect to *V* is a right-c.e. real relative to ∅^{(3)}. But this is item (iii) in the proof of lemma 3.2. Hence, the [weak] universality probability of *V* is the sum of the number in (3.2) and a right-c.e. real relative to ∅^{(3)}. By (3.3), it is 4-random and right c.e. relative to ∅^{(3)}.

Note that, in lemma 3.1, it is not claimed that the class of reals in *Q* that preserve universality with respect to *V* is a class. In fact, this will be a class but its measure will be merely right c.e. relative to ∅^{(3)} (see §4).

### Theorem 3.3

*The universality probability of a universal prefix-free machine is 4-random and right c.e. relative to ∅*^{(3)}*.*

### Proof.

Consider the machine *V* of lemma 3.2 with universality probability *P*_{V}. Given any universal machine *U*, there is a string *τ* such that *V* (*ρ*)=*U*(*τ***ρ*) for all strings *ρ*. Let be the class of reals that preserve universality with respect to *U* and for each string *σ* of length |*τ*| consider the class . The measure of is 2^{−|τ|}⋅*P*_{V}; so by lemma 3.2 it is a 4-random right-c.e. relative to ∅^{(3)} number. Moreover, the classes are so their measures are right c.e. relative to ∅^{(3)}. The measure of is the finite sum of the measures of the classes for the strings *σ* of length |*τ*|. By (3.3), this is a 4-random right-c.e. relative to ∅^{(3)} number.

We also wish to give a characterization of the real numbers that are the universality probability of some universal prefix-free machine. For the halting probabilities of universal prefix-free machines, such a characterization is well known and was obtained by the cumulative work of several authors [13–15] (for a simplified presentation, we recommend Downey & Hirshfeldt [16], §9.2).
3.4
By Downey *et al.* [17], §2, the above-mentioned result relativizes to any oracle, so that the following holds for each :
3.5
In Kučera & Slaman [15], it was also shown that, for every right-c.e. 1-random real *α*, there exists a class with measure *α* that contains only 1-random reals. If we combine this with Nies [9], theorem 3.2.35 (see the remarks (3.1)), we get (3.6).
3.6
If we had a version of lemma 3.1, where *Q*=∅, we could use a relativized version of (3.6) in order to obtain an analogue of the characterization (3.4) for universality probabilities. Unfortunately, such a version of lemma 3.1 would contradict proposition 2.9. However, we are able to obtain such a characterization using a less direct argument.

### Theorem 3.4

*A real number is the universality probability of a universal prefix-free machine if and only if it is right c.e. relative to ∅*^{(3)} *and 4-random.*

The proof of theorem 3.4 is presented in §5 and involves lemma 3.1 as well as some techniques in Downey & Hirshfeldt [16], §9.2 (originally from [13–15]) that were used to show (3.4).

In the following, we use the main results that we discussed earlier in order to show that the non-universality probability of a universal prefix-free machine equals the halting probability of another universal prefix-free machine that operates with oracle ∅^{(3)}. Moreover, the converse holds as well. The halting probability of a universal prefix-free machine that operates with oracle ∅^{(3)} equals the non-universality probability of another universal prefix-free machine (operating without an oracle). The reason for this coincidence is that 1-random left-c.e. reals are exactly the halting probabilities of universal prefix-free machines.

### Corollary 3.5

*For every universal prefix-free machine* *U*, *there exists an oracle universal prefix-free machine* *V* *such that*
3.7
*Conversely, for every oracle universal prefix-free machine* *V*, *there exists a universal prefix-free machine* *U* *such that* (3.7).

### Proof.

Let *U* be a universal prefix-free machine. By theorem 3.3, the probability *P*_{U} is 4-random and right c.e. relative to ∅^{(3)}. Hence, 1−*P*_{U} is 4-random and left c.e. relative to ∅^{(3)}. By (3.5) with *n*=3, there is a universal oracle prefix-free machine *V* such that . For the converse, let *V* be a universal oracle prefix-free machine. Then, is 4-random and right c.e. relative to ∅^{(3)}. By theorem 3.4, we can obtain a universal prefix-free machine *U* such that .

Corollary 3.5 says that, in a sense, universality probabilities are complementary to halting probabilities. The introduction of the parameter ∅^{(3)} in the halting probability is necessary because there is a difference in the quantifier complexity of the two unrelativized probabilities.

We have enough information about the universality probability of a universal prefix-free machine *U* in order to determine its place in the arithmetical hierarchy of complexity. By theorem 3.3, the number *P*_{U} is in . In addition, it is not in because it is 4-random. However, because it is right c.e. relative to ∅^{(3)}, it has degree.

### Corollary 3.6

*The universality probability of a universal prefix-free machine is* *but not* . *However, it has* degree.

From theorem 3.3, we can also derive some information about the degree of unsolvability of the universality probability of a universal prefix-free machine. The proof of corollary 3.7 uses the following fact:
3.8
This is a relativized version of the fact that for every universal prefix-free machine *M* the halting probability *Ω*_{M} is in the same Turing degree as the halting problem.

Note that the class of oracles that compute a given set is . This is analogous to the fact that the class of oracles that compute a given set is . Moreover, because this class is null whenever the given set is non-computable (by a classic result from de Leeuw *et al.* [27]), it follows that a 4-random oracle cannot compute any non-computable set (because 4-random oracles are not members of null classes). We use this basic fact in the following proof.

### Corollary 3.7

*The degree of the universality probability of a universal prefix-free machine and* **0**^{(3)} *have supremum* **0**^{(4)} *and infimum* **0**.

### Proof.

Let *U* be a universal prefix-free machine. Then, *P*_{U} has the same degree as 1−*P*_{U}. By corollary 3.5, the latter is equal to for some universal oracle prefix-free machine *V* . Hence, by (3.8) we have *P*_{U}⊕∅^{(3)}≡_{T}∅^{(4)}. Moreover, because *P*_{U} is 4-random, it does not compute any non-computable set. Hence, it does not compute any non-computable set that is computed by ∅^{(3)}. Hence, the degrees of *P*_{U} and ∅^{(3)} form a minimal pair.

The Turing degree of the halting probability *Ω*_{U} does not depend on the choice of the underlying universal machine *U*. Indeed, it always coincides with the degree of the halting problem. However, this may not be the case when we give *U* access to an oracle *A*. This issue was investigated in Downey *et al.* [17], where the following characterization was obtained:
3.9
This fact is explicitly mentioned in the introductory section of Downey *et al.* [17] and is a consequence of the results in §§4 and 8 of Downey *et al.* [17]. We note that the machines involved in these proofs are universal in the sense of definition 1.1 (and not merely weakly universal). Moreover, it follows from their arguments that if *A* is not *K*-trivial, then there exist two universal machines *U*,*V* such that the degrees of and are incomparable. We apply these results in order to show that the degree of the universality probability depends on the choice of the underlying universal prefix-free machine.

### Theorem 3.8

*There exist universal prefix-free machines U,V such that the Turing degrees of P*_{U} *and P*_{V} *are incomparable.*

### Proof.

The set ∅^{(3)} is not *K*-trivial. Hence, by (3.9) (and the remarks below it), we can choose universal prefix-free machines *M*,*N* such that the degrees of and are incomparable. Then, the same holds for the degrees of and . These numbers are 4-random and right c.e. relative to ∅^{(3)}. Hence, by theorem 3.4, we can choose universal prefix-free machines *U*,*V* such that and . Hence, *U*,*V* are as requested.

## 4. Proof of lemma 3.1

We will build on the ideas behind the proof of theorem 2.4. A set of strings is called *upward closed* if, for any string in the set, all of its extensions are in the set. Notice that the conditions in lemma 3.1 hold for *J* if and only if they hold for the upward closure of *J* (i.e. the union of *J* with all extensions of strings in *J*). Hence, it suffices to prove lemma 3.1 for the special case when *J* is upward closed.

Let *U* be a universal prefix-free machine, and let *J* be an upward closed set of strings. The set *Q* plays the same role in both proofs. It consists of the strings above which we choose to simulate *U*. In the proof of theorem 2.4, each string *σ* such that [*σ*] was not contained in the class generated by *Q* at stage |*σ*|+1 of the enumeration of *Q* was associated with an extension *τ* on which we simulated *U* (i.e. we set *V* (*τ***ρ*)=*U*(*ρ*) for each string *ρ*). This ensured that any real that is not prefixed by a string in *Q* preserves universality with respect to *V* . By ensuring that the measure of the class induced by *Q* is small, we proved theorem 2.4.

In this section, we will extend this idea so that we meet the more complex requirement stated in item (a) of lemma 3.1. As was the case in the proof of theorem 2.4, we do not care about which reals with a prefix in *Q* preserve universality with respect to *V* . Instead, we focus on which reals in 2^{ω}−[*Q*] preserve universality.

The less the complexity of *J* is, the easier it is to satisfy item (a) of lemma 3.1. For example, if it was a set of strings, it is easy to modify the construction in theorem 2.4 so that item (a) is met (at least for the main notion of universality). All we need to do is proceed as before, but when a real in 2^{ω}−[*Q*] is found to have a prefix in *J*, we stop any simulations of *U* on strings that extend that prefix. By ensuring that *μ*([*Q*])<2^{−4}, we have that 2^{ω}−[*Q*]−[*J*]≠∅. The situation when *J* is is quite similar, where instead of stopping a simulation we merely pause it. In order to deal with the real case of *J* being we still associate each string *σ* that is not in *Q* with an extension of it *τ*, but we do not run a single simulation above *τ*. Instead, we run infinitely many simulations above countably many extensions of *τ* (say, *τ*0^{n}1 for ). Each of these simulations may succeed or not, according to our guesses about whether *σ* is in *J*.

The following is a recursive definition of *Q* and the map *f* that assigns some strings to an extension of them where simulations of *U* may occur. Recall that *e* is a given parameter in the statement of lemma 3.1.
Notice that *Q*={*f*(*σ*)|*σ*∈2^{ω}∧*f*(*σ*)↓} and *Q* is a prefix-free set of strings. Moreover, because |*f*(*σ*)|>2|*σ*|+*e*+1 for all *σ* such that *f*(*σ*)↓ we have
4.1
By construction, if *X*∉[*Q*] then for all . In addition, *f* is partial computable and it is decidable whether it converges on a given argument. Next, we give a canonical representation of upward closed sets of strings.

### Lemma 4.1

*Let* *F* *be an upward closed* *set of strings. Then, there exists a computable predicate* *G* *such that*

*σ*∈*F*⇔∃*i*∀*j*∃*k*∀*t**G*(*σ*,*i*,*j*,*k*,*t*)

*for all strings* *σ* *and numbers* *i*_{0}.

### Proof.

Because *F* is , there is a computable predicate *H* such that
4.2
for each string *σ*. Let *G* be a computable predicate such that for each and each string *σ*
4.3
Such a predicate *G* exists because the second clause of (4.3) is . Indeed, let (*y*)_{n} denote the exponent of the *n*th prime in the unique prime decomposition of *y*. The second clause of (4.3) holds exactly when . This is a predicate because the predicate inside the brackets is ∅^{(2)}-computable.

The right implication of item (i) of the lemma follows from the definitions (4.2) and (4.3). The left implication follows from these and the additional assumption that *F* is upward closed. Finally, it follows from (4.3) that the predicate *G* satisfies property (ii) in the lemma.

Let us fix *G* to be a computable predicate as in lemma 4.1 for *F*:=*J*. The following technical notion is rather standard in computability theory.

### Definition 4.2 (Expansionary stages of statements)

Let ∀*i*∃*jH*(*i*,*j*) be a statement (where *H* is computable). In addition, let ℓ[*s*] be the largest *k*≤*s* such that ∀*i*<*k* ∃*j*≤*s* *H*(*i*,*j*) (if such *k* does not exist, let ℓ[*s*]=0). We say that ‘stage’ *s* is expansionary for the predicate if ℓ[*s*]>ℓ[*t*] for all *t*<*s*.

The point of definition 4.2 is that a statement is true if and only if it has infinitely many expansionary stages. This is sometimes called -approximation of the truth of the statement.

### Definition 4.3 (simulation of machines with overhead)

We say that a machine *N* successfully simulates another machine *U* with overhead a string *σ* if *N*(*σ***ρ*)=*U*(*ρ*) for all strings *ρ*. In addition, *N* successfully simulates *U* above *τ* if it successfully simulates *U* with overhead an extension of *τ*.

In definition 4.3, we talk about ‘successful’ simulation to refer to the eventual outcome of a step-by-step procedure (and distinguish this case from the case when the simulation stops after finitely many steps). The following construction of the machine *V* is designed so that the following requirement is met:
4.4
In fact, the following more general requirement will be met:
4.5
The following ‘weak universality’ version will also be met:
4.6
This stronger statement will enable us to show the version of item (a) of lemma 3.1 that refers to weak universality.

### (a) Construction of *V*

At stage *s*+1, do the following for each string of length ≤*s* such that *f*(*σ*) is defined and each *j*≤*s*. If *s*+1 is an expansionary stage for ∀*k*∃*t* ¬*G*(*σ*,|*σ*|,*j*,*k*,*t*), then let *V* (*f*(*σ*)*0^{j}1**ρ*)[*s*+1]=*U*(*ρ*)[*s*] for all strings *ρ* of length ≤*s*.

### (b) Verification

First, we prove some basic properties of the construction of machine *V* and then we verify the properties (a)–(c) of lemma 3.1.

The construction of *V* is computable because *f* is partial computable and it is decidable whether it converges on a given argument. Hence, *Q* is a class. In addition, all the computations have the form ‘*V* (*f*(*σ*)*0^{j}1**ρ*)=*U*(*ρ*)’, where *σ*,*ρ* are strings and . Because the set *Q*={*f*(*σ*)|*σ*∈2^{ω} ∧ *f*(*σ*)↓} is prefix free, the machine *V* is prefix free. Moreover, given the definition of a set of strings, one can compute a definition of its upward closure. Furthermore, the canonical representation of lemma 4.1 can be computed from the given definition of the set of strings. Hence, *V* and *Q* are effectively obtained from the given and a index of *J*.

*Verification of* (*4.4*)–(*4.6*). Suppose that *f*(*σ*) is defined and fix . If ∀*k*∃*t* ¬*G*(*σ*,|*σ*|,*j*,*k*,*t*), the statement ∀*k*∃*t* ¬*G*(*σ*,|*σ*|,*j*,*k*,*t*) will have infinitely many expansionary stages. Hence, *V* (*f*(*σ*)*0^{j}1**ρ*)=*U*(*ρ*) for all string *ρ* such that *U*(*ρ*) is defined and *V* simulates *U* with overhead *f*(*σ*)*0^{j}1. On the other hand, if ∃*k*∀*t* *G*(*σ*,|*σ*|,*j*,*k*,*t*) the simulation of *U* above *f*(*σ*)*0^{j}1 will stop at some stage. Hence, *V* does not simulate *U* with overhead *f*(*σ*)*0^{j}1 and this concludes the proof of (4.4).

For (4.5), suppose that *f*(*σ*) is defined. If ∃*j*∀*k*∃*t* ¬*G*(*σ*,|*σ*|,*j*,*k*,*t*), by (4.4) *V* simulates *U* above *f*(*σ*). Otherwise by (4.4), each simulation of *U* above *f*(*σ*) will terminate at some stage. More precisely, for each the simulation of *U* with overhead *f*(*σ*)*0^{j}1 will stop at some stage that depends on *j*. Hence, for each , the domain of *V* restricted to strings which extend *f*(*σ*)*0^{j}1 is finite. Moreover, these are the only *V* -computations that are enumerated for strings extending *f*(*σ*); so (4.5) holds.

For (4.6), it suffices to show that if *f*(*σ*)↓ and ∃*k*∀*t* *G*(*σ*,|*σ*|,*j*,*k*,*t*), then the machine *ρ*↦*V* (*σ***ρ*) is not weakly universal. Indeed, let *c* be a constant and consider a stage *s*_{0} after which no *V* -computations are enumerated for strings extending 0^{i}1,*i*≤*c*. In addition, let *τ* be a string that receives its first *U*-description after stage *s*_{0}. This exists because only finitely many *U*-computations exist by stage *s*_{0}. By the choice of stage *s*_{0} and the definition of *V* , the length of the shortest *V* -description of *τ* (if that exists) will be at least *c*+1 bits longer than its shortest *U*-description. Hence, the machine *ρ*↦*V* (*σ***ρ*) is not weakly universal with constant *c* and this concludes the proof of (4.6).

*Verification of item* (*a*) *of lemma 3.1* (*for universality and weak universality*). Let *X*∈2^{ω}−[*Q*]. By the construction, is defined for all . Assume that *X* does not have a prefix in *J*. Then for all we have . In particular, for all . By (4.5), the real *X* preserves universality with respect to *V* . Now assume that some prefix of *X* is in *J*. Then, . Let *i*_{0} be a number such that . By the choice of *G* (based on lemma 4.1), for all and all , we have ∀*j*∃*k*∀*t* *G*(*ρ*,*m*,*j*,*k*,*t*). By (4.5), it follows that *V* does not successfully simulate *U* at any *f*(*ρ*) for . Consider *t*>*m* such that is longer than and incomparable with all *f*(*τ*) for . Such *t* exists because *X*∈2^{ω}−[*Q*]. Then for all , the machine *V* is not universal with overhead *τ*. Indeed, if [*τ*]⊆[*Q*], then it holds by the choice of *m*,*t* and (4.5). Otherwise, *V* does not enumerate any definitions extending *τ*; so it trivially holds. Hence, *X* does not preserve universality and this completes the proof of item (a) for the stronger version of universality. The same argument becomes a proof of the weak universality version of item (a), if, instead of (4.5), we use (4.6).

*Verification of items (b), (c) of lemma 3.1*. Item (b) was already shown in (4.1). For item (c), let *S* be the set of strings *σ* such that *V* successfully simulates *U* with overhead *σ*. These are exactly the strings of the form *f*(*τ*)*0^{j}1 for some string *τ*, such that ∀*k*∃*t* ¬*G*(*τ*,|*τ*|,*j*,*k*,*t*). Because *Q* is prefix free (by the remark (4.1)), it follows that *S* is prefix free. By (4.4) and the fact that *f* is (partial) computable, the set *S* is computable in ∅^{(2)}.

If a real in [*Q*] preserves universality, then either it is of the form *f*(*σ*)*0^{ω} for some string *σ* with *f*(*σ*)↓ or it has a prefix in *S*. Indeed, if it is an extension of some *f*(*τ*) and it is not *f*(*τ*)*0^{ω}, then it extends some *f*(*τ*)*0^{j}1 for some . If *f*(*τ*)*0^{j}1 is not in *S*, then *V* will enumerate only finitely many computations on arguments that extend *f*(*τ*)*0^{j}1. Hence, no real extending, *f*(*τ*)*0^{j}1 preserves universality. Moreover, notice that because *Q* (i.e. the range of *f*) is prefix free we have
Hence, if we let denote the set of reals that preserve universality with respect to *V*, we have
But if *σ*∈*S*, then . Hence
4.7
Because [*S*] is a class, its measure is computable in ∅^{(3)}. Because *P*_{U} is a right-c.e. real relative to ∅^{(3)}, the measure of is a right-c.e. real relative to ∅^{(3)}. This concludes the proof of item (c) of lemma 3.1.

## 5. Proof of theorem 3.4

By theorem 3.3 (which is a consequence of lemma 3.1), it suffices to show that, given any 4-random real *α*<1 that is right c.e. relative to ∅^{(3)}, there exists a prefix-free machine with universality probability *α*. Let *α* be such a real. By (3.5), let for some universal oracle prefix-free machine *N*. By definition 1.1, there exists a string *ρ* such that if *M*_{e} is an effective list of all (oracle) prefix-free machines, then
5.1
We will use a fixed point of the algorithm provided by lemma 3.1 in order to produce *J* such that *Q*⊆*J* and a suitable machine *V* with universality probability *α*.

Let (*Ψ*_{e}) be an effective list of all functionals that output rational numbers in [0,1]. Also let (*Φ*_{e}) be an effective list of all functionals that output natural numbers. An index of a left-c.e. real *β* is a program *e* such that (*Ψ*_{e}(*i*)) is an increasing sequence of rationals converging to *β*. Similar definitions apply to the indices of right-c.e. reals as well as right-c.e. reals relative to an oracle *X*. The following fact is a version of Downey & Hirshfeldt [16], proposition 9.2.1:
5.2

### Proof of (5.2).

Given *β*, we may construct a machine *M* and by the recursion theorem we may use an index *e* of *M* in its own definition. We make *M* so that the weight of its domain is the minimum of 1 and 2^{|ρ|+e+1}⋅*β*, where *ρ* is from (5.1). We set *c*=2^{−e−1−|ρ|}. Clearly, if the input *β* is less than 2^{−c}, then the weight of *M* will be exactly 2^{e+1+|ρ|}⋅*β*. Moreover, by (5.1), every increase in the approximation to *β* will correspond to a later increase in *Ω*_{N}−*β*. Thus, we have a computable approximation of *Ω*_{N}−*β* from below.

This fact can be relativized to any oracle and holds symmetrically for right-c.e. reals with a similar proof.
5.3
Notice that (5.3) not only says that is a right-c.e. relative to ∅^{(3)} real (provided that *β*<2^{−c}) but it also gives a way to compute a witness (an index) of this fact. The following is a formal way to write (5.3), which we will need for the application of the fixed-point theorem:
5.4
We will also need the following program. Let (*W*_{e}) be an effective enumeration of all oracle computable enumerations of sets of strings. Given an oracle *X*, we say that *e* is an *X*-c.e. (or c.e. relative to *X*) index of the set *W*^{X}_{e}. If *X*=∅, we may omit the oracle in the notation.
5.5

### Proof of (5.5).

Let (*Q*[*s*]) be a computable enumeration of *Q* such that *μ*(*Q*)− *μ*(*Q*[*s*])<2^{−s}. In addition, let (*γ*_{s}) be a ∅^{(3)}-computable decreasing sequence of rationals converging to *γ*. At stage 2*s*+1 put *Q*[*s*+1]−*Q*[*s*] into *J*. At stage 2*s*+2, if *γ*_{s+1}+2^{−s−1}<1−*μ*(*J*[2*s*+1]) put into *J* a finite number of strings such that *μ*(*J*[2*s*+2])−*μ*(*J*[2*s*+1])=1−*μ*(*J*[2*s*+1])−*γ*_{s+1}−2^{−s−1}. By the construction, we have *Q*⊆*J*. Moreover, 1−*μ*(*J*)≥*γ*. In addition, for each we have 1−*μ*(*J*[2*s*+1])≤ *γ*_{s+1}+2^{−s−1}. Hence, 1−*μ*(*J*)=*γ*.

We give a formal version of (5.5) that will be used in an application of the fixed-point theorem.
5.6
Consider the following program that is based on lemma 3.1.
5.7
Let *f*,*g*,*h* be the following computable functions that give the output of program (5.7) on input *j*,*k*:

—

*W*_{f(j,k)}coincides with the set*Q*of lemma 3.1 (with*J*=*W*_{j},*e*=*c*(*k*))—

*Φ*_{g(j,k)}computes*μ*(*Q*) of lemma 3.1 (with*J*=*W*_{j},*e*=*c*(*k*))— is a non-increasing sequence of rationals converging to

*P*_{U}⋅*μ*(*S*) from (4.7) in lemma 3.1.

By the fixed-point theorem, we can find such that

—

—

*W*_{p(f(j,k),g(j,k),t(k))}=*W*_{j}.

By (5.7) (and the underlying program of lemma 3.1), we have *μ*(*Q*)<2^{−c(k)}. Because *S*⊆*Q* (see the discussion above (4.7)), the real *P*_{U}⋅*μ*(*S*) is less than 2^{−c(k)}. In other words, by the choice of *h*, the right-c.e. relative to ∅^{(3)} real with index *h*(*j*,*k*) is less than 2^{−c(k)}. But by the first clause of the fixed-point equations, this right-c.e. relative to ∅^{(3)} real also has index *k*. Then by (5.4), the real with index *t*(*k*) is . By the second clause of the fixed-point equations, the latter is equal to the measure of 2^{ω}−[*J*].
5.8
Hence, if we denote by the class of reals that preserve universality with respect to the machine *V* that was produced by program (5.7) (with the fixed-point input), we have:
where the last equality was obtained by item (a) of lemma 3.1 and (4.7). Because *Q*⊆*J* in this particular fixed-point construction, 2^{ω}−[*J*]⊆2^{ω}−[*Q*]. Hence
where the last equality follows by (5.8). But by the definition of *h*, we have . Hence, and this concludes the proof of theorem 3.4.

## Acknowledgements

G.B. was supported by a research fund for international young scientists (no. 611501-10168) from the National Natural Science Foundation of China, and an International Young Scientist Fellowship (no. 2010-Y2GB03) from the Chinese Academy of Sciences. Partial support was also obtained by the Grand Project: Network Algorithms and Digital Information of the Institute of Software, Chinese Academy of Sciences. D.L.D. thanks Chris J. Ash (1945–1995) for teaching him logic. We thank Chris Wallace (1933–2004) for originally drawing the notion of universality probability to our attention, and we thank the anonymous referees for their useful feedback.

## Footnotes

One contribution of 18 to a Theme Issue ‘The foundations of computation, physics and mentality: the Turing legacy’.

↵1 Occasionally ∅

^{(1)}is also denoted by ∅′.↵2 A set

*A*is partial many-one reducible to a set*B*if*A*=*f*^{−1}(*B*) for some partial computable function*f*. For more references about partial many-one reductions, see Becher & Grigorieff [20], §2.

- This journal is © 2012 The Royal Society