Admissibles in Gaps

Abstract : We consider clockable ordinals for Infinite Time Turing Machines (ITTMs), i.e., halting times of ITTMs on the empty input. It is well-known that, in contrast to the writable ordinals, the set of clockable ordinals has ‘gaps’. In this paper, we show several results on gaps, mainly related to the admissible ordinals they may properly contain. We prove that any writable ordinal can occur as the order type of the sequence of admissible ordinals in such a gap. We give precise information on their ending points. We also investigate higher rank ordinals (recursively inaccessible, etc.). Moreover, we show that those gaps can have any reasonably effective length (in the sense of ITTMs) compared to their starting point.
Type de document :
Communication dans un congrès
CiE: Computability in Europe, Jun 2017, Turku, Finland. 13th Conference on Computability in Europe, LNCS (10307), pp.175-186, 2017, 〈10.1007/978-3-319-58741-7_18〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02020594
Contributeur : Isabelle Gouat <>
Soumis le : vendredi 15 février 2019 - 12:19:19
Dernière modification le : mardi 19 février 2019 - 01:22:30

Identifiants

Citation

Merlin Carl, Bruno Durand, Grégory Lafitte, Sabrina Ouazzani. Admissibles in Gaps. CiE: Computability in Europe, Jun 2017, Turku, Finland. 13th Conference on Computability in Europe, LNCS (10307), pp.175-186, 2017, 〈10.1007/978-3-319-58741-7_18〉. 〈lirmm-02020594〉

Partager

Métriques

Consultations de la notice

11