Third-order functionals on partial combinatory algebras

DOI10.1016/J.APAL.2022.103205zbMATH Open1502.18008arXiv2103.09000OpenAlexW3138695222MaRDI QIDQ2105095FDOQ2105095

Authors: Jetze Zoethout 

Publication date: 8 December 2022

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Abstract: Computability relative to a partial function $f$ on the natural numbers can be formalized using the notion of an oracle for this function $f$. This can be generalized to arbitrary partial combinatory algebras, yielding a notion of `adjoining a partial function to a partial combinatory algebra $A$'. A similar construction is known for second-order functionals, but the third-order case is more difficult. In this paper, we prove several results for this third-order case. Given a third-order functional $Phi$ on a partial combinatory algebra $A$, we show how to construct a partial combinatory algebra $A[Phi]$ where $Phi$ is `computable', and which has a `lax' factorization property. Moreover, we show that, on the level of first-order functions, the effect of making a third-order functional computable can be described as adding an oracle for a first-order function.

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

Recommendations

• Effective operations of type 2 in PCAs
• Partial combinatory algebras of functions
• On (co)products of partial combinatory algebras, with an application to pushouts of realizability toposes
• Internal partial combinatory algebras and their slices
• Ordered partial combinatory algebras

zbMATH Keywords

realizabilitypartial combinatory algebrahigher-order computability

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) Combinatory logic and lambda calculus (03B40) Categorical logic, topoi (03G30) Topoi (18B25) Higher-type and set recursion theory (03D65) Categories of machines, automata (18B20)

Cites Work

• Realizability. An introduction to its categorical side
• Higher-order computability
• Title not available (Why is that?)
• Ordered partial combinatory algebras
• Partial combinatory algebras of functions
• Geometric morphisms of realizability toposes
• A general form of relative recursion
• More on Geometric Morphisms between Realizability Toposes
• Internal partial combinatory algebras and their slices
• Effective operations of type 2 in PCAs

Cited In (7)

• The cardinality of functionally complete algebras on a three element set
• A general form of relative recursion
• More on Geometric Morphisms between Realizability Toposes
• Functional Pearls
• The Ohm-Rush content function III: Completion, globalization, and power-content algebras
• Effective operations of type 2 in PCAs
• Ordinal analysis of partial combinatory algebras

This page was built for publication: Third-order functionals on partial combinatory algebras

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