We give an introduction to Turing categories, which are a convenient setting for the categorical study of abstract notions of computability. The concept of a Turing category first appeared in the work of Longo and Moggi; later, Di Paolo and Heller introduced the closely related recursion categories. One of the purposes of Turing categories is that they may be used to develop categorical formulations of recursion theory, but they also include other notions of computation, such as models of combinatory logic (...) and of the lambda calculus. In this paper our aim is to give an introduction to the basic structural theory, while at the same time illustrating how the notion is a meeting point for various other areas of logic and computation. We also provide a detailed exposition of the connection between Turing categories and partial combinatory algebras and show the sense in which the study of Turing categories is equivalent to the study of PCAs. (shrink)

We prove a generalization of Alex Heller's existence theorem for recursion categories; this generalization was suggested by work of Di Paola and Montagna on syntactic P-recursion categories arising from consistent extensions of Peano Arithmetic, and by the examples of recursion categories of coalgebras. Let B=BX be a uniformly generated isotypical B#-subcategory of an iteration category C, where X is an isotypical object of C. We give calculations for the existence of a weak Turing morphism in the Turing completion Tur of (...) B when C is separated; i.e., when connected domains in C are jointly epimorphic. Our proof generalizes as follows. Let D be a separated iteration category and let L : C → D be an iteration functor; i.e., a functor which preserves domains, coproducts, zero morphisms and the iteration operator; it is crucial for the generalization that an iteration functor need not preserve products. If L is faithful, then Tur is a recursion category. (shrink)