Generalizing slightly the notions of a strict computability model and of a simulation between them, which were elaborated by Longley and Normann (2015, Higher-Order Computability), we define canonical strict computability models over certain categories and appropriate presheaves on them. We study the canonical total computability model over a category C and a covariant presheaf on C and the canonical partial computability model over a category C with pullbacks and a pullback preserving, covariant presheaf on C. These strict computability models are shown to be special cases of a strict computability model over a category C with a so-called base of computability and a pullback preserving, covariant presheaf on C, connecting in this way Rosolini's theory of dominions with the theory of computability models. All our notions and results are dualized by considering certain (contravariant) presheaves on appropriate categories.

Strict computability models over categories and presheaves

Petrakis, Iosif
2022-01-01

Abstract

Generalizing slightly the notions of a strict computability model and of a simulation between them, which were elaborated by Longley and Normann (2015, Higher-Order Computability), we define canonical strict computability models over certain categories and appropriate presheaves on them. We study the canonical total computability model over a category C and a covariant presheaf on C and the canonical partial computability model over a category C with pullbacks and a pullback preserving, covariant presheaf on C. These strict computability models are shown to be special cases of a strict computability model over a category C with a so-called base of computability and a pullback preserving, covariant presheaf on C, connecting in this way Rosolini's theory of dominions with the theory of computability models. All our notions and results are dualized by considering certain (contravariant) presheaves on appropriate categories.
2022
higher-order computability
category theory
presheaves
base of computability
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/1118936
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact