From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/3020 Path: news.gmane.org!not-for-mail From: "Noson Yanofsky" Newsgroups: gmane.science.mathematics.categories Subject: Towards a Definition of an Algorithm Date: Mon, 6 Feb 2006 17:22:44 -0500 Message-ID: NNTP-Posting-Host: main.gmane.org Content-Type: text/plain;charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1241019048 6916 80.91.229.2 (29 Apr 2009 15:30:48 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:30:48 +0000 (UTC) To: "categories@mta. ca" Original-X-From: rrosebru@mta.ca Tue Feb 7 09:41:19 2006 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 07 Feb 2006 09:41:19 -0400 Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.52) id 1F6SvT-0006Jw-74 for categories-list@mta.ca; Tue, 07 Feb 2006 09:30:35 -0400 Original-Sender: cat-dist@mta.ca Precedence: bulk X-Keywords: X-UID: 3 Original-Lines: 33 Xref: news.gmane.org gmane.science.mathematics.categories:3020 Archived-At: Dear All, I just put a paper up at http://arxiv.org/abs/math/0602053 . It should be of interest to many. It uses coherence rules to tell when two programs are essentially the same algorithm. Here is the title and abstract: Towards a Definition of an Algorithm We define an algorithm to be the set of programs that implement or express that algorithm. The set of all programs is partitioned into equivalence classes. Two programs are equivalent if they are ``essentially'' the same program. The set of all equivalence classes is the category of all algorithms. In order to explore these ideas, the set of primitive recursive functions is considered. Each primitive recursive function can be described by many labeled binary trees that show how the function is built up. Each tree is like a program that shows how to compute a function. We give relations that say when two such trees are ``essentially'' the same. An equivalence class of such trees will be called an algorithm. Universal properties of the category of all algorithms are given. Looking forward to hearing any thoughts and criticisms. I hope to see you all in Nova Scotia at CT 2006 this Summer! All the best, Noson (Yanofsky)