An algorithmic approach to characterizations of admissibles - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

An algorithmic approach to characterizations of admissibles

Bruno Durand
  • Fonction : Auteur
  • PersonId : 1050434
Grégory Lafitte
  • Fonction : Auteur
  • PersonId : 943012

Résumé

Sacks proved that every admissible countable ordinal is the first admissible ordinal relatively to a real. We give an algorithmic proof of this result for constructibly countable admissibles. Our study is completed by an algorithmic approach to a generalization of Sacks’ theorem due to Jensen, that finds a real relatively to which a countable sequence of admissibles, having a compatible structure, constitutes the sequence of the first admissibles. Our approach deeply involves infinite time Turing machines. We also present different considerations on the constructible ranks of the reals involved in coding ordinals.
Fichier non déposé

Dates et versions

lirmm-02178788 , version 1 (10-07-2019)

Identifiants

Citer

Bruno Durand, Grégory Lafitte. An algorithmic approach to characterizations of admissibles. CiE 2019 - 15th Conference on Computability in Europe, Jul 2019, Durham, United Kingdom. pp.181-192, ⟨10.1007/978-3-030-22996-2_16⟩. ⟨lirmm-02178788⟩
84 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More