BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:SJT-hardness and pseudo-jump inversion - Turetsky\, D (Victoria Un
 iversity of Wellington)
DTSTART:20120705T080000Z
DTEND:20120705T090000Z
UID:TALK38869@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:Tracing was introduced to computability theory by Terwijn and 
 Zambella\, who used it to characterize the degrees which are low for Schno
 rr randomness. Zambella observed that tracing also has a relationship to K
 -triviality\, which was strengthened by Nies and then later others.\n \nA 
 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 ar
 e uniformly c.e. sets.\n \nAn order function is a total\, nondecreasing\, 
 unbounded positive function. If h is an order\, a trace (T_z) is an h-trac
 e if h(z) bounds the size of T_z.\n \nA set is called jump-traceable (JT) 
 if every partial function it computes has a c.e. h-trace for some computab
 le 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.\n \
 nFiguiera et al. constructed a non-computable c.e. set which is SJT. This 
 gives a natural pseudo-jump operator. Pseudo-jump inverting this SJT-opera
 tor gives a set A such that the halting problem looks SJT relative to A. T
 hat 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.\n \nDowney and Greenberg sh
 owed that there is a non-computable c.e. set E which is computable from ev
 ery c.e. SJT-hard set. Thus the SJT-operator cannot be pseudo-jump inverte
 d outside of the cone above E. We strengthen this result\, showing that E 
 can be made super high.\n\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR