Betwixt Turing and Kleene

Abstract

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 Kleene’s approach, in the guise of Kleene’s quantifier ∃3.