# An extension of the recursively enumerable Turing degrees

Stephen G. Simpson

Department of Mathematics

August 10, 2004

Pennsylvania State University

This research was partially supported by NSF grant DMS-0070718.

AMS Subject Classifications: 03D25, 03D30, 68Q30.

Journal of the London Mathematical Society, 75, 2007, pp. 287-297.

### Abstract:

Consider the countable semilattice consisting of the recursively enumerable Turing degrees. Although is known to be structurally rich, a major source of frustration is that no specific, natural degrees in have been discovered, except the bottom and top degrees, and . In order to overcome this difficulty, we embed into a larger degree structure which is better behaved. Namely, consider the countable distributive lattice consisting of the weak degrees (a.k.a., Muchnik degrees) of mass problems associated with nonempty subsets of . It is known that contains a bottom degree and a top degree and is structurally rich. Moreover, contains many specific, natural degrees other than and . In particular, we show that in one has . Here is the weak degree of the diagonally nonrecursive functions, and is the weak degree of the -random reals. It is known that can be characterized as the maximum weak degree of a subset of of positive measure. We now show that can be characterized as the maximum weak degree of a subset of whose Turing upward closure is of positive measure. We exhibit a natural embedding of into which is one-to-one, preserves the semilattice structure of , carries to , and carries to . Identifying with its image in , we show that all of the degrees in except and are incomparable with the specific degrees , , and in .

# Introduction

A principal object of study in recursion theory going back to the seminal work of Turing [36] and Post [25] has been the countable upper semilattice of recursively enumerable Turing degrees, i.e., Turing degrees of recursively enumerable sets of positive integers. See the monographs of Sacks [27], Rogers [26], Soare [35], and Odifreddi [22,23].

A major difficulty or obstacle in the study of has been the lack of natural examples. Although it has long been known that is infinite and structurally rich, to this day no specific, natural examples of recursively enumerable Turing degrees are known, beyond the two examples originally noted by Turing: the Turing degree of the Halting Problem, and the Turing degree of solvable problems. Furthermore, and are respectively the top and bottom elements of . This paucity of examples in is striking, because it is widely recognized that most other branches of mathematics are motivated and nurtured by a rich stock of examples. Clearly it ought to be of interest to somehow overcome this deficiency in the study of .

In 1999 [30,31] we defined a degree structure, here denoted , which is closely related to , but superior to in at least two respects. First, exhibits better structural behavior than , in the sense that is a countable distributive lattice, while is not even a lattice. Second and more importantly, there are plenty of specific, natural degrees in which are intermediate between and , the top and bottom elements of . Thus does not suffer from the above-mentioned lack of examples, which plagues .

In more detail, let be the lattice of weak degrees (a.k.a., Muchnik degrees) of mass problems given by nonempty subsets of . In 1999 [30] we showed that among the intermediate degrees in is the specific degree associated with the set of -random reals. The concept of -randomness was already well known from algorithmic information theory [19]. After 1999, we and other authors [2,3,4,5,32,33,34] continued the study of , using priority arguments to prove structural properties, just as for . In addition, we [33] discovered families of specific, natural, intermediate degrees in related to foundationally interesting topics such as reverse mathematics, Gentzen-style proof theory, and computational complexity. Some additional degrees of this kind are presented in Sections 3 and 4 below.

The purpose of the present paper is to further clarify the relationship between the semilattice and the lattice . Namely, we exhibit a specific, natural embedding which is one-to-one, preserves the semilattice structure of , and carries the top and bottom elements of to the top and bottom elements of . See Theorem 5.5 below. By identifying with its image in , we place the recursively enumerable Turing degrees into a wider context, where natural intermediate degrees occur. We view this as a step toward overcoming the above-mentioned difficulties concerning .

At the same time, our embedding of into fails to solve the long standing open problem of finding a specific, natural, intermediate degree within itself. Indeed, we shall see below (Theorem 5.6) that, regrettably, all of the intermediate degrees belonging to the image of under our embedding are incomparable with all of the known natural intermediate degrees in .

# Background: and

In this section we review some basic information concerning the semilattice and the lattice .

Throughout this paper we shall use standard recursion-theoretic notation from Rogers [26] and Soare [35]. For special aspects of mass problems and sets, a convenient reference is [33].

