The non-normal abyss in Kleene's computability theory

DOI10.1007/978-3-031-36978-0_4OpenAlexW4384789053MaRDI QIDQ6149028FDOQ6149028

Authors Sam Sanders 

Publication date 12 January 2024

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

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

Mathematics Subject Classification ID

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

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.

Recommendations

• On the computational properties of basic mathematical notions
• On the computability of the fan functional
• Between Turing and Kleene
• The countably based functionals
• Betwixt Turing and Kleene

Cites work

• scientific article; zbMATH DE number 3820069 (Why is no real title available?)
• scientific article; zbMATH DE number 3688286 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 1215497 (Why is no real title available?)
• scientific article; zbMATH DE number 1870414 (Why is no real title available?)
• scientific article; zbMATH DE number 3291139 (Why is no real title available?)
• scientific article; zbMATH DE number 3334141 (Why is no real title available?)
• scientific article; zbMATH DE number 2236640 (Why is no real title available?)
• A note on real cliquish functions
• Cousin’s lemma in second-order arithmetic
• Higher-order computability
• Iterated inductive definitions and subsystems of analysis: recent proof-theoretical studies
• On the Products of Bounded Darboux Baire One Functions
• On the computability of the fan functional
• On the computational properties of basic mathematical notions
• On the uncountability of \(\mathbb{R}\)
• Open sets in computability theory and reverse mathematics
• Pincherle's theorem in reverse mathematics and computability theory
• Recursive Functionals and Quantifiers of Finite Types I
• Subsystems of second order arithmetic
• Sums of quasicontinuous functions defined on pseudometrizable spaces
• The axiom of choice in computability theory and reverse mathematics with a cameo for the continuum hypothesis
• There are \(2^{\mathfrak{c}}\) quasicontinuous non Borel functions on uncountable Polish space
• USCO and quasicontinuous mappings

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)