Computability and Complexity of Categorical Structures

Computability and Complexity of Categorical Structures

[Noson S. Yanofsky]

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

Re: Computability and Complexity of Categorical Structures

[David Roberts]

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

Re: Computability and Complexity of Categorical Structures

[Steve Vickers]

Dear Noson,

It seems to me it's an oversimplification to say that categories can solve the Halting Problem. There's a logical principle involved.

In your proof on p.23, the central step is that if H: ω -> 2 is a functor (where ω and 2 are the posets of natural numbers and {0,1}), then it  has a colimit H': 1 -> 2. H(t) describes whether the computation has halted  by step t. (By the way, you use ω_i, the indiscreet natural numbers, for the type of t. That's a typo, isn't it? Since 2 is antisymmetric, that would imply H is constant.)

Does the colimit exist? That's not a fact of pure category theory, but a logical principle of "omniscience". If you go beyond classical logic (and category theory facilitates this) then the colimit might not exist.

For example, it will not work in a topos. To find the colimit you will need to embed 2 in Ω, the poset on the subobject classifier. There you still have the classical objects 0 and 1 (false and true), but also intermediate objects corresponding to truth values of other propositions such as "this computation halts". This switch from 2 to Ω corresponds to relaxing decidability to semidecidability - and semidecidability of the halting problem is trivial.

If my calculations are correct, you can see this in the topos of sheaves over the 1-point compactification of ω. This is the classifying topos for functors H, and the generic H has no colimit.

An alternative way to understand this is what you see in denotational semantics. Here, when a map to 2 takes the value 0 ("bottom"), that is interpreted  as meaning that the assignment of result to argument gets ensnared in a divergence.

Regards,

Steve.

> On 18 Sep 2015, at 16:30, 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/ ]

RE: Computability and Complexity of Categorical Structures

[Noson S. Yanofsky]

Dear Steve,

Thanks for taking the interest in the paper. 

Whether or not the colimit exists depends on which category you are in. In my paper the colimit is taken in the category of small categories where it does exist. Like you point out, (and David Roberts pointed out in a previous post) you might want to do some of this stuff in other categories such as the effective topos etc where this colimit would not exist. I do not know if the category of small categories is "omniscient" or not, and if that is a good thing or a bad thing, but the result stands.

(It is not a typo. Since 2 is indiscreet 0-->1 once the output goes to 1 it must stay in 1. This is exactly what Halt(x,y,t) does. Once it halts it stays halted. But all the outputs can remain 0.) 

All the best,
Noson

-----Original Message-----
From: Steve Vickers [mailto:s.j.vickers@cs.bham.ac.uk] 
Sent: Monday, September 21, 2015 6:10 AM
To: Noson S. Yanofsky
Cc: categories@mta.ca
Subject: Re: categories: Computability and Complexity of Categorical Structures

Dear Noson,

It seems to me it's an oversimplification to say that categories can solve the Halting Problem. There's a logical principle involved.

In your proof on p.23, the central step is that if H: ω -> 2 is a functor (where ω and 2 are the posets of natural numbers and {0,1}), then it has a colimit H': 1 -> 2. H(t) describes whether the computation has halted by step t. (By the way, you use ω_i, the indiscreet natural numbers, for the type of t. That's a typo, isn't it? Since 2 is antisymmetric, that would imply H is constant.)

Does the colimit exist? That's not a fact of pure category theory, but a logical principle of "omniscience". If you go beyond classical logic (and category theory facilitates this) then the colimit might not exist.

For example, it will not work in a topos. To find the colimit you will need to embed 2 in Ω, the poset on the subobject classifier. There you still have the classical objects 0 and 1 (false and true), but also intermediate objects corresponding to truth values of other propositions such as "this computation halts". This switch from 2 to Ω corresponds to relaxing decidability to semidecidability - and semidecidability of the halting problem is trivial.

If my calculations are correct, you can see this in the topos of sheaves over the 1-point compactification of ω. This is the classifying topos for functors H, and the generic H has no colimit.

