Exercise 27:

{u,v,RΣ={a,b}    uRv}{u,RΣ4    uR+u}\{\langle u,v,R\rangle\mid\Sigma=\{a,b\}\;\wedge\;u\to_R^*v\}\quad\leq\quad\{\langle u,R\rangle \mid |\Sigma|\leq 4\;\wedge\;u\to_R^+u\} (morphism not allowed in the reduction)
Reduce the word reachability problem restricted to the alphabet {a,b}\{a,b\} to the set of tuples u,R\langle u,R\rangle where uu is a word, RR is a word rewrite system, the used alphabet has at most 44 symbols, and uu reaches uu using RR with at least one step, in order to prove that such set is undecidable (not recursive).

The use of morphism is not allowed in the description of this reduction.
Authors: Guillem Godoy / Documentation:
To be able to submit you need to either log in, register, or become a guest.