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
2 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).