[Corpora-List] context-DEPENDENT grammar simulator.

[Yannick Versley]

> 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