Grigory Sarnitskiy wrote:
I'm not very familiar with algebra and I have a question.
Imagine we have ring K. We also have two expressions formed by
elements from K and binary operations (+) (*) from K.
Can we decide weather these two expressions are equivalent? If there
is such an algorithm, where can I find something in Haskell about it?
If there is no such algorithm for a ring, maybe there is for a field?
Deciding whether two elements are equal depends a lot on the ring K in
question. For instance, if K is the ring of polynomials in one variable,
you have, every element has the normal form
a_0 + a_1 * x + a_2 * x^2 + .. + a_n * x^n
and you can compare coefficients to decide whether equalities like
(x-1)(x^2+x+1) = x^3 - 1
hold. For polynomial rings in several variables, things are trickier,
but there is Buchberger's algorithm that can be used to solve such problems.
As Michael already mentioned, the problem is undecidable in general
since it includes group rings.
Regards,
Heinrich Apfelmus
--
http://apfelmus.nfshost.com
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
