Strict computability models over categories and presheaves

Petrakis, Iosif (2022): Strict computability models over categories and presheaves. In: Journal of Logic and Computation, Vol. 32, No. 8, exac077: pp. 1815-1838

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.

• Item Type: Journal article
• Faculties: Mathematics, Computer Science and Statistics > Mathematics
• Subjects: 500 Science > 510 Mathematics
• ISSN: 0955-792X
• Language: English