We write for the set of natural numbers, for the space of total functions from into , and for the space of total functions from into . We sometimes identify a set with its characteristic function given by if , if . For and we write to mean that the Turing machine with Gödel number and oracle and input eventually halts with output . In the absence of an oracle , we write . For we consider recursive functionals given by for some and all and . A function is said to be recursive if there exists such that for all . A set is said to be recursively enumerable if it is the image of a recursive function, i.e., for some recursive .

For we write to mean that is Turing reducible to , i.e., . The Turing degree of , denoted , is the set of all such that , i.e., and . The set of all Turing degrees is partially ordered by putting if and only if . Under this partial ordering, the bottom element of is is recursive. Within , the least upper bound of and is where and for all . A Turing degree is said to be recursively enumerable if where is recursively enumerable. The set of all recursively enumerable Turing degrees is denoted . It is easy to see that is closed under the least upper bound operation inherited from . The top and bottom elements of are and respectively, where is the Turing degree of the Halting Problem, . Thus is a countable upper semilattice with a top and bottom element.

Definition 2.1   Let be subsets of . We say that is weakly reducible to , written , if for all there exists such that . The weak degree of , written , is the set of all such that , i.e., and . The set of all weak degrees is partially ordered by putting if and only if . The concept of weak reducibility goes back to Muchnik [21] and has sometimes been called Muchnik reducibility.

Theorem 2.2   is a complete distributive lattice.

Proof.The least upper bound of and in is where

The greatest lower bound of and in is . The bottom element of is
and is recursive.
Note that if and only if , where is the Turing upward closure of ,

Thus the lattice of weak degrees, , is inversely isomorphic to the lattice of subsets of which are upward closed with respect to . It follows that is a complete distributive lattice.

Remark 2.3   There is an obvious, natural embedding of into given by . Here is the singleton set whose only member is . This embedding is one-to-one, preserves the partial ordering relation and least upper bound operation from , and carries to . Compare this with our embedding of into in Theorem 5.5 below.

Definition 2.4   A predicate is said to be recursive if
if , and if . A set is said to be if there exists a recursive predicate such that . A set is said to be if there exists a recursive predicate such that . Other levels of the arithmetical hierarchy are defined similarly.

Definition 2.5   A set is said to be recursively bounded if there exists a recursive function such that for all .

Definition 2.6   For , a recursive homeomorphism of onto is a recursive functional mapping one-to-one onto such that the inverse functional is recursive. In this case we say that and are recursively homeomorphic.

Theorem 2.7   is recursively bounded if and only if is recursively homeomorphic to a set .

Proof.See [33, Theorems 4.7 and 4.10].

Corollary 2.8   The weak degrees of nonempty recursively bounded sets are the same as the weak degrees of nonempty subsets of .

Proof.This is immediate from Theorem 2.7.

Definition 2.9   is the set of weak degrees of nonempty subsets of .

Theorem 2.10   is a countable distributive lattice with a top and bottom element, denoted and respectively.

Proof.If and are subsets of , then so are and . Thus is closed under the least upper bound and greatest lower bound operations inherited from . Clearly is countable, because there are only countably many subsets of . Clearly is the bottom element of . Let be the set of completions of Peano Arithmetic. Identifying sentences with their Gödel numbers, we may view as a subset of . By Scott [29], is the top element of . See also [33, Section 6].

Remark 2.11   Just like the countable semilattice , the countable distributive lattice is known to be structurally rich. Binns/Simpson [2,5] have shown that every countable distributive lattice is lattice embeddable in every nontrivial initial segment of . Binns [2,3] has obtained the analog of the Sacks Splitting Theorem for [27]. Namely, for all in there exist such that and . (The analog of the Sacks Density Theorem for [28] remains as an open problem.) These structural results for are proved by means of priority arguments. They invite comparison with the older, known results for , which were also proved by means of priority arguments.

We end this section by mentioning some technical notions and results concerning trees and almost recursiveness.

A finite sequence of natural numbers is called a string of length . The set of all strings is denoted . The set of strings of 's and 's is denoted . If are strings of length respectively, then the concatenation

is a string of length . We write if for some . If is a string of length , then for all we have defined by for , for . We write if for some .

A tree is a set such that, for all , . A path through is an such that . The set of all paths through is denoted . We sometimes identify a string with its Gödel number . A tree is said to be recursive if is recursive.

Theorem 2.12   is if and only if for some recursive tree . is if and only if for some recursive tree .

Proof.See [33, Theorem 4.3].

Definition 2.13   We say that is almost recursive if for all there exists a recursive function such that .

