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