Taming Koepke's Zoo II: Register Machines
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2019
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910229965307904 |
|---|---|
| author | Carl, Merlin |
| author_facet | Carl, Merlin |
| contents | We study the computational strength of resetting $α$-register machines, a model of transfinite computability introduced by P. Koepke in \cite{K1}. Specifically, we prove the following strengthening of a result from \cite{C}: For an exponentially closed ordinal $α$, we have $L_α\models$ZF$^{-}$ if and only if COMP$^{\text{ITRM}}_α=L_{α+1}\cap\mathfrak{P}(α)$, i.e. if and only if the set of $α$-ITRM-computable subsets of $α$ coincides with the set of subsets of $α$ in $L_{α+1}$. Moreover, we show that, if $α$ is exponentially closed and $L_α\not\models$ZF$^{-}$, then COMP$^{\text{ITRM}}_α=L_{β(α)}\cap\mathfrak{P}(α)$, where $β(α)$ is the supremum of the $α$-ITRM-clockable ordinals, which coincides with the supremum of the $α$-ITRM-computable ordinals. We also determine the set of subsets of $α$ computable by an $α$-ITRM with time bounded below $δ$ when $δ>α$ is an exponentially closed ordinal smaller than the supremum of the $α$-ITRM-clockable ordinals. Moreover, we obtain some sufficient and necessary conditions on ordinals $α$ for which the $α$-wITRM-clockable ordinals are bounded by $α$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1907_09513 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Taming Koepke's Zoo II: Register Machines Carl, Merlin Logic We study the computational strength of resetting $α$-register machines, a model of transfinite computability introduced by P. Koepke in \cite{K1}. Specifically, we prove the following strengthening of a result from \cite{C}: For an exponentially closed ordinal $α$, we have $L_α\models$ZF$^{-}$ if and only if COMP$^{\text{ITRM}}_α=L_{α+1}\cap\mathfrak{P}(α)$, i.e. if and only if the set of $α$-ITRM-computable subsets of $α$ coincides with the set of subsets of $α$ in $L_{α+1}$. Moreover, we show that, if $α$ is exponentially closed and $L_α\not\models$ZF$^{-}$, then COMP$^{\text{ITRM}}_α=L_{β(α)}\cap\mathfrak{P}(α)$, where $β(α)$ is the supremum of the $α$-ITRM-clockable ordinals, which coincides with the supremum of the $α$-ITRM-computable ordinals. We also determine the set of subsets of $α$ computable by an $α$-ITRM with time bounded below $δ$ when $δ>α$ is an exponentially closed ordinal smaller than the supremum of the $α$-ITRM-clockable ordinals. Moreover, we obtain some sufficient and necessary conditions on ordinals $α$ for which the $α$-wITRM-clockable ordinals are bounded by $α$. |
| title | Taming Koepke's Zoo II: Register Machines |
| topic | Logic |
| url | https://arxiv.org/abs/1907.09513 |