Partial combinatory algebras of functions

DOI10.1215/00294527-1499381zbMATH Open1248.03026arXiv0905.2665OpenAlexW2594284570MaRDI QIDQ654017FDOQ654017

Authors: Jaap van Oosten 

Publication date: 21 December 2011

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

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.

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

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

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)

Cited In (12)

• Continuous and monotone machines
• Collapsing partial combinatory algebras
• Title not available (Why is that?)
• Limiting 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
• Theory and Applications of Models of Computation
• Title not available (Why is that?)
• Ordered partial combinatory algebras
• Functions on universal algebras
• Extending 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)