# SAS

## Seminar

### SJT-hardness and pseudo-jump inversion

Turetsky, D (Victoria University of Wellington)
Thursday 05 July 2012, 09:00-10:00

Seminar Room 1, Newton Institute

#### Abstract

Tracing was introduced to computability theory by Terwijn and Zambella, who used it to characterize the degrees which are low for Schnorr randomness. Zambella observed that tracing also has a relationship to K-triviality, which was strengthened by Nies and then later others. A trace for a partial function f is a sequence of finite sets (T_z) with f(z) in T_z for all z in the domain of f. A trace (T_z) is c.e. if the T_z are uniformly c.e. sets. An order function is a total, nondecreasing, unbounded positive function. If h is an order, a trace (T_z) is an h-trace if h(z) bounds the size of T_z. A set is called jump-traceable (JT) if every partial function it computes has a c.e. h-trace for some computable order h. A set is called strongly jump-traceable (SJT) if every partial function it computes has a c.e. h-trace for every computable order h. Figuiera et al. constructed a non-computable c.e. set which is SJT. This gives a natural pseudo-jump operator. Pseudo-jump inverting this SJT-operator gives a set A such that the halting problem looks SJT relative to A. That is, for every partial function computable from the halting problem, and every computable order h, there is an h-trace which is uniformly c.e. relative to A. Such a set is called SJT-hard. Downey and Greenberg showed that there is a non-computable c.e. set E which is computable from every c.e. SJT-hard set. Thus the SJT-operator cannot be pseudo-jump inverted outside of the cone above E. We strengthen this result, showing that E can be made super high.

#### Video

Available Video Formats