Recognizable sets and Woodin cardinals: computation beyond the constructible universe

DOI10.1016/j.apal.2017.12.007zbMath1453.03055arXiv1512.06101OpenAlexW2255305829MaRDI QIDQ1694811

Philipp Schlicht, Merlin Carl, Philip D. Welch

Publication date: 6 February 2018

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

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

zbMATH Keywords

inner modelsinfinite time Turing machinesalgorithmic randomnessWoodin cardinalseffective descriptive set theory

Mathematics Subject Classification ID

Descriptive set theory (03E15) Inner models, including constructibility, ordinal definability, and core models (03E45) Large cardinals (03E55) Turing machines and related notions (03D10) Algorithmic randomness and dimension (03D32)

Related Items

Effectivity and reducibility with ordinal Turing machines ⋮ RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY ⋮ All melodies are lost -- recognizability for weak and strong \(\alpha \)-register machines ⋮ The recognizability strength of infinite time Turing machines with ordinal parameters ⋮ The lost melody theorem for infinite time Blum-Shub-Smale machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algebraicity and implicit definability in set theory
• \(\lambda\)-structures and \(s\)-structures: translating the models
• \(\lambda\)-structures and \(s\)-structures: translating the iteration strategies
• Register computations on ordinals
• Inner models with many Woodin cardinals
• Projectively well-ordered inner models
• Thin equivalence relations and inner models
• The basic theory of infinite time register machines
• Infinite computations with random oracles
• Set theory. Exploring independence and truth
• The distribution of ITRM-recognizable reals
• Proper forcing and L(ℝ)
• Hypermachines
• An Outline of Inner Model Theory
• A Core Model Toolbox and Guide
• Degrees of rigidity for Souslin trees
• Minimality in the ${Δ^1}_2$-degrees
• Iteration Trees
• Infinite time Turing machines
• Set Theory
• Optimal Proofs of Determinacy
• Effective Mathematics of the Uncountable
• The Lost Melody Phenomenon
• New Computational Paradigms
• Logical Approaches to Computational Barriers
• Inner models and large cardinals