Date: Sun, 23 Jul 2000 14:31:26 +0200 (CEST) From: Oliver Fromme <olli@dorifer.heim3.tu-clausthal.de> To: freebsd-chat@FreeBSD.ORG Subject: Re: dc Message-ID: <200007231231.OAA37963@dorifer.heim3.tu-clausthal.de> In-Reply-To: <8leo5p$2bm6$1@atlantis.rz.tu-clausthal.de>
next in thread | previous in thread | raw e-mail | index | archive | help
In list.freebsd-chat Alexander Langer <alex@big.endian.de> 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200007231231.OAA37963>