Computability on the space of countable ordinals
arXiv:1501.00386
Abstract
While there is a well-established notion of what a computable ordinal is, the question which functions on the countable ordinals ought to be computable has received less attention so far. We propose a notion of computability on the space of countable ordinals via a representation in the sense of computable analysis. The computability structure is characterized by the computability of four specific operations, and we prove further relevant operations to be computable. Some alternative approaches are discussed, too. As an application in effective descriptive set theory, we can then state and prove computable uniform versions of the Lusin separation theorem and the Hausdorff-Kuratowski theorem. Furthermore, we introduce an operator on the Weihrauch lattice corresponding to iteration of some principle over a countable ordinal.
arXiv commentcorrected Theorem 21 from v2
References in corpus (8)
- On the algebraic structure of Weihrauch degrees
- The degree structure of Weihrauch-reducibility
- Real Hypercomputation and Continuity
- Revising Type-2 Computation and Degrees of Discontinuity
- Non-deterministic computation and the Jayne-Rogers Theorem
- Total Representations
- The descriptive theory of represented spaces
- A topological view on algebraic computation models