Computability and Complexity of Categorical Structures

arXiv1507.05305MaRDI QIDQ6263745FDOQ6263745

Publication date: 19 July 2015

Abstract: We examine various categorical structures that can and cannot be constructed. We show that total computable functions can be mimicked by constructible functors. More generally, whatever can be done by a Turing machine can be constructed by categories. Since there are infinitary constructions in category theory, it is shown that category theory is strictly more powerful than Turing machines. In particular, categories can solve the Halting Problem for Turing machines. We also show that categories can solve any problem in the arithmetic hierarchy.

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10) Mathematical logic and foundations (03-XX) Category theory; homological algebra (18-XX)

This page was built for publication: Computability and Complexity of Categorical Structures

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