Sage Journals: Discover world-class research

Abstract

We give an introduction to the Turing degrees, aimed principally at those who have some experience with computability theory, but not necessarily with techniques specific to the study of the local degrees. The focus is on establishing which definable properties are satisfied by the degrees in the various jump classes, as introduced by Cooper and Soare in the 1970s. Along the way, we also point to a good number of open problems.

Keywords

Computability degrees Turing jump classes definability

Get full access to this article

View all access options for this article.

References

S.B.

Cooper, Distinguishing the arithmetical hierarchy, Preprint, Berkeley, 1972.

S.B.

Cooper, Computability Theory, Chapman & Hall, 2004.

S.B.

Cooper, The strong anticupping property for recursively enumerable degrees, Journal of Symbolic Logic54 (1989), 527–539. doi:10.2307/2274867.

Downey,

Greenberg,

A.E.M.

Lewis and

Montalbán, Extensions of embeddings below computably enumerable degrees, Transactions of the American Mathematical Society365 (2013), 2977–3018. doi:10.1090/S0002-9947-2012-05660-1.

Downey and

Hirschfeldt, Algorithmic Randomness and Complexity, Springer-Verlag, 2010.

Downey,

C.G.

Jockusch and

Stob, Array nonrecursive degrees and genericity, in: Computability, Enumerability, Unsolvability: Directions in Recursion Theory,

S.B.

Cooper,

T.A.

Slaman and

S.S.

Wainer, eds, London Mathematical Society Lecture Note Series, Vol. 224, Cambridge University Press, 1996, pp. 93–104.

Durrant,

Lewis-Pye,

Ng and

Riley, C.e. degrees and the meet property, Proceedings of the American Mathematical Society144 (2016), 1735–1744. doi:10.1090/proc/12808.

Ellison and

A.E.M.

Lewis, Joining up to the generalized high degrees, Proceeding of the American Mathematical Society138 (2010), 2949–2960. doi:10.1090/S0002-9939-10-10299-8.

Ellison and

A.E.M.

Lewis, The minimal cupping property, To appear.

10.

Greenberg,

Montalbán and

R.A.

Shore, Generalized high degrees have the complementation property, Journal of Symbolic Logic69 (2004), 1200–1220. doi:10.2178/jsl/1102022219.

11.

Ishmukhametov, Weak recursive degrees and a problem of Spector, in: Recursion Theory and Complexity: Proceedings of the International Workshop on Recursion Theory and Complexity Theory (WORCT’97), Kazan State University, Kazan, July 14–19, 1997,

M.M.

Arslanov and

Lempp, eds, de Gruyter Series in Logic and Its Applications, Vol. 2, Walter de Gruyter, 1999, pp. 81–89.

12.

C.G.

Jockusch, Simple proofs of some theorems on high degrees of unsolvability, Canadian Journal of Mathematics29 (1977), 1072–1080. doi:10.4153/CJM-1977-105-5.

13.

C.G.

Jockusch and

Shore, Pseudo jump operators I: The R.E. case, Transactions of the American Mathematical Society275 (1983), 599–609.

14.

C.G.

Joskusch and

D.B.

Posner, Double jumps of minimal degrees, Journal of Symbolic Logic43 (1978), 715–724. doi:10.2307/2273510.

15.

C.G.

Jockusch and

Soare,

Π_{1}^{0}

classes and degrees of theories, Transactions of the American Mathematical Society173 (1972), 33–56.

16.

S.C.

Kleene and

E.L.

Post, The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics59 (1954), 379–407. doi:10.2307/1969708.

17.

Kučera, Measure,

Π_{1}^{0}

classes and complete extensions of PA, in: Recursion Theory Week (Oberwolfach, 1984), Lecture Notes in Mathematics, Vol. 1141, Springer-Verlag, 1985, pp. 245–259. doi:10.1007/BFb0076224.

18.

Kučera, An alternative priority-free solution to Post’s problem, in: Mathematical Foundations of Computer Science: Proceedings of the 12th Symposium, Bratislava, Czechoslovakia, August 25–29, 1986,

Gruska,

Rovan and

Wiedermann, eds, Lecture Notes in Computer Science, Vol. 233, Springer-Verlag, pp. 493–500. doi:10.1007/BFb0016275.

19.

Lerman, Degrees of Unsolvability, Springer-Verlag, Berlin, 1983.

20.

Lerman, Degrees which do not bound minimal degrees, Annals of Pure and Applied Logic30 (1986), 249–276. doi:10.1016/0168-0072(86)90022-9.

21.

A.E.M.

Lewis,

Π_{1}^{0}

classes, strong minimal covers and hyperimmune-free degrees, Bulletin of the London Mathematical Society39 (2007), 892–910. doi:10.1112/blms/bdm083.

