Skip to main content

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 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 SN of the natural numbers, one can define a characteristic function cS(n), which takes the value cS(x)=1 when xS, and 0 otherwise. A set S is said to be recursive if its characteristic function cS is recursive.

Computable groups

An indexing of a set SN is a bijection i:NS which is recursive. We say that j=i(s) is the index of the element sinS, and denote by sj the element whose index is j.

An indexing i of a group G is admissible if the corresponding multiplication function m:i(G)×i(G)i(G), obeying gjgk=gm(j,k), is computable.

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


Suppose we have two computable groups G and F, with indices i1 and i2 respectively, and a homomorphism ϕ:GF. We can define a corresponding homomorphism ϕ:i1(G)i2(F) on the indices, and we say that ϕ is computable iff ϕ 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=(g1,,gn) if and only if G is a computable group.


Let F=x1,,xn 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 xi with gi.

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/UG. 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 F/U computable i(U) recursive G has solvable word problem.



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