Royal Society Publishing

Universality probability of a prefix-free machine

George Barmpalias , David L. Dowe

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: Embedded Image 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: Embedded Image 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. Embedded Image 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 ∩jUj where (Uj) is a uniform sequence of Embedded Image classes such that μ(Uj)<2j−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 Embedded Image for some constant c and all Embedded Image. In other words, if for each Embedded Image 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 Embedded Image 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 Embedded Image 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 Embedded Image-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 §1d, 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 §1a. 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(0e1σ)=Me(σ), where (Me) 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 §1a. 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 KV 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 KU(σ)≤KM(σ)+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 §1d) 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 Embedded Image, Embedded Image 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) Embedded Image 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 [1315] that we discussed in §1b. 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 (Ve) be a standard list of all prefix-free machines. The number e is said to be an index of the machine Ve. Notice that we use natural numbers to index machines, instead of strings. Let P(e,n,τ,σ,s) be the computable predicate that Ve(τ*σ)[s]=Vn(σ)[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 Embedded Image predicate ∀nτσ,ts>t, P(e,n,τ,σ,s). Similarly, the property that machine e is weakly universal can be expressed by the Embedded Image predicate ∀ncσ,ts>t,τ[|τ|≤|σ|+cP(e,n,τ,σ,s)]. However, the variables in P are not entirely ‘independent’ (e.g. if Ve(τ)↓ 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 Embedded Image-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 Vn. Hence, Ve is universal if and only if Embedded Image 2.1 Therefore, they form a Embedded Image 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 Vn. Hence, Ve is weakly universal if and only if Embedded Image 2.2 Therefore, they too form a Embedded Image set.

In order to show that (2.1) and (2.2) are Embedded Image-complete, let Q(e,t,k,s) be a computable relation such that the predicate ∃tks Q(e,t,k,s) is Embedded Image-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 Embedded Image 2.3 for each Embedded Image and all strings in the domain of Vf(e) extend some Embedded Image. This is simply carried out by expressing the Embedded Image predicate ∀ks Q(e,t,k,s) as the Embedded Image of a computable function g with binary values, and updating the Vf(e)-simulation of Vn on extensions of τt at stages s where g(s)=1. By (2.3) (and the fact that all Vf(e)-computations are enumerated on strings that are prefixed by some τi, Embedded Image), we have that Embedded Image Because f is computable, it follows that the predicates in (2.1) and (2.2) are Embedded Image-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 Embedded Image 2.4 Clearly, T is a tree (i.e. a downward closed set of strings) and, because the Embedded Image 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: Embedded Image 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 PM (denoted by PwM), 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 Embedded Image. If U is a universal machine, then clearly ΩU>0. In addition, PwU≤1−ΩU because, if U halts on some input, no real extending that input can preserve universality. Hence, PwU<1 for every universal machine U. We wish to show that we also have PU>0 and PwU>0. It suffices to construct a universal machine V such that PV>0. Indeed, then we argue that PU>0 (hence PwU>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, PU≥2−|τ|PV>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 PV>0. In order to achieve this, we will enumerate a Embedded Image class Q of measure <1, such that every real in the Embedded Image 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 >2s+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:=∪sQ[s] and suppose that X∈2ωQ. Then, by the construction, we have Embedded Image for all Embedded Image. Therefore, X preserves universality with respect to V . It remains to show that μ(Q)<1. Notice that C[s] consists of at most 2s 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 2s+2), we have that μ(Q[s+1]−Q[s])≤2s−2. Because Q=∪sQ[s], we have μ(Q)<1.

In the proof of theorem 2.4, we constructed a universal machine V and a Embedded Image 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 Embedded Image class P*={τ*X|XP} 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 Embedded Image 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 Embedded Image 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 2s+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 PV is as close to 1 as we wish. Similarly, by choosing the domain of V to have suitably large measure, we can ensure that PV 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 Embedded Image and Embedded Image.

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 Embedded Image 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 Embedded Image 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 Embedded Image for some real X. Let Nc be the c.e. set of strings σ such that K(σ)≤|σ|−c. Fix a computable enumeration of Nc 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 ρNc[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 Nc, every real X with no prefixes in Nc 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 [1820]. 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 Embedded Image-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 Embedded Image.

Lemma 3.1 (special machines)

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

  1. A real in 2ω−[Q] preserves [weak] universality with respect to V if and only if it does not have a prefix in J.

  2. The measure of [Q] is computable and at most 2e.

  3. 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 Embedded Image 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

  1. there are reals in 2ω−[Q] that preserve universality with respect to V

  2. every real in 2ω−[Q] that preserves [weak] universality with respect to V is 4-random

  3. the 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 Embedded Image class is a right-c.e. real and, similarly, the measure of a Embedded Image 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 Embedded Image class that contains only 1-random reals is a 1-random real. A direct relativization of this fact gives the following analogous result: Embedded Image 3.1 Because the class [Q] is Embedded Image, by (2.5) the class of reals in 2ω−[Q] that preserve [weak] universality with respect to V is a Embedded Image class. Then, by item (ii) of the proof of lemma 3.2 and (3.1) we have (3.2). Embedded Image 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). Embedded Image 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 Embedded Image class. In fact, this will be a Embedded Image 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 PV. Given any universal machine U, there is a string τ such that V (ρ)=U(τ*ρ) for all strings ρ. Let Embedded Image be the class of reals that preserve universality with respect to U and for each string σ of length |τ| consider the class Embedded Image. The measure of Embedded Image is 2−|τ|PV; so by lemma 3.2 it is a 4-random right-c.e. relative to ∅(3) number. Moreover, the classes Embedded Image are Embedded Image so their measures are right c.e. relative to ∅(3). The measure of Embedded Image is the finite sum of the measures of the classes Embedded Image 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 [1315] (for a simplified presentation, we recommend Downey & Hirshfeldt [16], §9.2). Embedded Image 3.4 By Downey et al. [17], §2, the above-mentioned result relativizes to any oracle, so that the following holds for each Embedded Image: Embedded Image 3.5 In Kučera & Slaman [15], it was also shown that, for every right-c.e. 1-random real α, there exists a Embedded Image 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). Embedded Image 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 [1315]) 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 Embedded Image 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 PU is 4-random and right c.e. relative to ∅(3). Hence, 1−PU 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 Embedded Image. For the converse, let V be a universal oracle prefix-free machine. Then, Embedded Image 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 Embedded Image.

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 PU is in Embedded Image. In addition, it is not in Embedded Image because it is 4-random. However, because it is right c.e. relative to ∅(3), it has Embedded Image degree.