Theorem 2.14   Suppose is almost recursive. Then for all we have for some total recursive functional .

Proof.See [33, Theorem 4.18].

The following result is known as the Almost Recursive Basis Theorem.

Theorem 2.15   If is and nonempty, then there exists such that is almost recursive.

Proof.This is a restatement of the Hyperimmune-Free Basis Theorem of [15, Theorem 2.4]. See also [33, Theorem 4.19].

# Some specific degrees in

In this section we identify and characterize some specific, natural degrees in , and we investigate their degree-theoretic properties.

Definition 3.1   Let be the fair coin'' probability measure on given by for all . Let be a Turing oracle. A point is said to be -random if there does not exist a recursive sequence of sets , , such that and . If the st Turing jump of , where is recursive and , then is said to be -random.

Thus is -random if and only if is random in the sense of Martin-Löf [20], and is -random if and only if is random relative to the Halting Problem. For a thorough treatment of randomness and -randomness, see Kautz [16] or Downey/Hirschfeldt [8]. We write

is -random. Note that .

Lemma 3.2   is . In particular, is , and is .

Proof.It is is well known (see for instance [33, Theorem 8.3]) that is . Relativizing to we see that is -random is , i.e., relative to . Putting , we see that is relative to . From this it follows easily that is .

Lemma 3.3   Let be , and let be nonempty . Then we can find a nonempty set such that .

Proof.First use a Skolem function technique to reduce to the case where is . Namely, fix a recursive predicate such that , and replace by the set of all such that holds. Clearly the latter set is and . Assuming now that is a subset of , let be a recursive subtree of such that is the set of paths through . We may safely assume that, for all and the length of , . Let be a recursive subtree of such that is the set of paths through . Define to be the set of strings of the form

where , , and for all the length of . Thus is a recursive subtree of . Let be the set of paths through . (Compare the construction of in Jockusch/Soare [14].) It is straightforward to verify that . Note that is and recursively bounded. By Theorem 2.7 we can find a set which is recursively homeomorphic to . This completes the proof.

Lemma 3.4   There exist sets such that and

Proof.By Lemmas 3.2 and 3.3 we can find sets such that and . Since is nonempty and , there is a nonempty set . Then , hence , hence .

Definition 3.5   We write and

Theorem 3.6   We have and and .

Proof.By Lemma 3.4 there are sets such that and . Thus and . Clearly , hence . Clearly has no recursive member, i.e., . By [33, Section 7] or [15, Corollary 5.4], the Turing upward closure of is of measure , i.e., for all of positive measure. In particular , i.e., . Summarizing, we have now shown that .

It remains to show that , i.e., . By Lemma 3.2, let be a nonempty subset of . By the Almost Recursive Basis Theorem 2.15, let be almost recursive. By Kautz [16, Theorem IV.2.4(iv)] or Dobrinen/Simpson [7, Remark 2.8], there is no almost recursive . In particular, there is no such that . Suppose there were such that . By Theorem 2.14 let be a total recursive functional such that . Put . We have , hence , hence is nonempty. Since and are , it follows by [33, Theorem 4.4] that is . Hence, by [33, Lemma 8.8], is of positive measure. Since , it follows that the Turing upward closure of is of positive measure, but this is a contradiction. We have now shown that, for a particular , there is no such that . Thus , and this completes the proof.

Remark 3.7   As an application of Theorem 3.6, we can find essentially undecidable, finitely axiomatizable theories and in the first-order predicate calculus, with the following properties: every -random real computes a completion of ; every -random real but not every -random real computes a completion of . This follows from Theorem 3.6 plus the well known, general relationship between subsets of and finitely axiomatizable theories. See [32, Theorem 3.18 and Remark 3.19] and Peretyatkin [24].

Theorem 3.8   We can characterize as the maximum weak degree of a subset of of positive measure. We can characterize as the maximum weak degree of a subset of whose Turing upward closure is of positive measure.

Proof.The first statement is [33, Theorem 8.10]. For the second statement, assume that is a subset of whose Turing upward closure is of positive measure. A computation in the style of Tarski and Kuratowski (compare Rogers [26, Section 14.3]) shows that is . Since is of positive measure, let be of positive measure. By Kautz [16, Lemma II.1.4(ii)] or Dobrinen/Simpson [7, Theorem 3.3], we may assume that is relative to . Relativizing [33, Lemma 8.7] to , we have . Since , it follows that , hence . Furthermore, since is a nonempty subset of , we have . We now see that , i.e., . On the other hand, by Theorem 3.6 let be a subset of such that . Note that , hence is of positive measure. We have now shown that is the maximum such that is of positive measure. This completes the proof of our theorem.

