The strange world of transfinite Melodies -- Recognizability for weak and strong infinite time $α$-register machines
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929405100556288 |
|---|---|
| author | Carl, Merlin |
| author_facet | Carl, Merlin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_04939 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The strange world of transfinite Melodies -- Recognizability for weak and strong infinite time $α$-register machines Carl, Merlin Logic 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. |
| title | The strange world of transfinite Melodies -- Recognizability for weak and strong infinite time $α$-register machines |
| topic | Logic |
| url | https://arxiv.org/abs/2205.04939 |