Partial combinatory algebras of functions

DOI10.1215/00294527-1499381MaRDI QIDQ654017zbMATH OpenOpenAlexFDO

Authors Jaap van Oosten

Publication date 21 December 2011

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

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

zbMATH Keywords

partial combinatory algebrapreorder-enriched categoryrealizability topossequential function

Mathematics Subject Classification ID

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

Abstract: We employ the notions of `sequential function' and `interrogation' (dialogue) in order to define new partial combinatory algebra structures on sets of functions. These structures are analyzed using J. Longley's preorder-enriched category of partial combinatory algebras and decidable applicative structures. We also investigate total combinatory algebras of partial functions. One of the results is, that every realizability topos is a quotient of a realizability topos on a total combinatory algebra.

Recommendations

• Limiting partial combinatory algebras
• On the existence of extensional partial combinatory algebras
• On (co)products of partial combinatory algebras, with an application to pushouts of realizability toposes
• Collapsing partial combinatory algebras
• Ordered partial combinatory algebras

Cited in

(19)

• Functions on universal algebras
• Limiting partial combinatory algebras
• Third-order functionals on partial combinatory algebras
• Difference-restriction algebras of partial functions: axiomatisations and representations
• Internal partial combinatory algebras and their slices
• A uniform approach to domain theory in realizability models
• Ordered partial combinatory algebras
• Collapsing partial combinatory algebras
• Extending partial combinatory algebras
• scientific article; zbMATH DE number 1405588 (Why is no real title available?)
• Computable analysis and notions of continuity in \textsc{Coq}
• Continuous and monotone machines
• On (co)products of partial combinatory algebras, with an application to pushouts of realizability toposes
• Effective operations of type 2 in PCAs
• Theory and Applications of Models of Computation
• The Kleene-Post and Post's theorem in the calculus of inductive constructions
• Categorifying computable reducibilities
• A topos for extended Weihrauch degrees
• A general form of relative recursion

This page was built for publication: Partial combinatory algebras of functions

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