From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/8698 Path: news.gmane.org!not-for-mail From: "Noson S. Yanofsky" Newsgroups: gmane.science.mathematics.categories Subject: Computability and Complexity of Categorical Structures Date: Fri, 18 Sep 2015 11:30:42 -0400 Message-ID: Reply-To: "Noson S. Yanofsky" NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1442792792 12034 80.91.229.3 (20 Sep 2015 23:46:32 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 20 Sep 2015 23:46:32 +0000 (UTC) To: Original-X-From: majordomo@mlist.mta.ca Mon Sep 21 01:46:21 2015 Return-path: Envelope-to: gsmc-categories@m.gmane.org Original-Received: from smtp3.mta.ca ([138.73.7.22]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1ZdoJI-0000ZO-U9 for gsmc-categories@m.gmane.org; Mon, 21 Sep 2015 01:46:21 +0200 Original-Received: from mlist.mta.ca ([138.73.1.63]:49610) by smtp3.mta.ca with esmtp (Exim 4.80) (envelope-from ) id 1ZdoIU-0006zj-GD; Sun, 20 Sep 2015 20:45:30 -0300 Original-Received: from majordomo by mlist.mta.ca with local (Exim 4.71) (envelope-from ) id 1ZdoIW-0000us-9f for categories-list@mlist.mta.ca; Sun, 20 Sep 2015 20:45:32 -0300 Precedence: bulk Xref: news.gmane.org gmane.science.mathematics.categories:8698 Archived-At: 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/ ]