Computable functions may be defined in terms of Turing machines or recursive functions, or some other model of computation. We normally say that the choice doesn't matter, because all models of computation are equivalent. However, something about this bothers me.

Turing machines, for example, operate on strings of tokens, taking strings as input and giving strings as output. If we have another model of computation that also operates on strings then we have no problem saying formally whether it's equivalent to a Turing machine. However, if our model of computation operates on something *other* than strings then we have to define a mapping from its inputs and outputs to strings, and it seems there is no way to formally define whether that mapping is computable or not. (If I am wrong about this, please correct me.) So whenever we talk about equivalence between Turing machines and some non-string based model of computation, we are invoking an informal step; this seems unsatisfying.

It occurs to me that category theory might offer a way out of this, and I'm wondering if this has been done. For example, suppose we define a category with one object, to be interpreted as the set of all strings on some alphabet. We draw an arrow from this set to itself for every (partial) function that can be computed with a Turing machine, and define composition of arrows as function composition.

It is clear that this forms a category. My question is whether this category by itself (i.e. just the morphisms and their relationships, without reference to the underlying string type) tells us everything we need to know about computable functions. In other words, would it make sense to define Turing equivalence in terms of isomorphism to this category?

What I have in mind here is something like this: suppose we're given a model of computation that computes partial functions from some set $S$ to itself. We can then form a category of all partial functions that can be computed by this system and check whether this category is isomorphic to the similar category for Turing machines as defined above. This is appealing, if it works, because we never needed to define a mapping between the elements of $S$ and the elements of the set of strings. (But I'm worried it might not work, due to the possibility of the category isomorphism itself being uncomputable, in some sense.)

Finally, if this idea doesn't work, is there some way to fix it so that it does? I would be interested to hear about any work on defining or reasoning about the set of computable partial functions from a purely categorical point of view, so that it can be characterised without reference to a particular underlying model of computation.