2021/09/03 by Dag Normann, Normann, Dag, Sam Sanders +1
Computer Science · #03B30 #03D30 #03D55 #03F35 #Cellular Automata and Applications #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.2109.01352
openalex publication_date 2021/09/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Turing's famous 'machine' model constitutes the first intuitively convincing framework for computing with real numbers. Kleene's computation schemes S1-S9 extend Turing's approach and provide a framework for computing with objects of any finite type. Various research programs have been proposed in which higher-order objects, like functions on the real numbers, are represented/coded as real numbers, so as to make them amenable to the Turing framework. It is then a natural question whether there is any significant difference between the Kleene approach or the Turing-approach-via-codes. Continuous functions being well-studied in this context, we study functions of bounded variation, which have at most countably many points of discontinuity. A central result is the Jordan decomposition theorem that a function of bounded variation on [0, 1] equals the difference of two monotone functions. We show that for this theorem and related results, the difference between the Kleene approach and the Turing-approach-via-codes is huge, in that full second-order arithmetic readily comes to the fore in Kleenes approach, in the guise of Kleene's quantifier ∃3.