Archives for Research

Talk: Computability of Bass-Serre structures in the Grzegorczyk hierarchy

My chum the inimitable David Cushing has started a postgrad pure maths seminar at Newcastle. Because there are only a few pure postgrads here, he asked me to give a talk about the stuff I was looking at for the …

Gatterdam’s proof that free products with amalgamation are $\mathcal{E}^{n+1}$-computable

I haven’t posted any research in ages! I haven’t done any research in ages! Here’s a rewriting of a theorem from Ronald Gatterdam’s doctoral thesis, in more sensible language. I’ve proved the same theorem for fundamental groups of graphs of …

Double coset normal form for FPAs

Liza Frenkel is visiting the department, and she wants me to write an algorithm to compute double coset representation normal forms for free products with amalgamation.

Here are some notes I typed up in write maths, see maths as she …

An $E_3$ fgoagog and an $E_4$ fgoagog

Over Christmas I typed up my Bass-Serre / Grzegorczyk stuff in quite a lot of detail and fairly rigorously. It’s far too much to put up here as blog posts, so here’s a link to the PDF.

The big …

Some notation for FPAs and HNN extensions

In order to define a free product with amalgamation $A \ast_C B$ you need to define $A,B,C$ and embeddings of $C$ into $A$ and $B$. Alternatively, instead of $C$ you can use a homomorphism $phi: A \rightarrow B$ and its …

Infinite trees are $E_3$ (maybe)

Not completely sure about this, but here we go: I will show that an ordered, plane recursive tree is $E_n$-computable, $n \geq 3$, if each vertex has its number of children bounded by an $E_n$ function. So this rules out …

Lists and finite trees are $E_3$

In order to prove the fgoagog thing we need to be able to do computations on trees at a low level of the Grzegorczyk hierarchy, so it doesn’t mess up the complexity of the whole group computation. I will give …

Computable categories

So I read a bit about categories after Peter Hines came up to talk to us.

Categories

A category $C$ is a collection of objects $obj(C)$ (or just Obj), a collection of arrows (or morphisms) $hom(C)$ (or just Hom)

The computability of a fgoagog (intro)

I’m going to write up a result I think I’ve proved, which follows on from Gatterdam’s thesis. He showed that if a group is $E_n$ computable, then doing a free product with amalgamation or any number of HNN extensions to …

Groups and the Grzegorczyk Hierarchy

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 …