Corollary 3.9   Let be a nonempty subset of . Then if and only if is of positive measure.

Proof.If then trivially , hence is of measure . Conversely, if is of positive measure, then by Theorem 3.8 we have .

Corollary 3.10   We can find a set whose Turing upward closure is of positive measure yet does not include any set of positive measure.

Proof.By Theorem 3.6 let be such that . By Theorem 3.8, is of positive measure. If there were a set of positive measure, then by Theorem 3.8 we would have , contradicting Theorem 3.6.

Theorem 3.11   Let . If then either or . If then either or .

Proof.The first statement is [33, Theorem 8.12, part 3]. For the second statement, let be nonempty subsets of with and . Trivially . Moreover , hence is of positive measure if and only if at least one of and is of positive measure. By Corollary 3.9 this means that if and only if at least one of and .

Definition 3.12   As in [33, Section 7], say that is separating if there is a pair of disjoint, recursively enumerable sets such that where separates . In particular, is separating.

Theorem 3.13   If is separating and , then .

Proof.This is a special case of [33, Theorem 7.5].

Corollary 3.14   For all weak degrees , we have .

Proof.Assume . By the definition of , we have , hence . Since is separating and , Theorem 3.13 tells us that , hence .

Corollary 3.15   Within the lattice , the degrees and are meet-irreducible and do not join to .

Proof.This follows from Theorem 3.11 and Corollary 3.14.

# Some additional, specific degrees in

In this section we identify some additional specific, natural, intermediate degrees in related to diagonal nonrecursiveness.

Definition 4.1   A function is said to be diagonally nonrecursive if for all . We put where
is diagonally nonrecursive. The Turing degrees of diagonally nonrecursive functions have been studied by Jockusch [12]. In particular, a Turing degree contains a diagonally nonrecursive function if and only if it contains a fixed point free function, if and only if it contains an effectively immune set, if and only if it contains an effectively biimmune set. Thus we see that the weak degree is recursion-theoretically natural.

Theorem 4.2   We have .

Proof.Put is diagonally nonrecursive. Obviously is a nonempty subset of . By Lemma 3.3 we can find a nonempty set such that . But , hence . We now see that .

Theorem 4.3   In we have

Proof.By Theorem 3.6 we have . Clearly has no recursive member, i.e., . By Giusto/Simpson [11, Lemma 6.18], for all there exists such that . Thus we have . It remains to show that . By Kumabe [18] there is a diagonally nonrecursive function which is of minimal Turing degree. But if is -random, then is not of minimal Turing degree, because the functions and defined by are Turing incomparable (see for instance van Lambalgen [37]). This proves . An alternative reference for the conclusion is Ambos-Spies et al [1, Theorems 1.4 and 2.1].

Definition 4.4   Let be the set of recursively bounded functions. Thus we have

Put . For an extended discussion of the recursion-theoretic naturalness of and related weak degrees, see [33, Section 10].

Theorem 4.5   We have and

Proof.A Tarski/Kuratowski computation shows that is . Let be as in the proof of Theorem 4.2. By Lemma 3.3 we can find a nonempty set such that . Thus . By Ambos-Spies et al [1, Theorems 1.4, 1.8, 1.9] we have , and the rest is from Theorem 4.3.

Definition 4.6   For all put

the set of functions which are diagonally nonrecursive relative to . Put and, for each ,

Clearly is a subset of . Put .

Remark 4.7   Trivially and for all . The proofs of Theorems 4.2 and 4.3 show that and for all . By Kumabe [18] we have , and we conjecture that for all . Thus in we apparently have

Note also that the sequence can be extended into the transfinite.

Remark 4.8   We conjecture that, for all , is incomparable with . Note also that these 's are not to be confused with the 's of Simpson [33, Example 10.14]. Indeed, we conjecture that, for all and , is incomparable with .

Remark 4.9   We do not know of any specific, natural degrees in outside the interval from to , except and . On the other hand, by Theorem 4.5 and Remarks 4.7 and 4.8, the interval from to within appears to be remarkably rich in specific, natural degrees.

# Embedding into

In this section we exhibit a specific, natural embedding of the countable upper semilattice into the countable distributive lattice .

Definition 5.1   A singleton is a point such that the singleton set is .

