Rodney Downey and
Noam Greenberg (Wellington)
Strong Jump Traceability 1 and 2

Interactions between randomness and computability have been very fruitful in the last decade. Figuiera, Nies and Stephan [1] introduced a concept called strong jump traceability which was seen as a possible combinatorial characterization of K-triviality at the time. Though this characterization failed (Cholak, Downey and Greenberg [2]), the SJT reals turn out to have significant interactions with randomness such as, for instance, Greenberg, Hirschfeldt, Nies [3] and Greenberg-Turetsky [4]. Moreover, recent work of Diamondstone, Greenberg and Turetsky [6], has shown that these considerations apply outside of the computably enumerable sets, and, indeed, SJT is an intrinsically enumerable property.

Recent work of Downey and Greenberg [5], and then work in preparation of those authors wth Diamondstone and Turetsky has shown that this interaction of randomness and computability can work very effectively the other way. Downey and Greenberg show that a longstanding question on pseudo-jump inversion can be solved using SJT sets under inversion, via the sets that think that the halting problem is SJT relative to them.

In the first lecture Downey will introduce the concepts of strong jump traceability, discuss its motivations and look at the techniques devised to handle the class. He will also discuss the class under inversion.

In the second lecture, Greenberg will discuss the results connecting SJT reals with randomness and benign cost functions, and the class of Demuth random reals. Given time he will also discuss the intrinsic enumerability of the class.

[1] S. Figueira, A. Nies and F. Stephan, Lowness properties and approximations of the jump, Ann. Pure Applied Logic 152 (2008), 51-66

[2] P. Cholak, R. Downey and N. Greenberg, Strong jump traceablilty I, the computably enumerable case, Advances in Mathematics, 217 (2008), 2045-2074.

[3] N. Greenberg, D. Hirschfeldt and A. Nies, Characterising the strongly jump-traceable sets via randomness, submitted

[4] N. Greenberg and D. Turetsky, Strong jump-traceability and Demuth randomness, submitted.

[5] R. Downey and N. Greenberg, Pseudo-jump inversion and SJT-hard sets, submitted.

[6] D. Diamondstone, N. Greenberg and D. Turetsky, Inherent enumerability of strong jump traceability, submitted.