The non-normal abyss in Kleene's computability theory

DOI10.1007/978-3-031-36978-0_4arXiv2302.07066OpenAlexW4384789053MaRDI QIDQ6149028FDOQ6149028

Sam Sanders

Publication date: 12 January 2024

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Kleene's computability theory based on his S1-S9 computation schemes constitutes a model for computing with objects of any finite type and extends Turing's `machine model' which formalises computing with real numbers. A fundamental distinction in Kleene's framework is between normal and non-normal functionals where the former compute the associated Kleene quantifier $exist{s}^n$ and the latter do not. Historically, the focus was on normal functionals, but recently new non-normal functionals have been studied, based on well-known theorems like the uncountability of the reals. These new non-normal functionals are fundamentally different from historical examples like Tait's fan functional: the latter is computable from $exist{s}^2$ while the former are only computable in $exist{s}^3$. While there is a great divide separating $exist{s}^2$ and $exist{s}^3$, we identify certain closely related non-normal functionals that fall on different sides of this abyss. Our examples are based on mainstream mathematical notions, like quasi-continuity, Baire classes, and semi-continuity.

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

Mathematics Subject Classification ID

Logic in computer science (03B70) Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Recursive Functionals and Quantifiers of Finite Types I
• Higher-Order Computability
• Pincherle's theorem in reverse mathematics and computability theory
• The Axiom of Choice in computability theory and Reverse Mathematics with a cameo for the Continuum Hypothesis
• Cousin’s lemma in second-order arithmetic
• Iterated inductive definitions and subsystems of analysis: recent proof-theoretical studies
• Sums of quasicontinuous functions defined on pseudometrizable spaces
• ON THE UNCOUNTABILITY OF
• On the Products of Bounded Darboux Baire One Functions
• A note on real cliquish functions
• Open sets in computability theory and reverse mathematics
• There are \(2^{\mathfrak{c}}\) quasicontinuous non Borel functions on uncountable Polish space
• USCO and quasicontinuous mappings
• On the Computability of the Fan Functional
• On the computational properties of basic mathematical notions

Cited In (1)

• Exploring the abyss in Kleene's computability theory

This page was built for publication: The non-normal abyss in Kleene's computability theory

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