# Computable categories

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

## Categories

A category *objects* **Obj**), a collection of *arrows* (or morphisms) **Hom)**, and an arrow *composition* operation

An arrow has a single *source *object and a single *target* object, and is written

The composition operation joins up pairs of arrows when possible and a category is closed under arrow composition, so if

Arrow composition is associative, so

A *functor* *Structure-preserving* means we require that

## Groups and categories

Any group can be thought of as a category – there is one object, and the arrows are the group elements. You could associate to each element

Suppose you have two groups. You can make a category with them both in, just by taking the disjoint union of the respective individual categories. If you have a homorphism between the two groups, you can add that in as an arrow and everything still works – if you have

If you have another arrow going the other way from

One of the things I was going to look at next was other kinds of group extensions apart from Bass-Serre graphs of groups. If I phrase the computability stuff in terms of categories, then all you have to do is say what the homomorphisms are and I can construct a computable function representing the group.

## Computable categories

So I need to define a computable category.

A category

- There is an
-decidable indexing${E}_{n}$ of the objects.$o:Obj\to \mathbb{N}$ - There is an
-decidable indexing${E}_{n}$ of the arrows.$i:Hom\to \mathbb{N}$ - There are
-computable functions${E}_{n}$ and$\iota :i(Hom)\to o(Obj)$ associating with each arrow its source and terminal objects.$\tau :i(Hom)\to o(Obj)$ - There is an
-computable composition function${E}_{n}$ satisfying$c:i(Hom)\times i(Hom)\to i(Hom)$ .$c(i(f),i(g))=i(f\circ g)$

All of of

Given two

So, my first task will be to rewrite the index for the free group in this category language, which should carry across directly. Then, for any finitely-presented group