[Corpora-List] context-DEPENDENT grammar simulator.

[Torbjörn Lager]

Oops, shame on me. You are right of course (as was also pointed out in
a private mail from Gertan van Noord).

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:
>  parse-->build_list(L),tm(s0,L,[]).
>  build_list([A|As])-->[A],build_list(As).
>  build_list([])-->[].
>
>  tm(s_end,_,_)-->[].
>  tm(State,[A|As],Bs)-->
>         tm_table(State,A,StateNew,A2,Dir),
>         move_tape([A2|As],Bs,Dir,As3,Bs3),
>         tm(StateNew,As3,Bs3).
>  move_tape(As,[B|Bs],right,[B|As],Bs)-->[].
>  move_tape([A1,A2|As],Bs,left,[A2|As],[A1|Bs])-->[].
>  move_tape(As,[],right,[empty|As],[])-->[].
>  move_tape([A1],Bs,left,[empty],[A1|Bs])-->[].
>
>  (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
>  rewrites).
>  Of course, in real grammars, you *want* to avoid potentially infinite chains
>  of unary and/or epsilon productions.
>
>  Best,
>  Yannick
>
>
> --
>  Yannick Versley
>  Seminar für Sprachwissenschaft, Abt. Computerlinguistik
>  Wilhelmstr. 19, 72074 Tübingen
>  Tel.: (07071) 29 77352
>

_______________________________________________
Corpora mailing list
Corpora at uib.no
http://mailman.uib.no/listinfo/corpora