The distribution of ITRM-recognizable reals

DOI10.1016/J.APAL.2014.04.010MaRDI QIDQ2453067zbMATH OpenOpenAlexFDO

Authors Merlin Carl

Publication date 6 June 2014

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1208.1901

zbMATH Keywords

constructible hierarchyGödel's Linfinite time computabilityinfinite time register machinesITRMrecognizable reals

Mathematics Subject Classification ID

Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Higher-type and set recursion theory (03D65) Inner models, including constructibility, ordinal definability, and core models (03E45)

Abstract: Infinite Time Register Machines ($ITRM$'s) are a well-established machine model for infinitary computations. Their computational strength relative to oracles is understood, see e.g. Koepke (2009), Koepke and Welch (2011) and Koepke and Miller (2008). We consider the notion of recognizability, which was first formulated for Infinite Time Turing Machines in Hamkins and Lewis (200) and applied to $ITRM$'s in Carl et al. (2010). A real $x$ is $ITRM$-recognizable iff there is an $ITRM$-program $P$ such that $P^y$ stops with output 1 iff $y=x$, and otherwise stops with output 0. In Carl et al. (2010), it is shown that the recognizable reals are not contained in the computable reals. Here, we investigate in detail how the $ITRM$-recognizable reals are distributed along the canonical well-ordering ${<}_L$ of G"odel's constructible hierarchy $L$. In particular, we prove that the recognizable reals have gaps in ${<}_L$, that there is no universal $ITRM$ in terms of recognizability and consider a relativized notion of recognizability.

Review text

This paper explores the distribution of ITRM-recognizable reals in the hierarchy of the constructible reals. Infinite time register machines (ITRM) are a model for infinite computation introduced by \textit{P. Koepke} and \textit{R. Miller} [Lect. Notes Comput. Sci. 5028, 306--315 (2008; Zbl 1142.03347)]. They differ from other register machines in allowing arbitrary ordinals as running times. A real \(x\) is ITRM-recognizable if there is an ITRM program \(P\) such that \(P\) halts with output 1 if the input equals \(x\), and halts with output 0 otherwise. The ITRM-recognizable reals properly contain the ITRM-computable reals and are a proper subset of the constructible reals. The author proves that the ITRM-recognizable reals have gaps relative to the canonical well-ordering on Gödel's constructible sets.

Recommendations

• Optimal results on recognizability for infinite time register machines
• Logical Approaches to Computational Barriers
• ITRM-recognizability from random oracles
• Infinite time recognizability from generic oracles and the recognizable jump operator
• The basic theory of infinite time register machines

Cites work

• A generalised dynamical system, infinite time register machines, and \(\Pi^1_1\)-\(\mathrm{CA}_{0}\)
• Alternative finestructural and computational approaches to constructibility
• An Enhanced Theory of Infinite Time Register Machines
• Descriptive set theory
• scientific article; zbMATH DE number 3700811 (Why is no real title available?)
• scientific article; zbMATH DE number 803269 (Why is no real title available?)
• Infinite time Turing machines
• Logical Approaches to Computational Barriers
• On the Semantics of the Constructible Levels
• Ordinal computability
• The basic theory of infinite time register machines
• The fine structure of the constructible hierarchy
• What is the theory ZFC without power set?

Cited in

(9)

• Recognizable sets and Woodin cardinals: computation beyond the constructible universe
• The recognizability strength of infinite time Turing machines with ordinal parameters
• The lost melody theorem for infinite time Blum-Shub-Smale machines
• Optimal results on recognizability for infinite time register machines
• ITRM-recognizability from random oracles
• Infinite time recognizability from generic oracles and the recognizable jump operator
• The lost melody phenomenon
• Logical Approaches to Computational Barriers
• All melodies are lost -- recognizability for weak and strong -register machines

This page was built for publication: The distribution of ITRM-recognizable reals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2453067)