zbMATH — the first resource for mathematics

Local computability for ordinals. (English) Zbl 1433.03118
Bonizzoni, Paola (ed.) et al., The nature of computation. Logic, algorithms, applications. 9th conference on computability in Europe, CiE 2013, Milan, Italy, July 1–5, 2013. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 7921, 161-170 (2013).
Summary: We examine the extent to which well orders satisfy the properties of local computability, which measure how effectively the finite suborders of the ordinal can be presented. Known results prove that all computable ordinals are perfectly locally computable, whereas \(\omega_1^{\mathrm{CK}}\) and larger countable ordinals are not. We show that perfect local computability also fails for uncountable ordinals, and that ordinals \(\alpha\geq \omega_1^{\mathrm{CK}}\) are \(\theta \)-extensionally locally computable for all \(\theta<\omega_1^{\mathrm{CK}}\), but not when \(\theta>\omega_1^{\mathrm{CK}}\), nor when \(\theta=\omega_1^{\mathrm{CK}}\leq\alpha<\omega_1^{\mathrm{CK}}\cdot\omega\).
For the entire collection see [Zbl 1268.68007].
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
03E10 Ordinal and cardinal numbers
Full Text: DOI