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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.