46 KAM Mathematical Colloquium

Prof. THEODORE A. SLAMAN

Berkeley

ASPECTS OF THE TURING JUMP

March 6, 2003 Lecture room in the 4th floor, Letenska 17, Praha 1 14:00 PM

Abstract

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.