46 KAM Mathematical Colloquium
Prof. THEODORE A. SLAMAN
ASPECTS OF THE TURING JUMP
March 6, 2003
Lecture room in the 4th floor, Letenska 17, Praha
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 a proof that the
jump is definable in the partial order of the Turing degrees.