The purpose of this note is to observe a generalization of the concept
"computable in..." to arbitrary partial combinatory algebras. For every partial
combinatory algebra (pca) A and every partial endofunction on A, a pca A[f] is constructed such that in A[f], the function f is representable by an element; a universal property of the construction is formulated in terms of Longley's 2-category of pcas and decidable applicative morphisms. It is proved that there is always a geometric inclusion from the realizability topos on A[f] into the one on A and that there is a meaningful preorder on the partial
endofunctions on A which generalizes Turing reducibility.
@article{1163775438,
author = {van Oosten, Jaap},
title = {A General Form of Relative Recursion},
journal = {Notre Dame J. Formal Logic},
volume = {47},
number = {1},
year = {2006},
pages = { 311-318},
language = {en},
url = {http://dml.mathdoc.fr/item/1163775438}
}
van Oosten, Jaap. A General Form of Relative Recursion. Notre Dame J. Formal Logic, Tome 47 (2006) no. 1, pp. 311-318. http://gdmltest.u-ga.fr/item/1163775438/