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 algebrarealizability topospreorder-enriched categorysequential 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

(15)

• Extending partial combinatory algebras
• Ordered partial combinatory algebras
• Computable analysis and notions of continuity in \textsc{Coq}
• Continuous and monotone machines
• Internal partial combinatory algebras and their slices
• Collapsing partial combinatory algebras
• A general form of relative recursion
• Difference-restriction algebras of partial functions: axiomatisations and representations
• Third-order functionals on partial combinatory algebras
• scientific article; zbMATH DE number 1405588 (Why is no real title available?)
• Functions on universal algebras
• 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
• Limiting partial combinatory algebras

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)