Computability Learning Seminar

Wednesday, August 15, 2012 4:30 pm - 4:30 pm EDT (GMT -04:00)

Paul-Elliot Angles D'Auriac, Université Claude Bernard Lyon 1 and Pure Mathematics, University of Waterloo

"The bounded jump operator"

The jump is an operator on sets with nice properties. It is  
defined as the halting set relativized to oracles, but this
definition does not take into account how far we use the oracle. This  
leads to the fact that some of these nice properties
do not hold for the bounded Turing reducibility, such as the  
Schoenfield jump inversion. We will define another
jump operator, the bounded jump, taking care of the use of oracle, and  
prove that it behaves as the counterpart of the jump
for bounded reducibility (the Schoenfield jump inversion holds) and  
that the iterates of the empty set by this operator
also recreates a hierarchy: the Ershov hierarchy