2022/05/10 by Merlin Carl, Carl, Merlin
Computer Science · Mathematics · #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.2205.04939
openalex publication_date 2022/05/10 · openalex created_date 2022/05/22 · openalex updated_date 2026/07/28
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 α, that the iterated recognizability is absolute between L and V for most values of α and generalize "all or nothing"-phenomenon known from ITRMs occurs for a proper class of α. For α-wITRMs, we offer a complete characterization of those α for which lost melodies exist and 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 such for which the set of recognizable sets is non-empty, but disjoint from the set of computable sets. %for class many values of α, the sets of α-wITRM-computable and α-wITRM-recognizable subsets of α are both non-empty, but disjoint, and, also for class many values of α, the set of α-wITRM-recognizable subsets of α is empty. This paper is an extension of our paper in the CiE 2023 proceedings.