Skip to Main content Skip to Navigation
Conference papers

An algorithmic approach to characterizations of admissibles

Bruno Durand 1 Grégory Lafitte 1
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Document type :
Conference papers
Complete list of metadata
Contributor : Bruno Durand <>
Submitted on : Wednesday, July 10, 2019 - 10:49:16 AM
Last modification on : Monday, December 14, 2020 - 5:26:12 PM




Bruno Durand, Grégory Lafitte. An algorithmic approach to characterizations of admissibles. CiE: Computability in Europe, Jul 2019, Durham, United Kingdom. pp.181-192, ⟨10.1007/978-3-030-22996-2_16⟩. ⟨lirmm-02178788⟩



Record views