Exercise 21:

{u,v,RΣ={a,b}    uRv}{u,v,w,RΣ2    uRvRw    uvw}\{\langle u,v,R\rangle\mid\Sigma=\{a,b\}\;\wedge\;u\to_R^*v\}\quad\leq\quad\{\langle u,v,w,R\rangle \mid |\Sigma|\leq 2\;\wedge\;u\to_R^*v\to_R^*w\;\wedge\;u\neq v\neq w\}
Reduce the word reachability problem restricted to the alphabet {a,b}\{a,b\} to the set of tuples u,v,w,R\langle u,v,w,R\rangle where u,v,wu,v,w are words, RR is a word rewrite system, the used alphabet has at most 22 symbols, uu reaches vv using RR, vv reaches ww using RR, uu is different from vv, and vv is different from ww, 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.