Hi Noson, it might be worthwhile pointing out that it would be interesting to consider if similar results hold when one works over a foundations informed by computation, for instance over the effective topos. I guess this would mean working in the 2-category of fibrations over Eff, or similar, rather than of bare categories. Similarly, one could imagine redoing this in HoTT, but I guess one needs a good model (if one wants to work in a model) for the (\infty,2)-category of (pre-)categories. This is much more at the coalface, since the theory is less settled down that the traditional topos-theoretic/logical approach using realisability etc. Best regards, David On 19 September 2015 at 01:00, Noson S. Yanofsky <noson@sci.brooklyn.cuny.edu> wrote:
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/ ]
-- Dr David Roberts http://ncatlab.org/nlab/show/David+Roberts [For admin and other information see: http://www.mta.ca/~cat-dist/ ]