Embeddings between partial combinatory algebras

DOI10.1215/00294527-2023-0002MaRDI QIDQ6158341zbMATH OpenOpenAlexFDO

Authors Anton Golov, Sebastiaan A. Terwijn

Publication date 31 May 2023

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

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

zbMATH Keywords

embeddingsenumeration degreespartial combinatory algebraTuring degrees

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Other Turing degree structures (03D28) Applications of computability and recursion theory (03D80)

Abstract: Partial combinatory algebras are algebraic structures that serve as generalized models of computation. In this paper, we study embeddings of pcas. In particular, we systematize the embeddings between relativizations of Kleene's models, of van Oosten's sequential computation model, and of Scott's graph model, showing that an embedding between two relativized models exists if and only if there exists a particular reduction between the oracles. We obtain a similar result for the lambda calculus, showing in particular that it cannot be embedded in Kleene's first model.

Recommendations

• Computability in partial combinatory algebras
• On the existence of extensional partial combinatory algebras
• Extensions of Scott's graph model and Kleene's second algebra
• Collapsing partial combinatory algebras
• Ordinal analysis of partial combinatory algebras

Cites work

• A sufficient condition for completability of partial combinatory algebras
• Classical recursion theory. The theory of functions and sets of natural numbers
• Classical recursion theory. Vol. II
• Constructivism in mathematics. An introduction. Volume II
• Extensional realizability for intuitionistic set theory
• Higher-order computability
• scientific article; zbMATH DE number 3900744 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 3503199 (Why is no real title available?)
• scientific article; zbMATH DE number 3556031 (Why is no real title available?)
• scientific article; zbMATH DE number 1405588 (Why is no real title available?)
• scientific article; zbMATH DE number 3216177 (Why is no real title available?)
• scientific article; zbMATH DE number 3349781 (Why is no real title available?)
• Ordinal analysis of partial combinatory algebras
• Realizability and recursive set theory
• Realizability. An introduction to its categorical side
• The lambda calculus. Its syntax and semantics. Rev. ed.
• Theorie der Numerierungen I
• Uniformly Reflexive Structures: On the Nature of Godelizations and Relative Computability

Cited in

(8)

• Embeddings of generalized effect algebras into complete effect algebras
• Collapsing partial combinatory algebras
• Letterplace
• The complexity of completions in partial combinatory algebra
• Completions of Kleene's second model
• Fixed point theorems in computability theory
• Computable structure theory of partial combinatory algebras
• Partiality. I: Embedding relation algebras

This page was built for publication: Embeddings between partial combinatory algebras

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