Reduce the word reachability problem restricted to the alphabet
{a,b} to
the set of tuples
⟨u,v,w,R⟩ where
u,v,w are words,
R is a
word rewrite system, the used alphabet has at most
4 symbols,
u reaches
v
using
R,
v reaches
w using
R,
u is different from
v, and
v is
different from
w, in order to prove that such set is undecidable (not
recursive).
The use of morphism is not allowed in the description of this reduction.