19
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • 3
    $\begingroup$ You said it yourself - computable functions. $\endgroup$
    – Yuval Filmus
    Jan 18, 2017 at 16:34
  • 1
    $\begingroup$ @Raphael the thing is you never really define a structure until you put it in a category. That's when the inessential features of the specific definition are stripped away. $\endgroup$
    – Saal Hardali
    Jan 18, 2017 at 21:25
  • 1
    $\begingroup$ @SaalHardali Keep in mind that not everybody subscribes to the promise of salvation made by category theorists. In fact, many roll their eyes. $\endgroup$
    – Raphael
    Jan 18, 2017 at 21:32
  • 2
    $\begingroup$ @JoshuaGrochow There is a morphism labeled $f$ from $T_1$ to $T_2$ if $f$ reduces $T_2$ to $T_1$ (or perhaps the other way around), that is $T_1(x) = T_2(f(x))$. This is, say, for machines which on every input either halt or not, but don't have any further output. $\endgroup$
    – Yuval Filmus
    Jan 19, 2017 at 18:50
  • 3
    $\begingroup$ Aside: why should TMs be objects? They could also be morphisms. $\endgroup$
    – Martin Berger
    Jan 20, 2017 at 10:05

3 Answers 3

Reset to default
12
$\begingroup$

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!

Improve this answer
$\endgroup$
15
$\begingroup$

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).

Improve this answer
$\endgroup$
5
  • $\begingroup$ I'm very new to this kind of math. I have read in the past about complexity theory but only recently I've picked it up again after I saw someone on the internet claiming that somehow cohomological techniques would enter complexity theory in the next century and it got me interested. After some reading I realized that beyond some superficial understanding of the definition of a turing machine I have basically no idea what it encodes exactly. That's how I arrived at the question. So you could say that at a very rudimentary level i'm trying to imagine how cohomology can enter complexity theory. $\endgroup$
    – Saal Hardali
    Jan 19, 2017 at 19:00
  • $\begingroup$ I realise this is extremly premature for someone like me who understands very little about this topic still I wanted to play a bit with this idea in my head of "doing homotopy theory on the category of turing machines". Your answer is nice and I certainly aim to read more into aspects of it. Thank you. $\endgroup$
    – Saal Hardali
    Jan 19, 2017 at 19:03
  • $\begingroup$ @SaalHardali: I am curious where you read that cohomology will enter complexity theory? I can think of two ways, but I don't yet see a route via homotopy type theory (perhaps because I don't yet understand HoTT well enough yet). The two ways I can see: (1) in distributed computing this has already happened, viz. Herlihy and Rajsbaum, and (2) via geometric complexity theory. $\endgroup$
    – Joshua Grochow
    Jan 20, 2017 at 0:30
  • $\begingroup$ By homotopy theory i was reffering to the general idea of studying categories with weak equivalences and not so much HoTT. I read it in a poll about P=?NP it's not hard to find I think it was linked to from one of the questions on this site. I guess my first guess (as an outsider) was that maybe there's some kind of interesting weak equivalence on some category of a model of computation that corresponds to complexity classes somehow and then studying functors invariant under those weak equivalence will constitue what I call a "homotopy theory" this is probably very naive and total miss though. $\endgroup$
    – Saal Hardali
    Jan 20, 2017 at 0:36
  • $\begingroup$ In case your interest is complexity theory rather than computability theory, maybe this answer is helpful to you: cstheory.stackexchange.com/a/3422/4896 $\endgroup$
    – Sasho Nikolov
    Jan 20, 2017 at 9:11
15
$\begingroup$

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?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.