EUVIMEDEUVIMED entdecken
Crossref

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

Merlin Carl

Computability · 2026

DOI: 10.1177/22113568261468537 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Computability, 2026. Verfasst von Merlin Carl. Die Arbeit nennt 24 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Carl, M. (2026). The strange world of transfinite melodies—Recognizability for weak and strong infinite time α-register machines. Computability. https://doi.org/10.1177/22113568261468537

Vancouver

Carl M. The strange world of transfinite melodies—Recognizability for weak and strong infinite time α-register machines. Computability. 2026. doi:10.1177/22113568261468537

BibTeX
@article{Carl2026,
  author = {Carl, Merlin},
  title = {The strange world of transfinite melodies—Recognizability for weak and strong infinite time α-register machines},
  journal = {Computability},
  year = {2026},
  doi = {10.1177/22113568261468537}
}
Kostenlos starten →