A lightface analysis of the differentiability rank
From MaRDI portal
Abstract: We examine the computable part of the differentiability hierarchy defined by Kechris and Woodin. In that hierarchy, the rank of a differentiable function is an ordinal less than omega_1 which measures how complex it is to verify differentiability for that function. We show that for each recursive ordinal alpha>0, the set of Turing indices of C[0,1] functions that are differentiable with rank at most alpha is Pi_{2 alpha + 1}-complete. This result is expressed in the notation of Ash and Knight.
Recommendations
Cites work
- A recursive function, defined on a compact interval and having a continuous derivative that is not recursive
- Computable structures and the hyperarithmetical hierarchy
- Hyperarithmetical Index Sets in Recursion Theory
- Index sets for computable differential equations
- On the definitions of computable real continuous functions
- On the Denjoy rank, the Kechris-Woodin rank and the Zalcwasser rank
- Ranks of differentiable functions
- Subsystems of second order arithmetic
- The Slaman-Wehner theorem in higher recursion theory
Cited in
(9)- On the complexity of continuous functions differentiable on cocountable sets
- Three ordinal ranks for the set of differentiable functions
- Computable analysis and classification problems
- Computable structures and operations on the space of continuous functions
- Index sets for computable differential equations
- Ranks of differentiable functions
- \(K\)-quasiderivations
- Computable classifications of continuous, transducer, and regular functions
- An effective analysis of the Denjoy rank
This page was built for publication: A lightface analysis of the differentiability rank
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921032)