Lemma 5.2   Given a singleton , we have . Thus
 (1)

is an upper semilattice homomorphism of the Turing degrees of singletons into .

Proof.The first statement is the special case of Lemma 3.3 with and . For the second statement, note that for any and we have , and implies . In particular this holds when and are singletons and .

Lemma 5.3   We have an upper semilattice homomorphism of the Turing degrees into , given by (1). Moreover, and .

Proof.The first statement is a special case of Lemma 5.2, because if and only if is (see Kleene [17, Theorem XI, page 293]), which implies that is a singleton. It is easy to see that . To show that , by Kleene [17, Theorem 38*, pages 401-402] let be . Then and , hence .

Lemma 5.4   If are Turing degrees , and if , then if and only if . In particular, the restriction of to is one-to-one.

Proof.Let be such that and . We must show that if and only if . The only if'' part is trivial. For the if'' part, suppose . In particular, . If , then , hence , hence by the Arslanov Completeness Criterion [12], hence , a contradiction. Thus . This proves our lemma.

We now obtain our main result.

Theorem 5.5   We have an embedding given by (1). The embedding is one-to-one, preserves the partial ordering relation and the least upper bound operation from , carries to , and carries to .

Proof.This result is obtained by combining Lemmas 5.3 and 5.4.

Theorem 5.6   Let be the embedding given by (1). Let be a recursively enumerable Turing degree other than and . Then the weak degree is incomparable with each of the specific weak degrees of Theorem 4.3.

Proof.By the Arslanov Completeness Criterion [12] we have . It remains to show that . This is obvious, because for any nonrecursive we have [27, §10, Theorem 1].

We finish by noting some generalizations of Theorem 5.5.

Remark 5.7   A set is said to be -REA if where is recursively enumerable and, for each , is recursively enumerable relative to and . A Turing degree is said to be -REA if it contains an -REA set. Note that any -REA set is a singleton. Hence by Lemma 5.2 we have for all -REA Turing degrees . Jockusch et al [13, Theorem 5.1] have generalized the Arslanov Completeness Criterion to -REA Turing degrees. In our terms, their result says that if is an -REA Turing degree for some , then if and only if , in which case . Therefore, letting denote the set of Turing degrees which are and -REA for some , we have as in Theorem 5.5 an embedding

which is one-to-one, preserves the partial ordering relation and the least upper bound operation from , and carries to and to . Moreover, for all other than and , we have as in Theorem 5.6 that is incomparable with .

Remark 5.8   More generally, given such that , we have an embedding

defined by . The embedding is one-to-one, preserves the partial ordering relation and least upper bound operation from , carries to , and carries to . If we set , we recover the embedding of Remark 5.7. If we set and restrict to , we recover the embedding of Theorem 5.5.

## Bibliography

1
Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp, and Theodore A. Slaman.
Comparing DNR and WWKL.
Journal of Symbolic Logic, 69:1089-1104, 2004.

2
Stephen Binns.
The Medvedev and Muchnik Lattices of Classes.
PhD thesis, Pennsylvania State University, August 2003.
VII + 80 pages.

3
Stephen Binns.
A splitting theorem for the Medvedev and Muchnik lattices.
Mathematical Logic Quarterly, 49:327-335, 2003.

4
Stephen Binns.
Small classes.
Archive for Mathematical Logic, 45:393-410, 2006.

5
Stephen Binns and Stephen G. Simpson.
Embeddings into the Medvedev and Muchnik lattices of classes.
Archive for Mathematical Logic, 43:399-414, 2004.

6
J. C. E. Dekker, editor.
Recursive Function Theory.
Proceedings of Symposia in Pure Mathematics. American Mathematical Society, 1962.
VII + 247 pages.

7
Natasha L. Dobrinen and Stephen G. Simpson.
Almost everywhere domination.
Journal of Symbolic Logic, 69:914-922, 2004.

8
Rodney G. Downey and Denis Hirschfeldt.
Algorithmic Randomness and Complexity.
May 2004.
Preprint, 305 pages, in preparation, to appear.

9
J.-E. Fenstad, I. T. Frolov, and R. Hilpinen, editors.
Logic, Methodology and Philosophy of Science VIII.
Number 126 in Studies in Logic and the Foundations of Mathematics. North-Holland, 1989.
XVII + 702 pages.

10
FOM e-mail list.
http://www.cs.nyu.edu/mailman/listinfo/fom/.
September 1997 to the present.