Corollary 3.6

The universality probability of a universal prefix-free machine is Embedded Image but not Embedded Image. However, it has Embedded Image 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: Embedded Image 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 Embedded Image set is Embedded Image. This is analogous to the fact that the class of oracles that compute a given Embedded Image set is Embedded Image. 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 Embedded Image set (because 4-random oracles are not members of null Embedded Image 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, PU has the same degree as 1−PU. By corollary 3.5, the latter is equal to Embedded Image for some universal oracle prefix-free machine V . Hence, by (3.8) we have PU⊕∅(3)T(4). Moreover, because PU is 4-random, it does not compute any non-computable Embedded Image set. Hence, it does not compute any non-computable set that is computed by ∅(3). Hence, the degrees of PU 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: Embedded Image 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 Embedded Image and Embedded Image 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 PU and PV 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 Embedded Image and Embedded Image are incomparable. Then, the same holds for the degrees of Embedded Image and Embedded Image. 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 Embedded Image and Embedded Image. 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, Embedded Image and let J be an upward closed Embedded Image 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 Embedded Image 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 Embedded Image 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 Embedded Image 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 Embedded Image is quite similar, where instead of stopping a simulation we merely pause it. In order to deal with the real case of J being Embedded Image 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, τ0n1 for Embedded Image). 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. Embedded Image 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 Embedded Image 4.1 By construction, if X∉[Q] then Embedded Image for all Embedded Image. 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 Embedded Image sets of strings.

Lemma 4.1

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

  1. σF⇔∃ijkt G(σ,i,j,k,t)

  2. Embedded Image

for all strings σ and numbers i0.

Proof.

Because F is Embedded Image, there is a computable predicate H such that Embedded Image 4.2 for each string σ. Let G be a computable predicate such that for each Embedded Image and each string σ Embedded Image 4.3 Such a predicate G exists because the second clause of (4.3) is Embedded Image. Indeed, let (y)n denote the exponent of the nth prime in the unique prime decomposition of y. The second clause of (4.3) holds exactly when Embedded Image. This is a Embedded Image 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 Embedded Image statements)

