Exercise 8:

{u,v,RΣ={a,b}    uRv}{u,v,RΣ2    uRv    R2˙ (as a set, i.e., not counting repetitions)}\{\langle u,v,R\rangle\mid\Sigma=\{a,b\}\;\wedge\;u\to_R^*v\}\quad\leq\quad\{\langle u,v,R\rangle \mid |\Sigma|\leq 2\;\wedge\;u\to_R^*v\;\wedge\;|R|\notin\dot{2}\text{ (as a set, i.e., not counting repetitions)}\}
Reduce the word reachability problem restricted to the alphabet {a,b}\{a,b\} to the set of tuples u,v,R\langle u,v,R\rangle where u,vu,v are words, RR is a word rewrite system, the used alphabet has at most 22 symbols, uu reaches vv using RR, and the number of rules of RR is odd (by considering RR as a set, i.e., each different rule is counted only once) in order to prove that such set is undecidable (not recursive).
Authors: Guillem Godoy / Documentation:
To be able to submit you need to either log in, register, or become a guest.