Taming Koepke's Zoo II: Register Machines

Abstract

We study the computational strength of resetting $\alpha$-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 $\alpha$, we have $L_{\alpha }\models$ZF${}^{-}$ if and only if COMP${}_{\alpha }^{\text{ITRM}}=L_{\alpha +1}\cap \mathfrak{P}(\alpha )$, i.e. if and only if the set of $\alpha$-ITRM-computable subsets of $\alpha$ coincides with the set of subsets of $\alpha$ in $L_{\alpha +1}$. Moreover, we show that, if $\alpha$ is exponentially closed and $L_{\alpha }/\models$ZF${}^{-}$, then COMP${}_{\alpha }^{\text{ITRM}}=L_{\beta (\alpha )}\cap \mathfrak{P}(\alpha )$, where $\beta (\alpha )$ is the supremum of the $\alpha$-ITRM-clockable ordinals, which coincides with the supremum of the $\alpha$-ITRM-computable ordinals. We also determine the set of subsets of $\alpha$ computable by an $\alpha$-ITRM with time bounded below $\delta$ when $\delta >\alpha$ is an exponentially closed ordinal smaller than the supremum of the $\alpha$-ITRM-clockable ordinals. Moreover, we obtain some sufficient and necessary conditions on ordinals $\alpha$ for which the $\alpha$-wITRM-clockable ordinals are bounded by $\alpha$.

References in corpus (1)

• Optimal Results on ITRM-recognizability

Cited by in corpus (1)

• Space and Time Complexity for Infinite Time Turing Machines