The strange world of transfinite melodies—Recognizability for weak and strong infinite time α-register machines

Abstract

For exponentially closed ordinals α , we consider recognizability of constructible subsets of α for α -(w)ITRMs and their distribution in the constructible hierarchy. In particular, for α -ITRMs, we show that there are lost melodies that are recognizable without parameters for all α and that iterated recognizability is absolute between L and V for most values of α ; moreover, we generalize the “all or nothing”-phenomenon that was hitherto known only for the case α = ω to a proper class of α . For α -wITRMs, we offer a complete characterization of those α for which lost melodies exist and show that the relation between the sets of computable and recognizable subsets of α varies wildly, depending on α : The computable sets may be included among the recognizable sets (which is usually the case in ordinal computability), but there are also class many values of α for which the set of recognizable sets is empty and others for which the set of recognizable sets is non-empty, but disjoint from the set of computable sets. This paper is an extension of our paper in the CiE 2023 proceedings.

The authors' abstract, as published at the source. Computability, 2026 · DOI ↗