Computability and Complexity of Categorical Structures

["Noson S. Yanofsky" <noson@sci.brooklyn.cuny.edu>]

Dear Category Theorists,



I recently uploaded a new paper to the arxiv.



http://arxiv.org/abs/1507.05305



Title: Computability and Complexity of Categorical Structures

Author: Noson S. Yanofsky



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.



I am very interested in any criticisms and comments.



Sincerely,

Noson (Yanofsky)



[For admin and other information see: http://www.mta.ca/~cat-dist/ ]