Reduce the word reachability problem restricted to the alphabet
the set of tuples
is a word
rewrite system, the used alphabet has at most
, and the number of rules of
is odd (by considering
as a list,
i.e., each different rule is counted as many times as it occurs in
order to prove that such set is undecidable (not recursive).
The use of morphism is not allowed in the description of this reduction.