solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看2935次
Computability and Complexity of Categorical Structures. (arXiv:1507.05305v2 [cs.CC] UPDATED)
来源于:arXiv
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. 查看全文>>