An algorithmic approach to characterizations of admissibles
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.