I guess I sort of reasoned backwards, taking as my point of departure the (wrong) belief HPSG, PATR etc. are not Turing complete, and since DCG (at least withot escape) is very similar to those, I wrongly concluded that DCG without escape was not Turing complete. Thanks for correcting me on this!
Best regards, Torbjörn
On Fri, Apr 11, 2008 at 10:39 AM, Yannick Versley
<versley at sfs.uni-tuebingen.de> wrote:
> > DCG with escape to Prolog is turing complete, but DCG without that
> > escape is not. That's why I did not use escape to Prolog in my
> > example.
> Oh, you can write a Turing machine in DCG just fine:
> (note that tm_table is not a proper predicate, but a DCG rule that has an
> epsilon production for every entry of the turing table. And it would be
> perfectly possible to rewrite the whole thing so that it uses a chain of
> unary rules instead of lots of epsilon rules).
> as long as you can hide your computation in a chain of unary productions, you
> can sneak in all the Turing-ness you want. In fact, any symbol annotation
> that is more complex than a stack will give you turing-completeness. (i.e.,
> s(s(s(0)) - one counter- is allowed AFAIK, but a(s(s(0)),s(0)) - two
> counters - is not, roughly speaking, unless you constrain the possible symbol
> Of course, in real grammars, you *want* to avoid potentially infinite chains
> of unary and/or epsilon productions.
> Yannick Versley
> Seminar für Sprachwissenschaft, Abt. Computerlinguistik
> Wilhelmstr. 19, 72074 Tübingen
> Tel.: (07071) 29 77352