Running summarizing tools on a new article

Check the paper below, then start its synthesis.


Between Turing and Kleene

Sam Sanders

20 pages, to appear in the Proceedings of LFCS22, Lecture Notes in Computer Science. Keywords: Computability theory, Kleene S1-S9, Turing machines

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 to computing with objects of any finite type. Both frameworks have their pros and cons and it is a natural question if there is an approach that marries the best of both the Turing and Kleene worlds. In answer to this question, we propose a considerable extension of the scope of Turing's approach. Central is a fragment of the Axiom of Choice involving continuous choice functions, going back to Kreisel-Troelstra and intuitionistic analysis. Put another way, we formulate a relation `is computationally stronger than' involving third-order objects that overcomes (many of) the pitfalls of the Turing and Kleene frameworks.

Submitted to arXiv on 09 Nov. 2021