The search for natural definability in the Turing degrees

Issue title: In Memory of S. Barry Cooper (1943–2015)

Guest editors: Benedikt Löwe

Article type: Research Article

Authors: Lewis-Pye, Andrew E.M.

Affiliations: Department of Mathematics, London School of Economics, London, UK. [email protected]

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

DOI: 10.3233/COM-170068

Journal: Computability, vol. 7, no. 2-3, pp. 189-235, 2018