Exploring the abyss in Kleene’s computability theory

Article type: Research Article

Authors: Sanders, Sam^{; *}

Affiliations: Department of Philosophy II, RUB Bochum, Germany

Correspondence: [*] Corresponding author. sasander@me.com.

Abstract: Kleene’s computability theory based on the 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 ∃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, the weakest among which seems to be 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 ∃2, while the former are computable in ∃3 but not in weaker oracles. Of course, there is a great divide or abyss separating ∃2 and ∃3 and we identify slight variations of our new non-normal functionals that are again computable in ∃2, i.e. fall on different sides of this abyss. Our examples are based on mainstream mathematical notions, like quasi-continuity, Baire classes, bounded variation, and semi-continuity from real analysis.

Keywords: Kleene computability theory, fan functional, non-normal functionals, S1–S9, real analysis

DOI: 10.3233/COM-230475

Journal: Computability, vol. 13, no. 2, pp. 113-134, 2024