[Haskell-cafe] [Ann] group-theory

[Zemyla]

A simpler example of groups with no computable equality: the Sum group on
computable reals. x + negate x === 0 for all x, but we can never fully
prove it, only demonstrate it for each number of digits. And yet this is a
perfectly well behaved abelian group.

On Sat, Dec 12, 2020, 23:41 Viktor Dukhovni <ietf-dane at dukhovni.org> wrote:

> 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.
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20201213/7fd48b69/attachment.html>