An alternative way to understand this is what you see in denotational semantics. Here, when a map to 2 takes the value 0 ("bottom"), that is interpreted as meaning that the assignment of result to argument gets ensnared in a divergence.

Regards,

Steve.


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

Re: Computability and Complexity of Categorical Structures

[Steve Vickers]

Dear Noson -

On 21/09/2015 14:42, Noson S. Yanofsky wrote:
> Dear Steve,
>
> Thanks for taking the interest in the paper.
>
> Whether or not the colimit exists depends on which category you are
> in. In my paper the colimit is taken in the category of small
> categories where it does exist. Like you point out, (and David
> Roberts pointed out in a previous post) ...

(I don't seem to have David's post. Apologies if I'm repeating what he
said.)

> ... you might want to do some of
> this stuff in other categories such as the effective topos etc where
> this colimit would not exist. I do not know if the category of small
> categories is "omniscient" or not, and if that is a good thing or a
> bad thing, but the result stands.

You seem to be shifting uncertainly between the category where colimits
may or may not exist and a category (e.g. Set or a topos) that provides
an ambient logic for your mathematics.

Do you assume that 2 has all colimits? (Then the proof for the halting
problem says take the colimit of the diagram H: ?? -> 2. You've
parameterized that by x and y for program and data, but the essence of
the argument can be seen even without those.) Or even those colimits of
the specific form H? If so, then you are using a logical principle of
your ambient mathematics, not pure category theory.

>
> (It is not a typo. Since 2 is indiscreet 0-->1 once the output goes
> to 1 it must stay in 1. This is exactly what Halt(x,y,t) does. Once
> it halts it stays halted. But all the outputs can remain 0.)

"Indiscrete" means for each pair of objects x, y, there is a unique
morphisms from x to y. From your definition on p.4, 2 is not indiscrete,
since there is no morphism 1 -> 0. From the definition on p.14, ??_i is
indiscrete. Suppose you have a functor H: ??_i -> 2.
For any n you have H(0 -> n): H(0) -> H(n) and H(n -> 0): H(n) -> H(0).
Hence, by antisymmetry in the poset 2, H(n) = H(0). What you are saying
in words is captured by a functor from ?? (poset) to 2, not from ??_i to 2.

Steve.

>
> All the best, Noson
>
> -----Original Message----- From: Steve Vickers
> [mailto:s.j.vickers@cs.bham.ac.uk] Sent: Monday, September 21, 2015
> 6:10 AM To: Noson S. Yanofsky Cc: categories@mta.ca Subject: Re:
> categories: Computability and Complexity of Categorical Structures
>
> Dear Noson,
>
> It seems to me it's an oversimplification to say that categories can
> solve the Halting Problem. There's a logical principle involved.
>
> In your proof on p.23, the central step is that if H: ?? -> 2 is a
> functor (where ?? and 2 are the posets of natural numbers and {0,1}),
> then it has a colimit H': 1 -> 2. H(t) describes whether the
> computation has halted by step t. (By the way, you use ??_i, the
> indiscreet natural numbers, for the type of t. That's a typo, isn't
> it? Since 2 is antisymmetric, that would imply H is constant.)
>
> Does the colimit exist? That's not a fact of pure category theory,
> but a logical principle of "omniscience". If you go beyond classical
> logic (and category theory facilitates this) then the colimit might
> not exist.
>
> For example, it will not work in a topos. To find the colimit you
> will need to embed 2 in ??, the poset on the subobject classifier.
> There you still have the classical objects 0 and 1 (false and true),
> but also intermediate objects corresponding to truth values of other
> propositions such as "this computation halts". This switch from 2 to
> ?? corresponds to relaxing decidability to semidecidability - and
> semidecidability of the halting problem is trivial.
>
> If my calculations are correct, you can see this in the topos of
> sheaves over the 1-point compactification of ??. This is the
> classifying topos for functors H, and the generic H has no colimit.
>
> An alternative way to understand this is what you see in denotational
> semantics. Here, when a map to 2 takes the value 0 ("bottom"), that
> is interpreted as meaning that the assignment of result to argument
> gets ensnared in a divergence.
>
> Regards,
>
> Steve.
>

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