zbMATH — the first resource for mathematics

Partial combinatory algebras of functions. (English) Zbl 1248.03026
Summary: 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 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 geometric quotient of a realizability topos on a total combinatory algebra.

03B40 Combinatory logic and lambda calculus
03G30 Categorical logic, topoi
68N18 Functional programming and lambda calculus
Full Text: DOI arXiv