## Computable Groups

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 $(mu x)[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} \rightarrow S$ which is recursive. We say that $j = i(s)$ is the *index* of the element $s in S$, 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) \rightarrow i(G)$, obeying $g_jg_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) \rightarrow 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 $\phi: G \rightarrow F$. We can define a corresponding homomorphism $\overline{\phi}: i_1(G) \rightarrow i_2(F)$ on the indices, and we say that $\phi$ is computable iff $\overline{\phi}$ 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 = \langle x_1, \dots, x_n \rangle$ 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 $\Leftrightarrow$ $F/U$ computable $\Leftrightarrow$ $i(U)$ recursive $\Leftrightarrow$ $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.