A general form of relative recursion

DOI10.1305/NDJFL/1163775438zbMATH Open1113.03014arXivmath/0510189OpenAlexW2124223175MaRDI QIDQ866493FDOQ866493

Authors: Jaap van Oosten 

Publication date: 20 February 2007

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/math/0510189

Recommendations

• Relative and modified relative realizability
• Third-order functionals on partial combinatory algebras
• Partial combinatory algebras of functions
• Computability in partial combinatory algebras
• Effective operations of type 2 in PCAs

zbMATH Keywords

Turing reducibilityrealizability topospartial combinatory algebras

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Categorical logic, topoi (03G30) Topoi (18B25) Functional programming and lambda calculus (68N18)

Cited In (12)

• Functoriality of modified realizability
• Introduction to Turing categories
• More on Geometric Morphisms between Realizability Toposes
• Third-order functionals on partial combinatory algebras
• A notion of a computational step for partial combinatory algebras
• Effective operations of type 2 in PCAs
• Ordinal analysis of partial combinatory algebras
• Arithmetical conservation results
• Extensions of Scott's graph model and Kleene's second algebra
• A Generalized Modality for Recursion
• Characterizing partitioned assemblies and realizability toposes
• Computability in partial combinatory algebras

This page was built for publication: A general form of relative recursion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q866493)