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,
u reaches
v using
R with an odd number of steps, but it
is not possible with an even 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.