Re: Computability and Complexity of Categorical Structures

[David Roberts <david.roberts@adelaide.edu.au>]

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/ ]