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, and the number of rules of
R is even (by considering
R as a set,
i.e., each different rule is counted only once), in order to prove that such
set is undecidable (not recursive).
The use of morphism is not allowed in the description of this reduction.