An algorithmic approach to characterizations of admissibles - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2019

An algorithmic approach to characterizations of admissibles

Bruno Durand
  • Function : Author
  • PersonId : 1050434
Grégory Lafitte
  • Function : Author
  • PersonId : 943012


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.
No file

Dates and versions

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



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⟩
82 View
0 Download



Gmail Facebook X LinkedIn More