Lists and finite trees are $E_{3}$

2010-07-16

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 a model of finite trees that lies in $E_{3}$ , the same level as Cannonito/Gatterdam’s standard index for the free group. (( this post has been sitting as a draft since the beginning of May because I wanted to make some nice tree pictures, but I’d rather just publish it now. So, the trees section is copied out of my notes and might not make sense ))

Computable categories

2010-07-15

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

The computability of a fgoagog (intro)

2010-05-15

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 it results in a group which is at worst $E_{n + 1}$ computable. What I’m going to say is that the fundamental group of a graph of $E_{n}$ groups is at most $E_{n + 1}$ computable. This isn’t unreasonable, because a fgoagog (( ‘fgoagog’ is short for ‘fundamental group of a graph of groups’, because I can’t be doing with writing that out once every three minutes )) represents a load of HNN extensions and amalgamated products.

The tactic will be to follow Gatterdam’s method for amalgamated products – if we can find an algorithm which solves the word problem of the fgoagog (decides if a word on the generators is equivalent to the identity) in $E_{n + 1}$ time, then the whole group is $E_{n + 1}$ computable as a quotient of the free group by the set of trivial words.

I will define an admissible form for words from the fgoagog, which is an alternating series of edge letters and words from the vertex groups, such that the edge letters make up a cycle starting and ending at the base vertex. Once we have a word in admissible form, we can reduce it by swapping the image of an edge group in one vertex with its counterpart in the vertex at the other end, and eventually a trivial word will end up as just a word on the base vertex, which is an $E_{n}$ decision.

Clearly the process of putting a word in admissible form involves knowing something about the shape of the graph, so we need to make some $E_{n}$ computable functions which can represent the graph and compute paths between vertices. That’s a tiny bit interesting on its own, so I’ll spend my next post talking about that. It will need some pretty pictures of trees though, which is why I’ve put off writing it for so long.

Interesting papers collection

2010-04-06

I've started a collection of interesting non-pregroup-related papers on Mendeley. At the moment this includes a formal system which makes the diagrams in Euclid's proofs a part of the formal reasoning, and "How to explain zero-knowledge protocols to your children"

Groups and the Grzegorczyk Hierarchy

2010-03-01

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 $x i n A$ , 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}$ .

Computable Groups

2010-02-22

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 $(m u 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 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.

Serre’s Graphs and Trees

2010-02-10

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.

The Grzegorczyk Hierarchy

2010-02-02

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.

What’s a pregroup?

2010-02-02

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.

yo.

2010-02-02

Here’s a new blog, to write mathematics on.

$e^{i π} + 1 = 0$

Check my working
clp's techy blog

Lists and finite trees are $E_{3}$

Computable categories

Categories

The computability of a fgoagog (intro)

Interesting papers collection

Groups and the Grzegorczyk Hierarchy

$E_{n}$ computable groups

Computable Groups

Computable functions and sets

Serre’s Graphs and Trees

The Grzegorczyk Hierarchy

What’s a pregroup?

Definitions

yo.

Categories

En computable groups

Computable functions and sets

Definitions

$E_{n}$ computable groups