dana.scott at cs.cmu.edu
Sun Jan 21 13:03:28 EST 2007
Take any equational theory with an unsolvable word
problem (e.g., monoids, groups, rings, lattices).
Then take as identities the axioms of the theory plus
a number of equations between constants (i.e., thinking
of generators and relations).
Hence, the problem of deducing another equation (without
variables, a special kind of identity) is exactly the
original word problem for the theory.
More information about the FOM