Dominical categories: recursion theory without elements

DOI10.2307/2274352zbMath0649.03032OpenAlexW4239158956MaRDI QIDQ3794173

Alex Heller, Robert A. Di Paola

Publication date: 1987

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2274352

zbMATH Keywords

Rice's theoremGödel's incompleteness theoremalgebraizationdominical categoriesabstract formulation of recursion theorydominical recursion theory

Mathematics Subject Classification ID

Categorical logic, topoi (03G30) Abstract and axiomatic computability and recursion theory (03D75)

Related Items

Total maps of Turing categories ⋮ Timed Sets, Functional Complexity, and Computability ⋮ Categories of partial maps ⋮ Partial hyperdoctrines: categorical models for partial function logic and Hoare logic ⋮ Restriction categories II: Partial map classification ⋮ Presheaves over a join restriction category ⋮ Restriction categories as enriched categories ⋮ Many-one reductions and the category of multivalued functions ⋮ More existence theorems for recursion categories. ⋮ Inclusions for partiality ⋮ Precomplete Equivalence Relations in Dominical Categories ⋮ Restriction categories III: colimits, partial limits and extensivity ⋮ Boolean restriction categories and taut monads ⋮ Restriction categories. I: Categories of partial maps ⋮ Introduction to Turing categories ⋮ Monoidal computer III: a coalgebraic view of computability and complexity (extended abstract) ⋮ Boolean and classical restriction categories ⋮ Unnamed Item ⋮ Formalizing abstract computability: Turing categories in Coq ⋮ Diagonal fixed points in algebraic recursion theory ⋮ Aspects of Categorical Recursion Theory ⋮ Cocompletion of restriction categories