[Haskell-cafe] [Ann] group-theory

Viktor Dukhovni ietf-dane at dukhovni.org
Sun Dec 13 05:39:58 UTC 2020


On Sun, Dec 13, 2020 at 12:19:18AM -0500, Carter Schonwald wrote:

> Having a decidable equality seems important for reasoning about groups.  Or
> computing on representations thereof.

This is of course not always possible.  If a group is presented as a
quotient of a free group on a set of generators via some set of
relators, then deciding whether two words are equal is IIRC known to be
generally intractable.  One can still perform the group operation, but
there is no known terminating algorithm for constructing a canonical
form for an element, performing equality tests, ...

Of course one might take the view that groups where equality is not
computable are not "useful", but that might rule out some applications.

-- 
    Viktor.


More information about the Haskell-Cafe mailing list