This is Rabin’s definition of computable groups. There’s a slightly different version by Mal’cev but I haven’t read it and Rabin seems the most popular from my perspective.

Computable functions and sets

Very quickly: the primitive recursive functions are the class of functions that starts with the same primitives as the Grzegorczyk hierarchy, closed under composition and unbounded recursion. The recursive functions are the primitive recursive functions also closed under minimalisation, the operation which gives you the least $n$ such that some $P(n)=1$ (( “the least x such that P(x) holds” is written $(mux)[P(x)]$ )) . Because those all sound like fairly possible things to do, recursive functions are also called (effectively) computable functions.

For any subset $S\subseteq \mathbb{N}$ of the natural numbers, one can define a characteristic function $c_S(n)$, which takes the value $c_S(x)=1$ when $x\in S$, and $0$ otherwise. A set $S$ is said to be recursive if its characteristic function $c_S$ is recursive.

Computable groups

An indexing of a set $S\subseteq \mathbb{N}$ is a bijection $i:\mathbb{N}\to S$ which is recursive. We say that $j=i(s)$ is the index of the element $sinS$, and denote by $s_j$ the element whose index is $j$.

An indexing $i$ of a group $G$ is admissible if the corresponding multiplication function $m:i(G)\times i(G)\to i(G)$, obeying $g_j{g}_k=g_{m(j,k)}$, is computable.

Given a group with index $i$ and multiplication function $m$, one can compute the inverse function $in(x):i(G)\to i(G)$ as follows:

$$in(j)=\underset{k}{\mu }(k\in i(G)\wedge m(j,k)=i(1))$$

Suppose we have two computable groups $G$ and $F$, with indices $i_1$ and $i_2$ respectively, and a homomorphism $\varphi :G\to F$. We can define a corresponding homomorphism $\bar{\varphi }:i_1(G)\to i_2(F)$ on the indices, and we say that $\varphi$ is computable iff $\bar{\varphi }$ is.

The word problem

It should be clear that a computable group has solvable word problem, but what about the other way round? It turns out that all finitely generated groups with solvable word problem, at least, are computable.

To prove this, we need a couple of theorems first:

Theorem 1. Suppose we have a finitely generated computable group $G$ with a normal subgroup $H$. Then $G/H$ is computable if and only if $i(H)$ is recursive.

Theorem 2. The free group $F$ on $n$ generators is computable.

The latter theorem just requires your favourite way of encoding a sequence of integers, then a little argument about freely reducing words to get the multiplication function.

Now I’m going to give the proof of the main theorem because it is like a tongue-twister:

Theorem 3

A finitely generated group $G$ has a solvable word problem with respect to a system of generators $S=(g_1,\dots ,g_n)$ if and only if $G$ is a computable group.

Proof

Let $F=⟨x_1,\dots ,x_n⟩$ be the free group on $n$ generators with index $i$. Let $U$ be the set of words on $F$ which are sent to the identity in $G$ by replacing $x_i$ with $g_i$.

$i(U)$ is recursive if and only if $G$ has solvable word problem (( “has solvable word problem” means there is a recursive (computable) function which characterises the set of trivial words )) .

Now notice that $F/U\approx G$. So $G$ is computable iff $F/U$ is, and by Theorem 1, $F/U$ is computable if and only if $i(U)$ is recursive. But I just said $i(U)$ is recursive if and only if $G$ has solvable word problem, so $G$ is computable if and only if it has solvable word problem.

To recap:

$G$ computable $\iff$ $F/U$ computable $\iff$ $i(U)$ recursive $\iff$ $G$ has solvable word problem.

QED!

References

Rabin M. O. Computable Algebra, General Theory and Theory of Computable Fields. Transactions of the American Mathematical Society. 1960;95(2):341 – 360.