From owner-freebsd-chat Sun Jul 23 5:31:30 2000 Delivered-To: freebsd-chat@freebsd.org Received: from dorifer.heim3.tu-clausthal.de (dorifer.heim3.tu-clausthal.de [139.174.243.252]) by hub.freebsd.org (Postfix) with ESMTP id 1391A37B8D4 for ; Sun, 23 Jul 2000 05:31:27 -0700 (PDT) (envelope-from olli@dorifer.heim3.tu-clausthal.de) Received: (from olli@localhost) by dorifer.heim3.tu-clausthal.de (8.9.3/8.9.3) id OAA37963; Sun, 23 Jul 2000 14:31:26 +0200 (CEST) (envelope-from olli) Date: Sun, 23 Jul 2000 14:31:26 +0200 (CEST) Message-Id: <200007231231.OAA37963@dorifer.heim3.tu-clausthal.de> From: Oliver Fromme To: freebsd-chat@FreeBSD.ORG Reply-To: freebsd-chat@FreeBSD.ORG Subject: Re: dc X-Newsgroups: list.freebsd-chat In-Reply-To: <8leo5p$2bm6$1@atlantis.rz.tu-clausthal.de> Organization: Administration TU Clausthal MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: tin/1.4.1-19991201 ("Polish") (UNIX) (FreeBSD/3.4-19991219-STABLE (i386)) MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit Sender: owner-freebsd-chat@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.org In list.freebsd-chat Alexander Langer wrote: > Thus spake Oliver Fromme (olli@dorifer.heim3.tu-clausthal.de): > [...] > > By the way, I even think that dc is turing-complete. > > I haven't tried to prove it, though. :) > > *g* > Hmm. What would one do to prove it? You'd have to prove that it is equivalent to a turing machine, i.e. that you could implement a turing machine with it. One example of such an implementation would be sufficient to prove it. Since dc provides input and output facilities, infinitely sized stacks (at least the manpage doesn't mention any limits) and conditional constructs, I'm pretty sure that it's turing-complete. Although it's probably non-trivial to prove. Regards Oliver -- Oliver Fromme, Leibnizstr. 18/61, 38678 Clausthal, Germany (Info: finger userinfo:olli@dorifer.heim3.tu-clausthal.de) Addresses will change soon!! If in doubt: www.fromme.com "In jedem Stück Kohle wartet ein Diamant auf seine Geburt" (Terry Pratchett) To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-chat" in the body of the message