2023/02/14 by Sam Sanders, Sanders, Sam
Computer Science · Mathematics · #03D30 #03D75 #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #F.4.1 #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2302.07066
openalex publication_date 2023/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ∃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 ∃2 while the former are only computable in ∃3. While there is a great divide separating ∃2 and ∃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.