Reduce the word reachability problem restricted to the alphabet
{a,b} to
the set of tuples
⟨u,R⟩ where
u is a word,
R is a word
rewrite system, the used alphabet has at most
4 symbols, and
u reaches
u
using
R 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.