The distribution of ITRM-recognizable reals (Q2453067)

This paper explores the distribution of ITRM-recognizable reals in the hierarchy of the constructible reals. Infinite time register machines (ITRM) are a model for infinite computation introduced by \textit{P. Koepke} and \textit{R. Miller} [Lect. Notes Comput. Sci. 5028, 306--315 (2008; Zbl 1142.03347)]. They differ from other register machines in allowing arbitrary ordinals as running times. A real \(x\) is ITRM-recognizable if there is an ITRM program \(P\) such that \(P\) halts with output 1 if the input equals \(x\), and halts with output 0 otherwise. The ITRM-recognizable reals properly contain the ITRM-computable reals and are a proper subset of the constructible reals. The author proves that the ITRM-recognizable reals have gaps relative to the canonical well-ordering on Gödel's constructible sets.