Right, so I’ve written about computable groups and the Grzegorczyk hierarchy previously. Now it’s time to join the two together so we can talk about the computational complexity of certain groups.

$E_n$ computable groups

Let $G$ be a group with an admissible index $i$ and corresponding multiplication function $m$. If $i(G)$ is $E_n$ decidable (( there is an $E_n$ computable function which returns $1$ on numbers which are indices of elements of $G$, and $0$ otherwise )) and $m$ is $E_n$ computable, then $G$ is said to be $E_n$ computable.

We can also add the characteristic function (( $c_A$ such that $c_A(x)=1$ if $xinA$, and $0$ otherwise )) of a particular set to the primitive functions in the Grzegorczyk hierarchy to make some arguments about group computability easier. If we have $c_A$, the characteristic function of the set $A$, to our hierarchy, then we say a function (or group) is $E_n(A)$ computable ((or “$E_n$ computable relative to $A$”)) if it can be obtained from composition and bounded recursion on $E_n$ functions and $c_A$.

Read more…

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.

Read more…

I think this is the last Vast Branch of Mathematics I need to include before heading right into Rimlinger, but who knows? The Bass-Serre theory of fundamental groups of graphs of groups (fgoagogs!) is a very appealing way of representing constructions like free products with amalgamation and HNN extensions, where you create bigger groups by identifying subgroups of ones you’ve already got. Or the other way round; FPAs and HNN extensions are the building blocks of Bass-Serre theory. Whatever.

Read more…

Now to the other end of the subject, computational complexity. The two ends aren’t going to meet in the middle, but the Grzegorczyk Hierarchy is so simple it should be at the start by natural justice, and it’s good to have in mind as a pleasant ending point while getting lost in pregroup theory.

If you want to ask yourself whether a problem is computable or not, you have to define what you mean by ‘computable’. It’s left as an exercise for the reader, basically. So the popular thinking is that effectively computable functions and recursive functions are the same thing – that is, every computable function should be recursive.

Furthermore, a slightly smaller class of functions, the primitive recursive functions, contains pretty much everything anyone’s interested in, and leaves out horror shows like the Ackermann function.

The idea is that you can start with a few really simple initial functions: zero; successor; projection, and the operations of composition and recursion, and end up with pretty much every function on the natural numbers that anyone’s ever thought up. (( before this was claimed and people tried to think of things that weren’t included in this class, anyway ))

A primitive recursive function is one which can be defined by finitely many compositions and recursions on the initial functions. A generally recursive function can be defined using unbounded minimisation as well, but remember that we’re deliberately ignoring those.

Read more…

I’ll just start with a quicky lot of definitions basically copied wholesale out of Rimlinger, then talk about the idea behind them and what they’re useful for, and stuff like that.

Definitions

Start with a pree, which is a set and a partial multiplication table. So we have a set $P$, $D\subset P\times P$, and $m:D\to P$ is the partial multiplication. Write down the pree as $(P,D)$, or just $P$ if you’re cool and don’t need the Man’s rules. Note we haven’t yet got any rules about associativity or inverses or what have you.

Read more…