From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/6356 Path: news.gmane.org!not-for-mail From: "Noson S. Yanofsky" Newsgroups: gmane.science.mathematics.categories Subject: Galois Theory of Algorithms Date: Wed, 3 Nov 2010 12:15:06 -0400 Message-ID: Reply-To: "Noson S. Yanofsky" NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Trace: dough.gmane.org 1288923933 18561 80.91.229.12 (5 Nov 2010 02:25:33 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 5 Nov 2010 02:25:33 +0000 (UTC) To: "'Categories list'" Original-X-From: majordomo@mlist.mta.ca Fri Nov 05 03:25:28 2010 Return-path: Envelope-to: gsmc-categories@m.gmane.org Original-Received: from smtpx.mta.ca ([138.73.1.114]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1PEBzb-0006ba-Mi for gsmc-categories@m.gmane.org; Fri, 05 Nov 2010 03:25:27 +0100 Original-Received: from mlist.mta.ca ([138.73.1.63]:33519) by smtpx.mta.ca with esmtp (Exim 4.71) (envelope-from ) id 1PEByb-0000qO-0o; Thu, 04 Nov 2010 23:24:25 -0300 Original-Received: from majordomo by mlist.mta.ca with local (Exim 4.71) (envelope-from ) id 1PEByW-0002LE-Dz for categories-list@mlist.mta.ca; Thu, 04 Nov 2010 23:24:20 -0300 Content-Language: en-us Precedence: bulk Xref: news.gmane.org gmane.science.mathematics.categories:6356 Archived-At: Hi, I posted a new paper on the arxiv: Title: Galois Theory of Algorithms http://arxiv.org/abs/1011.0014 Abstract: Many different programs are the implementation of the same algorithm. This makes the collection of algorithms a quotient of the collection of programs. Similarly, there are many different algorithms that implement the same computable function. This makes the collection of computable functions into a quotient of the collection of algorithms. Algorithms are intermediate between programs and functions: Programs -> Algorithms -> Functions. Galois theory investigates the way that a subobject sits inside an object. We investigate how a quotient object sits inside an object. By looking at the Galois group of programs, we study the intermediate types of algorithms possible. Along the way, we formalize the intuition that one program can be substituted for another if they are the same algorithm. I would be most interested in any comments or criticisms. All the best, Noson [For admin and other information see: http://www.mta.ca/~cat-dist/ ]