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 *un*bounded 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 $\stackrel{\u2015}{\varphi}:{i}_{1}(G)\to {i}_{2}(F)$ on the indices, and we say that $\varphi $ is computable iff $\stackrel{\u2015}{\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=\u27e8{x}_{1},\dots ,{x}_{n}\u27e9$ 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.