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 …
Archives for Research
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 …
