Writability power of ITTMs: ordinals and constructible sets - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Preprints, Working Papers, ... Year : 2024

Writability power of ITTMs: ordinals and constructible sets

Abstract

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
Origin Files produced by the author(s)

Dates and versions

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

Identifiers

  • HAL Id : lirmm-04505369 , version 1

Cite

Kenza Benjelloun, Bruno Durand, Grégory Lafitte. Writability power of ITTMs: ordinals and constructible sets. 2023. ⟨lirmm-04505369⟩
32 View
13 Download

Share

More