The recognizability strength of infinite time Turing machines with ordinal parameters

DOI10.1007/978-3-319-58741-7_20MaRDI QIDQ2011653zbMATHOpenAlexFDO

Authors Merlin Carl, Philipp Schlicht

Publication date 4 August 2017

Full work available at URL https://doi.org/10.1007/978-3-319-58741-7_20

Mathematics Subject Classification ID

Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Turing machines and related notions (03D10)

Recommendations

• Cardinal-recognizing infinite time Turing machines
• Infinite time recognizability from generic oracles and the recognizable jump operator
• Optimal results on recognizability for infinite time register machines
• Recognizable sets and Woodin cardinals: computation beyond the constructible universe
• A Survey of Infinite Time Turing Machines

Cites work

• scientific article; zbMATH DE number 1390284 (Why is no real title available?)
• Cardinal-recognizing infinite time Turing machines
• Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems
• Infinite time Turing machines
• Infinite time decidable equivalence relation theory
• Optimal results on recognizability for infinite time register machines
• RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY
• Recognizable sets and Woodin cardinals: computation beyond the constructible universe
• The distribution of ITRM-recognizable reals
• The lost melody phenomenon

Cited in

(8)

• All melodies are lost -- recognizability for weak and strong \(\alpha \)-register machines
• Recognizable sets and Woodin cardinals: computation beyond the constructible universe
• Ordinal machines and admissible recursion theory
• Effectivity and reducibility with ordinal Turing machines
• Cardinal-recognizing infinite time Turing machines
• Parameter-free uniformisation
• Optimal results on recognizability for infinite time register machines
• Infinite time recognizability from generic oracles and the recognizable jump operator

This page was built for publication: The recognizability strength of infinite time Turing machines with ordinal parameters

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