Abstract

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