Let ∀ijH(i,j) be a Embedded Image statement (where H is computable). In addition, let ℓ[s] be the largest ks such that ∀i<k ∃js 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 Embedded Image statement is true if and only if it has infinitely many expansionary stages. This is sometimes called Embedded Image-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: Embedded Image 4.4 In fact, the following more general requirement will be met: Embedded Image 4.5 The following ‘weak universality’ version will also be met: Embedded Image 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 js. If s+1 is an expansionary stage for ∀kt ¬G(σ,|σ|,j,k,t), then let V (f(σ)*0j1*ρ)[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 Embedded Image class. In addition, all the computations have the form ‘V (f(σ)*0j1*ρ)=U(ρ)’, where σ,ρ are strings and Embedded Image. Because the set Q={f(σ)|σ∈2ω ∧ f(σ)↓} is prefix free, the machine V is prefix free. Moreover, given the Embedded Image definition of a set of strings, one can compute a Embedded Image definition of its upward closure. Furthermore, the canonical representation of lemma 4.1 can be computed from the given Embedded Image definition of the set of strings. Hence, V and Q are effectively obtained from the given Embedded Image and a Embedded Image index of J.

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

For (4.5), suppose that f(σ) is defined. If ∃jkt ¬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 Embedded Image the simulation of U with overhead f(σ)*0j1 will stop at some stage that depends on j. Hence, for each Embedded Image, the domain of V restricted to strings which extend f(σ)*0j1 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 ∃kt G(σ,|σ|,j,k,t), then the machine ρV (σ*ρ) is not weakly universal. Indeed, let c be a constant and consider a stage s0 after which no V -computations are enumerated for strings extending 0i1,ic. In addition, let τ be a string that receives its first U-description after stage s0. This exists because only finitely many U-computations exist by stage s0. By the choice of stage s0 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, Embedded Image is defined for all Embedded Image. Assume that X does not have a prefix in J. Then for all Embedded Image we have Embedded Image. In particular, Embedded Image for all Embedded Image. By (4.5), the real X preserves universality with respect to V . Now assume that some prefix Embedded Image of X is in J. Then, Embedded Image. Let i0 be a number such that Embedded Image. By the choice of G (based on lemma 4.1), for all Embedded Image and all Embedded Image, we have ∀jkt G(ρ,m,j,k,t). By (4.5), it follows that V does not successfully simulate U at any f(ρ) for Embedded Image. Consider t>m such that Embedded Image is longer than and incomparable with all f(τ) for Embedded Image. Such t exists because X∈2ω−[Q]. Then for all Embedded Image, 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(τ)*0j1 for some string τ, such that ∀kt ¬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(τ)*0j1 for some Embedded Image. If f(τ)*0j1 is not in S, then V will enumerate only finitely many computations on arguments that extend f(τ)*0j1. Hence, no real extending, f(τ)*0j1 preserves universality. Moreover, notice that because Q (i.e. the range of f) is prefix free we have Embedded Image Hence, if we let Embedded Image denote the set of reals that preserve universality with respect to V, we have Embedded Image But if σS, then Embedded Image. Hence Embedded Image 4.7 Because [S] is a Embedded Image class, its measure is computable in ∅(3). Because PU is a right-c.e. real relative to ∅(3), the measure of Embedded Image 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 Embedded Image for some universal oracle prefix-free machine N. By definition 1.1, there exists a string ρ such that if Me is an effective list of all (oracle) prefix-free machines, then Embedded Image 5.1 We will use a fixed point of the algorithm provided by lemma 3.1 in order to produce J such that QJ 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: Embedded Image 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=2e−1−|ρ|. Clearly, if the input β is less than 2c, then the weight of M will be exactly 2e+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. Embedded Image 5.3 Notice that (5.3) not only says that Embedded Image is a right-c.e. relative to ∅(3) real (provided that β<2c) 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: Embedded Image 5.4 We will also need the following program. Let (We) 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 WXe. If X=∅, we may omit the oracle in the notation. Embedded Image 5.5

Proof of (5.5).

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

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

  • Wf(j,k) coincides with the set Q of lemma 3.1 (with J=Wj, e=c(k))

  • Φg(j,k) computes μ(Q) of lemma 3.1 (with J=Wj, e=c(k))

  • Embedded Image is a non-increasing sequence of rationals converging to PUμ(S) from (4.7) in lemma 3.1.

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

  • Embedded Image

  • Wp(f(j,k),g(j,k),t(k))=Wj.

By (5.7) (and the underlying program of lemma 3.1), we have μ(Q)<2c(k). Because SQ (see the discussion above (4.7)), the real PUμ(S) is less than 2c(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 2c(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 Embedded Image. By the second clause of the fixed-point equations, the latter is equal to the measure of 2ω−[J]. Embedded Image 5.8 Hence, if we denote by Embedded Image 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: Embedded Image where the last equality was obtained by item (a) of lemma 3.1 and (4.7). Because QJ in this particular fixed-point construction, 2ω−[J]⊆2ω−[Q]. Hence Embedded Image where the last equality follows by (5.8). But by the definition of h, we have Embedded Image. Hence, Embedded Image 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

References

View Abstract