11
Mariagnese Giusto and Stephen G. Simpson.
Located sets and reverse mathematics.
Journal of Symbolic Logic, 65:1451-1480, 2000.

12
Carl G. Jockusch, Jr.
Degrees of functions with no fixed points.
In [9], pages 191-201, 1989.

13
Carl G. Jockusch, Jr., Manuel Lerman, Robert I. Soare, and Robert M. Solovay.
Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion.
Journal of Symbolic Logic, 54:1288-1323, 1989.

14
Carl G. Jockusch, Jr. and Robert I. Soare.
Degrees of members of classes.
Pacific Journal of Mathematics, 40:605-616, 1972.

15
Carl G. Jockusch, Jr. and Robert I. Soare.
classes and degrees of theories.
Transactions of the American Mathematical Society, 173:35-56, 1972.

16
Steven M. Kautz.
Degrees of Random Sets.
PhD thesis, Cornell University, 1991.
X + 89 pages.

17
Stephen C. Kleene.
Introduction to Metamathematics.
Van Nostrand, 1952.
X + 550 pages.

18
Masahiro Kumabe.
A fixed point free minimal degree.
1997.
Preprint, 48 pages.

19
Ming Li and Paul Vitányi.
An Introduction to Kolmogorov Complexity and its Applications.
Graduate Texts in Computer Science. Springer-Verlag, 2nd edition, 1997.
XX + 637 pages.

20
Per Martin-Löf.
The definition of random sequences.
Information and Control, 9:602-619, 1966.

21
Albert A. Muchnik.
On strong and weak reducibilities of algorithmic problems.
Sibirskii Matematicheskii Zhurnal, 4:1328-1341, 1963.
In Russian.

22
Piergiorgio Odifreddi.
Classical Recursion Theory.
Number 125 in Studies in Logic and the Foundations of Mathematics. North-Holland, 1989.
XVII + 668 pages.

23
Piergiorgio Odifreddi.
Classical Recursion Theory, Volume 2.
Number 143 in Studies in Logic and the Foundations of Mathematics. North-Holland, 1999.
XVI + 949 pages.

24
Mikhail G. Peretyatkin.
Finitely Axiomatizable Theories.
Siberian School of Algebra and Logic. Consultants Bureau, New York, 1997.
XIV + 294 pages.

25
Emil L. Post.
Recursively enumerable sets of positive integers and their decision problems.
Bulletin of the American Mathematical Society, 50:284-316, 1944.

26
Hartley Rogers, Jr.
Theory of Recursive Functions and Effective Computability.
McGraw-Hill, 1967.
XIX + 482 pages.

27
Gerald E. Sacks.
Degrees of Unsolvability.
Number 55 in Annals of Mathematics Studies. Princeton University Press, 1963.
IX + 174 pages.

28
Gerald E. Sacks.
The recursively enumerable degrees are dense.
Annals of Mathematics, 80:300-312, 1964.

29
Dana S. Scott.
Algebras of sets binumerable in complete extensions of arithmetic.
In [6], pages 117-121, 1962.

30
Stephen G. Simpson.
FOM: natural r.e. degrees; Pi01 classes.
FOM e-mail list [10], 13 August 1999.

31
Stephen G. Simpson.
FOM: priority arguments; Kleene-r.e. degrees; Pi01 classes.
FOM e-mail list [10], 16 August 1999.

32
Stephen G. Simpson.
Mass problems.
24 May 2004.
Preprint, 24 pages, submitted for publication.

33
Stephen G. Simpson.
Mass problems and randomness.
Bulletin of Symbolic Logic, 11:1-27, 2005.

34
Stephen G. Simpson and Theodore A. Slaman.
Medvedev degrees of subsets of .
July 2001.
Preprint, 4 pages, in preparation, to appear.

35
Robert I. Soare.
Recursively Enumerable Sets and Degrees.
Perspectives in Mathematical Logic. Springer-Verlag, 1987.
XVIII + 437 pages.

36
Alan M. Turing.
On computable numbers, with an application to the Entscheidungsproblem.
Proceedings of the London Mathematical Society, 42:230-265, 1936.

37
Michiel van Lambalgen.
Von Mises' definition of random sequences reconsidered.
Journal of Symbolic Logic, 52:725-755, 1987.

An extension of the
recursively enumerable Turing degrees

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 extre

The translation was initiated by Stephen G Simpson on 2008-04-28

Stephen G Simpson 2008-04-28