COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > SJT-hardness and pseudo-jump inversion

## SJT-hardness and pseudo-jump inversionAdd to your list(s) Download to your calendar using vCal - Turetsky, D (Victoria University of Wellington)
- Thursday 05 July 2012, 09:00-10:00
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Semantics and Syntax: A Legacy of Alan Turing 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. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsDiscrete Analysis Seminar 2d to 3d equation sets and implication of super massive blackholes Technology Enterprise Group Seminar Series## Other talksSolving the Reproducibility Crisis Atmospheric Structure Revealed by Refraction of Routine Radio Transmissions from Civil Aircraft. The cardinal points and the structure of geographical knowledge in the early twelfth century Joseph Banks: science, culture and the remaking of the Indo-Pacific world Imaging techniques and novel tools for early detection and intervention |