"The" category of Turing machines?

Question

Disclaimer: I know very little about complexity theory.

I'm sorry but there is really no way to ask this question without being (terribly) concise:

What should be the morphisms in "the" category of Turing machines?

This is obviously subjective and depends upon one's interpretation of the theory, so an answer to this question should ideally give some evidence and reasoning supporting the answer as well.

I'd like to emphasis the point that i'm looking for a category of Turing machines and not of formal languages for example. In particular I think my morphisms should contain finer information then reductions or anything like that (I'm not sure though).

Of course if there's already a well known and used category in the literature i'd like to know what it is.

Answer 1

Saal Hardali mentioned that he wanted a category of Turing machines to do geometry (or at least homotopy theory) on. However, there are a lot of different ways to achieve similar aims.

• There is a very strong analogy between computability and topology. The intuition is that termination/nontermination is like the Sierpinski space, since termination is finitely observable (i.e., open) and nontermination isn't (not open). See Martin Escardo's lecture notes Synthetic topology of data types and classical spaces for a moderately gentle but comprehensive introduction to these ideas.

• In concurrent and distributed computation, it is often useful to think of the possible executions of a program as a space, and then various synchronization constraints can be expressed as homotopical properties of the space. (The fact that execution has a time order seems to call for directed homotopy theory, rather than ordinary homotopy theory.)

  See Eric Goubault's article Some Geometric Perspectives on Concurrency Theory for more details. Also see Maurice Herlihy and Nir Shavit's Goedel-prize winning paper, The Topological Structure of Asynchronous Computability, which settled some long-standing open problems in the theory of distributed programming.

• A third idea comes via homotopy type theory, via the discovery that Martin-Löf type theory is (likely?) a syntactic presentation (in the sense of generators and relations) of the theory of omega-groupoids -- ie, the models of abstract homotopy theory. The best introduction to these ideas is the homotopy type theory book.

Note that all of these ideas are very different from each other, but all still use geometric intuitions! And there are still others, which I don't know, like the uses that arise in geometric complexity theory, and the way that the theories of circuits can be described in terms of the (co)homology theory of graphs.

Basically, when you are doing CS, geometry is a tool -- you use it to formalize your intuitions, so that you can get leverage via the enormous body of work that has been done on it. But it's an idea amplifier, not a substitute for having ideas!

Answer 2

If your objects are Turing machines, there are several reasonable possibilities for morphisms. For example:

1) Consider Turing machines as the automata they are, and consider the usual morphisms of automata (maps between the alphabets and the states that are consistent with one another) which also either preserve the motions of the tape head(s), or exactly reverse them (e.g. whenever the source TM goes left, the target TM goes right and vice versa).

2a) Consider simulations or bisimulations.

2b) Along similar lines, you can consider when one TM can be transformed (by a computable function) to simulate the other one. This can be done at the level of step-wise behavior, or as Yuval suggested in the comments, at the level of input-output, that is, a morphism from $T_1$ to $T_2$ (or maybe the other way around) is a computable $f$ such that $T_1(x) = T_2(f(x))$ for all $x$.

3) Consider the transition graph of the Turing machine (each vertex is a complete description of the state of the machine and the tapes, with directed edges corresponding to the transitions the TM would make) and consider morphisms of graphs. For TMs this is a very coarse relationship, however, as it essentially ignores the local nature of computation (it ignores, for example, what the contents of the tapes are).

I think the real question is: what is it you want to know about TMs or to do with them? In the absence of this, it's hard to give arguments for any one definition over another, beyond naturality (in the usual sense of the word, not the categorical sense).

Answer 3

You might be interested in Turing categories by Robin Cockett and Pieter Hofstra. From the point of view of category theory the question "what is the category of Turing machines" is less interesting than "what is the categorical structure which underlies computation". Thus, Robin and Pieter identify a general kind of category that is suitable for developing computability theory. Then, there are several possibilities for defining such a category starting from Turing machines. Why have one category when you can have a whole category of them?