[Haskell-cafe] [Ann] group-theory

[Carter Schonwald]

Absolutely.

I do think that the moment you start caring about representations or
presentations, as I believe emily has mentioned, some stronger assumptions
for certain families of interfaces is worth considering to allow for cool
stuff when those assumptions are admissible.

On Sun, Dec 13, 2020 at 1:51 AM Zemyla <zemyla at gmail.com> wrote:

> 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.
>
> _______________________________________________
> 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/cc66d227/attachment.html>