Taming Koepke's Zoo II: Register Machines

2019/07/22 by Carl, Merlin
#FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.1907.09513

Abstract

We study the computational strength of resetting α-register machines, a model of transfinite computability introduced by P. Koepke in \citeK1. Specifically, we prove the following strengthening of a result from \citeC: For an exponentially closed ordinal α, we have L_α\modelsZF^- if and only if COMP^ITRM_α=L_α+1∩\mathfrakP(α), 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\modelsZF^-, then COMP^ITRM_α=L_β(α)∩\mathfrakP(α), 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 α.

Related

• Lower bounds on β(α) and other properties of α-ITRMs
• The strange world of transfinite Melodies -- Recognizability for weak and strong infinite time α-register machines
• Recognizable sets and Woodin cardinals: Computation beyond the constructible universe
• Space-Bounded OTMs and REG^∞
• The Lost Melody Phenomenon