Reduce the word reachability problem restricted to the alphabet
{a,b} to
the set of tuples
⟨u,v,R⟩ where
u,v are words,
R is a word
rewrite system, the used alphabet has at most
3 symbols,
u reaches
v
using
R with an even number of steps, but it is not possible with an odd
number of steps, in order to prove that such set is undecidable (not
recursive).
The use of morphism is not allowed in the description of this reduction.