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 hierarchyinfinite time register machinesinfinite time computabilityITRMrecognizable realsGödel's L

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.

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

• scientific article; zbMATH DE number 3700811 (Why is no real title available?)
• scientific article; zbMATH DE number 803269 (Why is no real title available?)
• 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
• 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)

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

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)