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$.
Origine | Fichiers produits par l'(les) auteur(s) |
---|