From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/4926 Path: news.gmane.org!not-for-mail From: Thorsten Altenkirch Newsgroups: gmane.science.mathematics.categories Subject: Re: Decidability of the theory of a monad Date: Fri, 5 Jun 2009 09:58:21 +0100 Message-ID: Reply-To: Thorsten Altenkirch NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 (Apple Message framework v930.3) Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1244224251 13145 80.91.229.12 (5 Jun 2009 17:50:51 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 5 Jun 2009 17:50:51 +0000 (UTC) To: categories List Original-X-From: categories@mta.ca Fri Jun 05 19:50:46 2009 Return-path: Envelope-to: gsmc-categories@m.gmane.org Original-Received: from mailserv.mta.ca ([138.73.1.1]) by lo.gmane.org with esmtp (Exim 4.50) id 1MCdYz-0001Ky-1S for gsmc-categories@m.gmane.org; Fri, 05 Jun 2009 19:50:45 +0200 Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1MCcur-0000HW-0l for categories-list@mta.ca; Fri, 05 Jun 2009 14:09:17 -0300 Original-Sender: categories@mta.ca Precedence: bulk Xref: news.gmane.org gmane.science.mathematics.categories:4926 Archived-At: Hi, Sam Lindley and Ian Stark proved that Moggi's computational Metalanguage (\lambda_ML) is decidable - this is simply typed lambda calculus with a monad. If I am not mistaken your theory can be faithfully encoded in \lambda_ML. Actually, isn't it the case that the continuation monad is actually the free monad. Hence, using this result decidability of \lambda_ML should follow from the decidability of simply typed lambda calculus. Cheers, Thorsten http://www.springerlink.com/content/y44yn0fg76dthfnn/ On 3 Jun 2009, at 12:10, Andrej Bauer wrote: > Consider the theory of a monad, i.e., the axioms are those of a > category and a monad given as a triple: an operation T on objects, for > each object A a morphism eta_A : A -> T A, and an operation lift_{A,B} > which maps morphisms f : A -> T B to lift f : T A -> T B. Concretely, > the axioms are (where lift f is written f* and composition is > juxtaposition): > > id f = f > f id = f > (f g) h = f (g h) > eta* = id > f* eta = f > (f* g)* = f* g* > > Presumably, the equational theory (with partial operations) of such a > triple is decidable. Is this known? If we ignore the types and > partiality, we can attempt to turn the above equations into a > confluent terminating rewrite system using the Knuth-Bendix algorithm, > but it gets stuck (on various orderings I tried). > > A more categorical way of asking the same question is: what is a > concrete description of the free "monad on a category" (is this the > same as "free monad" on "free category"?). > > With kind regards, > > Andrej [For admin and other information see: http://www.mta.ca/~cat-dist/ ]