Algorithmically processable representation of groups

46 Views Asked by At

In this question the word group means a group which can be described with finitely many generators and finitely many relations.


I know that no algorithm can tell anything about a group, given number of generators and list of relations. Can't even tell if the group has more than one element. So, although describing groups with relations is convenient for us, it's "not that good" for computers. Is there any other way to define groups, which can be processed by computer? I will now try to formalize my question with three options. Affirmative answer to any one of them means affirmative answer to the general problem. Moreover, maybe there's some other way of doing what I want.

Q1. Is there an injection from all groups into natural numbers, such that there's a algorithm which takes a number (image of a group), a word in this group (meaning product of generators and its inverses) and replies whether this word is equal to unity.
Actually, instead of injection $G\to\mathbb{N}$ it's fine to assume a surjection from some subset of numbers onto groups $\mathbb{N}\supset S\to G$, doesn't matter much if a group can have multiple encodings.

Q2. Is there an algorithm, which prints out, one by one, numbers of generators and lists of relations of all possible groups, but without repeating itself. Meaning, it does not print a description, which defines the same group as has already been printed out.

Q3. Same as Q1, but instead of parsing the word, the algorith just decides any non-trivial property of given group. Say, is it $\{e\}$? is it finite? is it free?

While Q1 and Q3 talk about computer working with the group in some encoding, Q2 is about if computer can at least perform such encoding without understanding what groups are at all. This is a curiosity question. I gave formal problems just as examples of my broader question: whether there is a way to describe groups so that computer can work with them in any way.