A general form of relative recursion

DOI10.1305/NDJFL/1163775438MaRDI QIDQ866493zbMATH OpenOpenAlexFDO

Authors Jaap van Oosten

Publication date 20 February 2007

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

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

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)

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.

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

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
• Arithmetical conservation results
• Extensions of Scott's graph model and Kleene's second algebra
• Ordinal analysis of partial combinatory algebras
• 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)