22.

A.E.M.

Lewis, Strong minimal covers and a question of Yates: The story so far, in: Logic Colloquium 2006, Cambridge University Press, 2006, pp. 213–228. doi:10.1017/CBO9780511605321.011.

23.

A.E.M.

Lewis, On a question of Slaman and Groszek, Proceedings of the American Mathematical Society136 (2008), 3663–3668. doi:10.1090/S0002-9939-08-09345-3.

24.

A.E.M.

Lewis, A note on the join property, Proceedings of the American Mathematical Society140 (2012), 707–714. doi:10.1090/S0002-9939-2011-10908-0.

25.

A.E.M.

Lewis, Minimal complements for degrees below 0′, Journal of Symbolic Logic69(4) (2004), 937–966. doi:10.2178/jsl/1102022208.

26.

A.E.M.

Lewis, The minimal complementation property above 0′, Mathematical Logic Quarterly51(5) (2005), 470–492. doi:10.1002/malq.200410044.

27.

A.E.M.

Lewis, A single minimal complement for the c.e. degrees, Transactions of the American Mathematical Society359 (2007), 5817–5865. doi:10.1090/S0002-9947-07-04331-0.

28.

A.E.M.

Lewis, Finite cupping sets, Archive for Mathematical Logic43 (2004), 845–858. doi:10.1007/s00153-004-0215-5.

29.

Martin, Classes of recursively enumerable sets and degrees of unsolvability, Zeit. Math. Log. Grund. Math.12 (1966), 295–310. doi:10.1002/malq.19660120125.

30.

Nies, Computability and Randomness, Oxford University Press, 2009.

31.

Nies, Coding methods in computability theory and complexity theory, Habilitation thesis, Universität Heidelberg, 1998.

32.

Nies,

R.A.

Shore and

T.A.

Slaman, Interpretability and definability in the recursively enumerable degrees, Proceedings of the London Mathematical Society (3)77(2) (1998), 241–291. doi:10.1112/S002461159800046X.

33.

Posner, The uppersemilattice of degrees

⩽ 0^{'}

is complemented, Journal of Symbolic Logic46 (1981), 705–713. doi:10.2307/2273220.

34.

Posner and

Robinson, Degrees joining to

0^{'}

, Journal of Symbolic Logic46 (1981), 714–722. doi:10.2307/2273221.

35.

Riley, Structural properties of the local Turing degrees, PhD thesis, University of Leeds, 2016.

36.

Sacks, A minimal degree less than

0^{'}

, Bulletin of the American Mathematical Society67 (1961), 416–419. doi:10.1090/S0002-9904-1961-10652-6.

37.

Sacks, Recursive enumerability and the jump operator, Transactions of the American Mathematical Society108 (1963), 223–239. doi:10.1090/S0002-9947-1963-0155747-3.

38.

Sasso, A minimal degree not realizing least possible jump, Journal of Symbolic Logic39 (1974), 571–574. doi:10.2307/2272899.

39.

Scott, Algebras of sets binumerable in complete extensions of arithmetic, in: Recursive Functions Theory, Proceedings of Symposia in Pure Mathematics, Vol. V, American Mathematical Society, Providence, RI, 1962, pp. 117–121. doi:10.1090/pspum/005/0141595.

40.

Shore and

Slaman, Defining the Turing jump, Mathematical Research Letters6(5–6) (1999), 711–722. doi:10.4310/MRL.1999.v6.n6.a10.

41.

Shore, Direct and local definitions of the Turing jump, Journal of Mathematical Logic7 (2007), 229–262. doi:10.1142/S0219061307000676.

42.

Simpson, First order theory of the degrees of recursive unsolvability, Annals of Mathematics105 (1977), 121–139. doi:10.2307/1971028.

43.

T.A.

Slaman and

J.R.

Steel, Complementation in the Turing degrees, Journal of Symbolic Logic54(1) (1989), 160–176. doi:10.2307/2275022.

44.

T.A.

Slaman and

Woodin, Definability in the Turing degrees, Illinois Journal of Mathematics30 (1986), 320–334.

45.

Soare, Automorphisms of the lattice of recursively enumerable sets, Bulletin of the American Mathematical Society80 (1974), 53–58. doi:10.1090/S0002-9904-1974-13350-1.

46.

Spector, On degrees of recursive unsolvability, Annals of Mathematics64 (1956), 581–592. doi:10.2307/1969604.

47.

S.A.

Terwijn and

Zambella, Computational randomness and lowness, Journal of Symbolic Logic66 (2001), 1199–1205. doi:10.2307/2695101.

The search for natural definability in the Turing degrees

Abstract

Keywords

Get full access to this article

References