Aspects of the Turing Jump

Theodore A. Slaman

The Turing jump is the function which maps X, a set of natural numbers, to X′, the halting problem relative to X. X′ is the canonical example of an arithmetically definable set which is not recursive in X.

We will discuss two aspects of this remarkable function and its iterations. First, we will examine the thesis that the only robust definable way to produce a set from X which is strictly more complicated than X is to produce a set which is as least as complicated as X′. Second, we will discuss how this canonical aspect of the jump and of the double-jump leads to Shore and Slaman’s proof that the jump is definable in the partial order of the Turing degrees.

Address: Department of Mathematics, University of California, Berkeley, CA 94720-3840, USA

E-mail: slaman@math.berkeley.edu