The distribution of ITRM-recognizable reals

DOI10.1016/J.APAL.2014.04.010zbMATH Open1321.03055arXiv1208.1901OpenAlexW2294961809MaRDI QIDQ2453067FDOQ2453067

Authors: Merlin Carl 

Publication date: 6 June 2014

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

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.

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

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

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)

Cites Work

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

Cited In (9)

• All melodies are lost -- recognizability for weak and strong \(\alpha \)-register machines
• The lost melody theorem for infinite time Blum-Shub-Smale 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)