Writability power of ITTMs: ordinals and constructible sets - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Pré-Publication, Document De Travail Année : 2024

Writability power of ITTMs: ordinals and constructible sets

Résumé

We present an optimal writability method for ordinals and Gödel’s constructible sets $L_\alpha$ by infinite time Turing machines (ITTMs). For ordinals, we obtain that the time needed to write a writable ordinal is either $\omega$, or the end of a clockability gap, or a limit of ends of such gaps. Our result is proved optimal and requires complex techniques for dealing with long gaps. As for Gödel’s constructible sets $L_\alpha$, we adapt our construction for writing ordinals for optimally writing $L_\alpha$ when $\alpha$ is ITTM-writable. We also obtain an optimal result (for closed enough $\alpha$’s): the time needed to compute $L_\alpha$ is the maximum between $\alpha$ and the ordinal time needed to write $\alpha$.
Fichier principal
Vignette du fichier
article2.pdf (128.93 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-04505369 , version 1 (14-03-2024)

Identifiants

  • HAL Id : lirmm-04505369 , version 1

Citer

Kenza Benjelloun, Bruno Durand, Grégory Lafitte. Writability power of ITTMs: ordinals and constructible sets. 2023. ⟨lirmm-04505369⟩
40 Consultations
20 Téléchargements

Partager

More